Challenge 4 - The Travelling Salesman Problem: Exhaustive, Intuitive and Evolutionary Searches.
Due Monday, November 5, 2001

This challenge, as with all the other challenges, is open ended. There is no single correct answer and there is no single incorrect answer. The optimal response to the challenge would be to modify the code for the Travelling Salesman Problem to implement one or more new solutions. Again, if you are strong on programming you may focus on the application's logic, if you are strong on design then you may focus on visualization and display, and if you are strong on innovative ideas then you may focus on writing pseudocode. You may consider three classes of solutions:

Class of Search For Example Costs Benefits
Random Throw dice. Worse than the worst human intuiation. Hard to imagine.
Exhaustive Try every route.

Since it examines the distance of every possible route it will take an unrealistically long time to find the shortest route for a large number of cities. The number of possible routes increases factorially with the number of cities:

numberOfRoutes = (numberOfCities - 1) ! / 2

 It will find the shortest possible route.
Intuitive Go to the next closest city. It will not find the shortest route. It will find a reasonably short route quickly and easily without a computer.
Evolutionary

Selection

  • Shortest Path

Reproduction:

  • Asexual
  • Unisexual
  • Bisexual

Variation:

  • Mutation
  • Cross-Over
  • Inversion
  • Transposition
 It will not find the shortest route. It will find close to the shortest route rather quickly on a computer.

Note that there are a number of "Mutating Algorithms" available in the C++ Standard Library, which are discussed in the Borland "Help" menu. They include:

Your challenge is to devise one or more algorithms for one or more classes of search. The object of the challenge is to have each participant explore a different approach to solving the problem. Just as with evolutionary mechanisms, it is only by creating a population of different solutions that we can evaluate the effectiveness of varying procedures. Your task is not necessarily to find the best procedure, but to describe one or more procedures that attempt to find the shortest route connecting all the cities.

The project file for a working application without the search algorithms may be found at the bottom of our WORKS IN PROGRESS page or may be distributed on floppy in class.