用分支限界法解决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 条评论
回复 删除
下一页