Introduction

The Traveling Salesman Problem (TSP) is to find an "optimal path" which reaches all points in a graph in the shortest time.

Note: A graph is a structure in discrete mathematics consisting of points (vertices) and lines (edges) that connect them.

• An undirected graph's edges have no direction; they connect two vertices symmetrically. (In other words, point A to point B is the same as point B to point A.)
• Directed graph edges have a direction, connecting an ordered pair of vertices. (In other words, point A to point B may different from point B to point A.)

Project #1

Solve a traveling salesman problem by trying all permutations (paths) and see which path is the smallest.

For simplicity use a brute-force search.

Use a maximum of 5 or 6 points with defined Cartesian coordinates.

Note: Using 4 or 6 points reduces the computation time (CPU cycles) for testing. If you can do it for 4, you can do it for 20. It just takes longer.

The points are in an undirected graph.

Use a defined graph for testing. Once the code is working generate random graphs.

For example

Project #2

Repeat project #1 with a directed graph.

Project #3

Collect TSP execution statistics and plot them. Start with a graphs with 5 or 6 points and end with 10 to 20 points.

Note: Pick an appropriate number of points to show the exponential growth as the number of points increase.

Project #4

Do a little research. Can you find a better algorithm that brute-force?

Links

Travelling salesman problem (Wikipedia)

What is the Traveling Salesman Problem? (YouTube)

What is the difference between an undirected and a directed Graph?