The
"Traveling Salesman Problem" (TSP) is a common problem applied to
artificial intelligence. The TSP presents the computer with a number of cities,
and the computer must compute the optimal path between the cities. This applet
uses a genetic algorithm to produce a solution to the "Traveling Salesman
Problem".

The
traveling salesman problem (TSP) is a problem in discrete or combinatorial
optimization. It is a prominent illustration of a class of problems in
computational complexity theory, which are classified as NP-hard. In the
traveling-salesman problem, which is closely related to the Hamiltonian cycle
problem, a salesman must visit n cities. Modeling the problem as a complete graph
with n vertices, we can say that the salesman wishes to make a tour, or
hamiltonian cycle, visiting each city exactly once and to finishing at the city
he starts from. There is an integer cost c(i, j) to travel from city i to city
j , and the salesman wishes to make the tour whose total cost is minimum, where
the total cost is the sum of the individual costs along the edges of the tour.

Representing the cities by
vertices and the roads between them by edges. We get a graph. In this graph,
with every edge there is associated a real number such a graph is called a
weighted graph being the weight of edge.

In our problem, if each of the
cities has a road to every other city, we have a complete weighted graph. This
graph has numerators Hamiltonian circuits, and we are to pick the one that has
the smallest sum of the distance

The total number of different
Hamiltonian circuits in a complete graph of n vertices can be shown to be (n -
1)!/2. This follows from the fact that starting from any vertex we have n - 1
edges to choose from the first vertex , n- 2 from the second, n- 3 from the
third, and so on, these being independent, result with (n-1) choices This
number is, however, divided y2, because each Hamiftonian circuit has been
counted twice

Theoretically the problem of
the traveling salesman can always be solved by enumeration all (n-1)!/2
Hamtltonian circuits, calculation the distance traveled in each, and then
picking the shortest one. However for a large value of n, the labor involved is
too great even for a digital computer.

The
problem is to prescribe a manageable algorithm for finding the shortest route.
No efficient algorithm for problems of arbitrary size has yet been found,
although many attempts have been made. Since this problem has application in
operations research, some specific large-scale examples have been worked out.
There are also available several heuristic methods of solution that give a
route very close to the shortest one, but do not guarantee the shortest.

Thanks for this explanation

ReplyDelete