350 rub
Journal Electromagnetic Waves and Electronic Systems №7 for 2016 г.
Article in number:
Approximate solution of traveling salesman problem
Keywords: optimization discrete mathematics complexity
Authors:
A.M. Donetskov - Ph. D. (Eng.), Associate Professor, Department «Computer systems and networks», Kaluga branch of the Bauman MSTU. E-mail: dam@kaluga.ru
Abstract:
The article describes the method for solving the traveling salesman problem. Defined the weighted graph G = , where V - the set of vertices; U - set of edges; W - set of weights of the edges. Required to find the way minimum (maximum) length passing through all vertices of the graph. The article describes the method proposed by the author, the essence of which is as follows. On vertices original graph G is constructed bipartite graph G1, = , where | U1 | = | U |, | X | = | Y | = | V |, the vertex vi (vi ϵ X) is connected by an edge to a vertex vj (vj ϵ Y), if the arc (vi, vj) ϵ U. In the bipartite graph is defined full matching the maximum (minimum) weights. On the edges matching is built «given» graph, where semi-degree outcome and semi-degree income each vertex is equal to 1. If the constructed graph does not contain directed cycles of length less than the number of vertices in the graph, it is found the optimal way, otherwise need to remove all the directed cycles of length less than the count of vertices in a graph, using the formula wпр = w(vi, Гпр(vi)) + w(vj, Гпр(vj)) − w(vi, Гпр(vj)) − w(vj, Гпр(vi)). Among the many options deleting of directed circuits select variant, which weight is of minimal importance. The time complexity of the method proposed solutions is O (n4), and the solutions accuracy is greater than or equal to 3/4 if the initial graph has symmetry property is greater than or equal to 2/3 otherwise.
Pages: 55-58
References

 

  1. Doneckov A.M. Podkhod k resheniju zadachi kommivojazhera // EHlektromagnitnye volny i ehlektronnye sistemy. 2015. T. 20. № 7. 57−60 s.
  2. Kristofides N. Teorija grafov. Algoritmicheskijj podkhod. M.: Mir. 1978. 432 s.
  3. Emelichev V.A., Kovalev M.M., Kravcov M.K. Mnogogranniki, grafy, optimizacija. M.: Nauka. 1981. 344 s.
  4. Sedzhvik R. Fundamentalnye algoritmy na C++. Algoritmy na grafakh. SPb.: OOO «DiaSoftJUP». 2002. 496 s.
  5. Papadimitriou C., Steiglitz K. On the Complexity of Local Search for the Traveling Salesman Problem // J.SIAM.Comp. 1977. V. 6. N 1. P. 76−83.
  6. Gehri M., Dzhonson D. Vychislitelnye mashiny i trudnoreshaemye zadachi. M.: Mir. 1982. 416 s.
  7. Doneckov A.M. Reshenie zadach perestanovochnogo tipa pri proektirovanii pechatnykh plat. M.: Sredstva svjazi. 1991. № 1. 56−59 s.
  8. Novikov F.A. Diskretnaja matematika dlja programmistov. SPb.: Piter. 2009. 384 s.
  9. Svami M., Tkhulasiraman K. Grafy, seti i algoritmy. M.: Mir. 1984. 454 s.
  10. Kormen T., Lejjzerson CH., Rivest R., SHtajjn K. Algoritmy: postroenie i analiz. M.: Viljams. 2013. 1324 s.