A.M. Donetskov - Ph. D. (Eng.), Associate Professor, Department «Computer systems and networks», Kaluga branch of the Bauman MSTU E-mail: dam@kaluga.ru

Describes an original approach of decision traveling salesman problem. Prerequisite is a weighted graph G = < V, U, W (U) >, where V is the many vertices; U-a lot of edges; W-set weights of edges. Required to find the way minimum (maximum) length passing through all vertices of the graph. On the vertices of the source graph G built a weighted bipartite graph Gдв = <Х, Y, W(Uдв)>, where W(Uдв) - edge weight, |Uдв| = |U|, |X| = |Y| = |V|, vertex vi (vi ϵ Х) is connected by an edge with a vertex vj (vj ϵ Y), if the arc (vi, vj) is present in the original graph G. In a bipartite graph is built a perfect matching of maximum (minimum) weight. On the edges of the found matching is built the graph. If the constructed graph contains no circuits of length less than the number of vertices in the graph, we found the optimal path. Other-wise, it is necessary to remove all circuits of length less than the number of vertices in the graph, using the formula wпр = w(vi, Гпр(vi)) + w(vj, Гпр(vj)) − w(vi, Гпр(vj)) − w(vj, Гпр(vi)) (1). If the initial graph has the property of symmetry, then (1) takes the form (2): wобпр = min(wпр, wпрr1, wпрr2, wпрr1r2), where wпрr1 = w(Гпр(vi), vi) + w(vj, Гпр(vj)) − w(Гпр(vi), Гпр(vj)) − w(vj, vi), changing direction in the circuit, which belongs to the vertex vi; wпрr2 = w(vi, Гпр(vi)) + w(Гпр(vj), vj) − w(Гпр(vj), Гпр(vi)) − w(vi, vj), changing direction in the circuit, which belongs to the vertex vj; wпрr1r2 = w(Гпр(vi), vi) + w(Гпр(vj), vj) − w(Гпр(vi), vj) − w(Гпр(vj), vi), changing direction in the circuits which belong to the vertices vi and vj. 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.

 

1. Doneckov A.M. Priblizhennoe reshenie zadachi kommivojazhera // EHlektromagnitnye volny i ehlektronnye sistemy. 2016. T. 21. № 7. S. 55−58.
2. Doneckov A.M. Podkhod k resheniju zadachi kommivojazhera // EHlektromagnitnye volny i ehlektronnye sistemy. 2015. T. 20. № 7. S. 57−60.
3. Doneckov A.M. Osnovnye podkhody k proektirovaniju raspisanija uchebnykh zanjatijj VUZa na osnove programmy «Raspisanie» // EHlektromagnitnye volny i ehlektronnye sistemy. 2014. № 10. S. 61−63.
4. Onufrieva T.A., Zajjceva A.A. Primenenie cepejj Markova dlja modelirovanija algoritma dinamicheskojj marshrutizacii // EHlektromagnitnye volny i ehlektronnye sistemy. 2016. T. 21. № 7. S. 63−66.
5. Aliev M.JU., Maksimov A.V., Tatjanich N.V. Metod ocenki chisla otchetov cifrovogo filtra po shirine perekhodnojj zony ego amplitudno-chastotnojj kharakteristiki // EHlektromagnitnye volny i ehlektronnye sistemy. 2016. T. 21. № 7. S. 27−32.
6. Belova I.K., Derjugina E.O., Ermolenko A.V. Metody konturnogo analiza pri formirovanii prostranstva priznakov v zadache nejjrosetevojj identifikacii // EHlektromagnitnye volny i ehlektronnye sistemy. 2016. T. 21. № 7. S. 37−45.
7. Gehri M., Dzhonson D. Vychislitelnye mashiny i trudnoreshaemye zadachi. M.: Mir. 1982. S. 416.
8. Svami M., Tkhulasiraman K. Grafy, seti i algoritmy. M.: Mir. 1984. 455 s.
9. Doneckov A.M. Reshenie zadach perestanovochnogo tipa pri proektirovanii pechatnykh plat // Sredstva svjazi. 1991. № 1. S. 56−59.
10. TSP Test Data. URL = http://www.math.uwaterloo.ca/tsp/data/index.html.
11. Rasstojanija mezhdu gorodami Germanii. URL = http://www.bsi-travel.ru/country/deu/info/deu_distance.
12. Index of /software/TSPLIB95. URL = http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/XML-TSPLIB/instances.
13. Zadacha kommivojazhera. URL = http://mirznanii.com/a/244807/zadacha-kommivoyazhera.