Fences and Traveling Salesmen

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. 

     

We receive a few cents from each purchase.  Thanks

 


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa 365 Puzzlers  Calendar 2017

Mensa 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

Problem Description

Here are three "connect-the-dot" algorithms tied together by a common user interface.

bulletSimple Path connects an arbitrary arrangement of points with no line crossings.
bulletConvex Hull can draw a minimal length "fence" around any collection of dots with the property that all of the interior angles are less than 180o.   If the points were pegs, a piece of string wrapped around the pegs would define the convex hull. 
bulletFinally, Shortest Path introduces the Traveling Salesman problem.  The salesman needs to visit a set of cities and wants to plan his route so that the distance traveled is as short as possible.    

Background & Techniques

Simple Path

The 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 Hull

Pick 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:

  1. Draw some points on a piece of paper and select the lowest one, P1
  2. Draw a line extending horizontally to the right and place your pencil on this line with the eraser end on P1.
  3. Keeping the eraser end on P1 (or Pn), rotate the pencil counterclockwise until you touch a point, that's you next point on the hull, P2 (Pn+1).
  4. Draw line from P1 to P2 (Pn to Pn+1) and the slide the pencil along this line until the eraser is on P2 (Pn+1).
  5. Repeat steps 3 and 4 until you get back to P1 and the hull is complete.  

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 Path  

One 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 

bulletBrowse source extract
bulletDownload source
bulletDownload  executable

Suggestions for Further Explorations

The 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-2017, Gary Darby    All rights reserved.