Looking for shortest paths

Most problems can be seen in terms of locating the best solution in the huge space of all possible solutions. For example, finding the shortest path connecting n cities can be solved by choosing the best city to walk to, or by looking through all possible paths and choosing the shortest one. However, for 10 cities there are 3628800 possible paths, and for 30 cities - 265252859812191058636308480000000 paths! No hope to evaluate them no matter what computer power is available.

You can apply various optimization algorithms for this sample problem, including evolutionary algorithm (where an individual is a single path). The OptiVis program demonstrates many optimization techniques. The program shown below presents the shortest path problem (the so-called Traveling Salesman Problem) and provides a few optimization algorithms. Of course, this is just one of the many examples of optimization. The Traveling Salesman Problem itself has many generalizations and practical implementations that provide route optimization in transport and logistics. Some of these generalizations and additional, practical constraints are provided by tools like OptiFacility online optimization service.

Using the applet below, you can click to add cities and right-click to remove them. Enjoy your experiments!