An exact algorithm with linear complexity for a problem of visiting megalopolises |
| |
Authors: | A G Chentsov M Yu Khachai D M Khachai |
| |
Institution: | 1.Krasovskii Institute of Mathematics and Mechanics,Ural Branch of the Russian Academy of Sciences,Yekaterinburg,Russia;2.Ural Federal University,Yekaterinburg,Russia |
| |
Abstract: | A problem of visiting megalopolises with a fixed number of “entrances” and precedence relations defined in a special way is studied. The problem is a natural generalization of the classical traveling salesman problem. For finding an optimal solution, we give a dynamic programming scheme, which is equivalent to a method of finding a shortest path in an appropriate acyclic oriented weighted graph. We justify conditions under which the complexity of the algorithm depends on the number of megalopolises polynomially, in particular, linearly. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|