Home
Welcome to the travelling-salesman-problem wiki!
Suppose that a salesman wants to take a tour between 10 cities and to sell some products and then return home by the end of the day. But he wants to achieve the maximum profit he can possibly get so the problem is if you know that all the roads directly lead from one city to another each road will coast the salesman some money to travel through it, how to choose the set of roads with minimal coast and ends with the salesman at home (the city he started with).
The reader need to be familiar with the following definitions:
Graph: for a set of vertices(points) and a set of edges(lines)
such that every edge connects two vertices, a graph
is the ordered pair
.
-
Weighted Graph: It is a graph where each edge is given a numeric value(weight).
-
Directed Graph: Is a Graph or Weighted Graph in which each edge is associated with a direction
-
Path: Is a sequence of vertices and their connecting edges such that the edges are distinct.
-
Cycle: Is a path that its sequence of vertices starts and ends with the same vertex.
-
Hamiltonian Cycle: Is a cycle in which each vertex is visited once except the first one.
So what we need to do to help the salesman is to consider each city as a node and the roads between them to be the edges and the coast it takes to pass through a road will be the weight of its corresponding edge so we will have a weighted directed graph and the problem is how to find the Hamiltonian cycle that have the minimum sum of edge weights(optimal Hamiltonian cycle).
content not added yet