An Algorithm for Path Connections and Its Applications

TLDR

Section VI provides the background context. The study aims to determine whether efficient computer procedures can solve path‑connection problems in logical drawing, wiring diagramming, and optimal route finding. The framework solves path‑connection problems by finding paths that minimize crossings, avoid obstacles, and optimize multiple properties, with implementations on an IBM 704 computer. The algorithm successfully solves a class of path‑connection problems, with a minimal‑distance solution implemented on an IBM 704 computer, and reveals an unexpected link to physical optics.

Abstract

The algorithm described in this paper is the outcome of an endeavor to answer the following question: Is it possible to find procedures which would enable a computer to solve efficiently path-connection problems inherent in logical drawing, wiring diagramming, and optimal route finding? The results are highly encouraging. Within our framework, we are able to solve the following types of problems: 1) To find a path between two points so that it crosses the least number of existing paths. 2) To find a path between two points so that it avoids as much as possible preset obstacles such as edges. 3) To find a path between two points so that the path is optimal with respect to several properties; for example, a path which is not only one of those which cross the fewest number of existing paths, but, among these, is also one of the shortest. The minimal-distance solution has been programmed on an IBM 704 computer, and a number of illustrations are presented. The class of problems solvable by our algorithm is given in a theorem in Section III. A byproduct of this algorithm is a somewhat remote, but unexpected, relation to physical optics. This is discussed in Section VI.