旅游路线问题的分枝限界算法及其实现

A BRANCH-AND-BOUND IN THE TOURING-PATH PROBLIEM AND ITS COMPUTER IMPLEMENTATION

提出了一个寻求最佳旅游路线的分枝限界算法.该算法利用归约方法求出路线集合的花费下界,沿着具有最小下界的活结点继续扩展,生成一棵状态空间树,求出一条最佳旅游路线.该算法将数据结构与算法紧密结合,研究了许多细节,给出了旅游路线问题的计算机实现.

This paper provies a branch-and-bound algorithm for seeking the beat touring-path. Using the reduction method,this algorithm has found cost low-limits of a set of the paths.As a branch node,the live node having minimum low-limit has been expanded and a state space tree has been generated,The best touring-path has been found.Moreover,combining algorithm with data structure, the auther studied many details about this problem,and gave its computer implementation.