Traveling Salesman Problem using Hill Climbing

Hill climbing is a mathematical optimization algorithm whose purpose is to find the best solution to a problem with a (large) number of possible solutions.

Explaining the algorithm (and optimization in general) is best done using an example. In the Travelling salesman problem, we have a salesman who needs to visit several cities exactly once, after which he returns to the first city. The distances between each pair of cities are known, and we need to find the shortest route. As you can imagine, there is (often) a large number of possible solutions (routes) to a specific Travelling salesman problem; the goal is to find the best (i.e., the shortest) solution.