Штучний інтелект

Анотація: У статті пропонується класифікація фундаментальних задач побудови замкнених маршрутів на повних і неповних графах. Розглядаються узагальнення і окремі випадки задачі комівояжера і задач про листоношу. Аналізуються зв'язки між задачами і формулюються їхні математичні моделі.

Ключові слова: транспортна мережа, задача маршрутизації, задача комівояжера, задача про листоношу.

Посилання:

1. Bronshtein E. M/ Deterministic optimization problems of transport logistics / E. M Bronshtein, T. AZayko // Automation and Remote Control. – 2010. – №10. – P. 133–147.
2. Gary M. Computers and Intractability / M. Gary, D. Johnson. – M .: Mir, 1982. – 416 p.
3. Melamed I. I. Traveling Salesman Problem. Problems in the theory / I. I. Melamed, S. I. Sergeev, I. H.Sigal // Automation and Remote Control. – 1989. – № 9. – P. 3–33.
4. Papadimitriou H. Combinatorial optimization. Algorithms and Complexity / H. Papadimitriou, K.Stayglits. – M.: Mir, 1985. – 510 p.
5. Vyalitsin A. A Enumeration of Hamiltonian cycles / A. A Vyalitsin // Discrete mathematics. – 1991. –Volume 3, No. 3. – P. 46–49.
6. Zabinyako G. I Organization of parallel calculations in some problems of discrete optimization / G. I.Zabinyako, E. A. Kotelnikov // Siberian Journal of Computational Mathematics. – 2008. – V. 11, № 4. –P. 414–422.
7. Orlovich Y. L. Hamiltonian cycles in graphs triangulated lattice / Y. L. Orlovich, V. S. Gordon, F.Werner // Reports of the National Academy of Sciences of Belarus. – 2005. – V. 49, № 5. – P. 21–25.
8. Maynika E. Optimization algorithms on networks and graphs / E. Maynika – M .: Mir, 1981. – 323 p.
9. Panov S. A. Models routing in road transport / S. A. Panov. – M .: Transport, 1974. – 152 p.
10. Morozov A. V. Branch and bound method in the Hamiltonian Rural Postman Problem / A. V. Morozov,A. V. Panishev // System Research and Information Technologies. – 2012. – №2. – P. 57–66