میر محمد علیپور

The path traveling salesman problem is one the most well-known NP-complete problem, where it is restricted to traverse all the nodes exactly ones between two prespecified the source and the destination nodes. So, one the most discussed challenges for this kind of a hard problem is to find a good solution by some. There are some approximate algorithms with tight approximation ratio in the version of the problem that the arc cost values satisfy the triangle inequality. The simulated annealing algorithm is a local search method, which is based on the Markov chain formulation and it discovers a nearby optimal solution. The simulated annealing algorithm produces a solution state space and the Markov chain Monte Carlo search method improves the produced state space. The Metropolis algorithm and Boltzmann distribution function have the critical role to accept or reject the produced solution. The simulated annealing algorithm starts with a relatively high temperature and then the most of the solutions are accepted; however, it is cooled gradually, and at end of the annealing process the temperature is so low that the most of the energy increasing solutions (for a minimizing objective function) are rejected. The Markov chain Monte Carlo method produces some samples around the accepted and the rejected states for the possibly improving directions in the solution state space.