The traveling salesman problem(TSP) is one of the m most important combinatorial optimization problems. The salesman wants to visit some cities and he wants to visit t each city exactly once and return to the beginning city. minimize the total cost of the trip. At first one may to express the equivalence of the problem in graph theory , we are given a complete graph and the cost function such that each vertex represents a city and t he cost function c specifies the cost of going from each city to another one. The goal is to find a minimum cost tour that visits every vertex exactly once, i.e. a Hamiltonian cycle with minimum total cost.