[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem DescriptionHere are three "connect-the-dot" algorithms tied together by a common user interface.
Background & TechniquesSimple PathThe technique for solving this problem is itself pretty simple. We'll start at a point with one of the coordinates at an extreme, say the maximum Y value. Then consider the lines formed by connecting that point to every other point in the set. Compute the angle from horizontal for these lines and sort by that angle. The path from the initial point to each of the sorted points in sequence and back to the initial point is a simple closed path. Convex HullPick the point (biggest Y value) and calculate the included angle from this point to every other point - choose the point with the biggest included angle (or minimum angle from horizontal), draw the line to that point. The idea is that we will swing one complete revolution as we add these hull points. Repeat from the point just added with the added restriction that the new point is one with smallest angle that is also larger than the previous angle. Continue until back to starting point. If I weren't so lazy, I'd draw some graphics here to explain how this works. You can try it yourself like this:
The "sliding the pencil" step keeps us rotating around the hull. The program equivalent is to saving each angle in the prevangle variable and ignoring all angles less than prevangle when searching. The smallest angle greater than prevangle is the one selected as the next point.
Shortest PathOne of a large class of problems called NP-complete (non-deterministic polynomial complete). This term refers to a class of problems for which no polynomial time solution is known, but it has not been proven that no such solution exists. Problems which can be solved in polynomial time have solution times proportional to some combination of powers of the number of elements. Problems which are not polynomial, are exponential (or worse) and solution times increase proportional to some function involving the number of elements as a power, (e.g. 2N). Exhaustive searches requiring N factorial (N!) operations are one the "or worse" cases. The version included here tries the brute force, exhaustive search technique by checking the path length for each possible order of visiting the cities. It can check 50,000 to 200,000 paths per second and works OK up to about 10 points (3.6 million paths checked). It will never solve the 15 cities case (about a trillion, 1012 paths). By simply presorting the points so that each is near its closest neighbor, we can usually get paths that look pretty good in a reasonable period of time. This section of the program uses the TComboSet class defined in the Combos unit and described in Permutes1. (Combos is also included the source download here). TComboSet provide the logic needed to generate all permutations of point numbers to test all possible paths. Running/Exploring the Program
Suggestions for Further ExplorationsThe Traveling Salesman Problem (TSP) has been well studied. I see lots of doctoral theses based on the TSP and lots of web information with techniques used to solve it. Optimum solutions have been found for 13,000 or so cities. Apparently they have been proven optimal by techniques other than exhaustive checking. Some heuristics (rule of thumb tests) are probably easy to implement. For example, just watching the program run for large cases, I can see that path crossings could be easily corrected to give a shorter path. As usual, a Google search will turn up enough pages to keep you occupied for as long as your interest lasts. |
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |