用B和B′算法求解TSP问题

Sloving TSP Question Taking Advantage of B and B′ Algorithm

B算法和B′算法都是A 算法的变种 ,TSP (TravellingSalesmanProblem)问题为NP完全问题 ,无一般的多项式复杂度算法 .但采用合适的启发函数后 ,利用B算法或B′算法 ,可在多项式时间内解出 .作者利用C ++的继承功能统一算法形式 ,实现一个完成TSP问题求解的通用搜索算法 .

B and B′ algorithm are deformations of A* algorithm. TSP question is a NP complete question. There is no common algorithm whose time complexity equals to ploynomial. However, we can solve it taking advantage of B and B′ algorithm. An unified algorithm is put forward in this paper.