首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号