用分支限界法解决TSP问题
2020-11-22 20:41:51 11 举报来了
作者其他创作
大纲/内容
是
next.lb > up？
down = 取距离代价矩阵每行最小的两个元素相加再除以2的值;
孩子结点next是否扩展完毕？
开始
当前的PT表为空？
依次扩展当前结点的所有孩子结点next
up = 用贪心法求得的初始上界；
已经走了n-1个结点？
建立虚拟的解空间排列树
ret = 最优解所对应的路径长度；result[ ] = 最优解路径；
初始化根节点，并将根节点加入到PT表中
否
循环获取城市间的距离value[i][j]
n = 城市个数；
next.lb = getLb(next); //获取当前下界
将孩子结点next加入到PT表中
结束
找到最后一个结点（叶子结点）
建立城市之间的距离代价矩阵
叶子结点的目标函数值在表PT中最小？
收藏
0 条评论
下一页
