Mazes
From Maze
(Difference between revisions)
(→Mazes in Mathematics) | (→Mazes in Mathematics) | ||
| Line 276: | Line 276: | ||
The problem of solvability in mazes has become part of the purview of mathematics, particularly in the area of "critical path analysis" (CPA). Critically CPA has its origins not in hedgerows or darkened hallways but the twisty little corridors of project management. | The problem of solvability in mazes has become part of the purview of mathematics, particularly in the area of "critical path analysis" (CPA). Critically CPA has its origins not in hedgerows or darkened hallways but the twisty little corridors of project management. | ||
| − | Critical Path Analysis, developed by James E. Kelley and Morgan Walker at Dupont in the late 1950s, became an algorithmic approach to the shortest path problem. This puzzle appears in telephone routing, planning routes for driving, and optimizing circuit boards. | + | George Dantzig, the developer of the simplex algorithm and linear programming, if often credited with playing a pivotal role in the creation of maze solutions. The simplex algorithm addresses the shortest path problem and was originally put in service of minimizing cost on large-scale, Cold War airforce projects. |
| − | "The first autorouter was tested on a map of the maze at Hampton Court Palace about 35 years ago." | + | Curiously, Dantzig himself as acquired legendary status as the student who upon arriving late to a class mistook the historically unsolved problems on the board as his homework. Needless to say, his professor was surprised when he turned in the solutions several weeks later. If nothing else, the story reflects the status of this modern day Theseus. |
| − | An interesting reversal happens. As maze-solving algorithms are applied to more and more real world puzzles, they in turn prove themselves to be mazes of telephones, rest stops, and resisters. | + | Around the same time, Critical Path Method, developed by James E. Kelley and Morgan Walker at Dupont offered an algorithmic approach to the shortest path problem in project management. |
| + | |||
| + | The shortest-path problem has proven to be one of the grand challenges of the late twentieth century. The puzzle appears in telephone routing, planning routes for driving, and optimizing circuit boards. Solutions to the problem would become part of the crucial machinery of electronic networks, for example in autorouters. | ||
| + | |||
| + | Curiously, one website on the history of mazes reports, "The first autorouter was tested on a map of the maze at Hampton Court Palace about 35 years ago." | ||
| + | |||
| + | An interesting reversal happens as math takes up mazes. As maze-solving algorithms are applied to more and more real world puzzles, they in turn prove themselves to be mazes of telephones, rest stops, and resisters. | ||
| + | |||
| + | Even more importantly, the terror of the maze is not the minotaur but time itself, time which can be just as easily lost in unproductive paths. | ||
| + | |||
| + | Of course, the celebrity of 10 Print... grows out of the quest for optimization, where the clever distillation of a solution to one line becomes the sign of mastery. | ||
| + | |||
| + | The mathematical grand challenge of finding the shortest path thus introduces the aesthetic of optimization into the lore of mazes. | ||
James E. Kelley, J., & Walker, M. R. (1959). Critical-path planning and scheduling. In Papers presented at the December 1-3, 1959, eastern joint IRE-AIEE-ACM computer conference (pp. 160-173). Boston, Massachusetts: ACM. doi:10.1145/1460299.1460318 | James E. Kelley, J., & Walker, M. R. (1959). Critical-path planning and scheduling. In Papers presented at the December 1-3, 1959, eastern joint IRE-AIEE-ACM computer conference (pp. 160-173). Boston, Massachusetts: ACM. doi:10.1145/1460299.1460318 | ||
| + | |||
| + | |||
| + | |||
| + | Dantzig, George B. “On the Shortest Route Through a Network.” Management Science 6.2 (1960): 187-190. Print. | ||
---- | ---- | ||
