1、分支限界 法作业 1. 旅行商问题 设有 n个城市，城市之间道路的长度均大于或等于 0，还可能是（对应城市之间无交通线路）。一个旅行商从某个城市出发，要经过每个城市一次且仅一次，最后回到出发的城市，问他如何走才能使他走的路线最短？ 要求：使用矩阵归约确定限界函数的方法，或者其他方法实现。 分析： 旅行商问题对应的解的元组为 n元组，其中假设第一个城市为 1，则 n元组中未确定的为剩下 n-1个城市，元组为（ 1,x2, ,xn） ,每个 xi的取值为 2, ,n；约束条件为已经经过的城市不能再走，最后回到出发城市。目标 函数是巡回旅行路线长度。 利用矩阵归约的方法 确定限界函数： 限界函数：
2、对任意路线上的结点 d，设 p是其前驱结点，则 f(d) = g(d) + h(d)， 其中， g(d) = f(p) + Cppd， h(d) = rd。 Cppd是在 p点规约后得到的矩阵中 p点到 d点的长度值， rd为 d点可以归约掉的值。 算法 1： (叶子结点进堆 ) Input：图 G； Output：从源点 1出发再回到 1顶点的最短巡回旅行路线。 1. 设定目标函数的限界 down=r1， up= 2. 计算初始结点 1的 f(1)=r1，将初始结点插入最小堆 H; 3. while (H ) 4. 5. 从 H中做 DELETEMIN 的操作，用 p带回相应结点 ; 6.
3、If p是叶子 结点 then 7. 输出当前 最优值 ， 并从叶子结点沿 parent指针输出解， 退出； 8. Else 9. 产生 p的所有 满足约束条件的 后继结点 d(建树，建立指向 parent的指针 ) 并计算 f(d)； 10. if f(d)C2 9. if p为叶子结点 then 10. if 堆 H为空 then 输出没有解 , exit (结束程序 )； 11. else if f(p)down then down=f(p), 删除 H中小于 等于 down的结点； 12. else 13. 产生 p满足约束条件的后继结点 d(建树，保留结点的 parent指针 ) 并计算 f(d)和 g(d) 14. 将 f值大于 down的结点插入最大堆 H中； 15. 16. 17. if flag=false then 输出没有解 ；
