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