文档介绍：算法设计与分析大作业
TSP问题
篡法大作业
TSP问题
—问题描述：旅行推销员问题（Travelling Salesman Problem,又 称为旅行商问题、货郎担问题、TSP问题）是一个多局部最优的最优 化问题：有n个城市，一个推销员要从其中某一个城市出发，唯一走 遍所有的城市，再回到他出发的城市，求最短的路线。也即求一个最 短的哈密顿回路。
二算法解决
TSP问题的求解算法有很多：遗传算法，贪心算法，局部搜索，一群 算法。
本文应用分支界限法：
1算法思想：
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式 搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点 一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点 中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点 被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述 结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时
为止。
2算法设计说明：
设求解最大化问题，解向量为X=(xl，…,xn), xi的取值范围为 Si, |Si|=rio在使用分支限界搜索问题的解空间树时，先根据限界 函数估算目标函数的界[down, up],然后从根结点出发，扩展根结点 的rl个孩子结点，从而构成分量xl的rl种可能的取值方式。
对这rl个孩子结点分别估算可能的目标函数bound(xl),其含义： 以该结点为根的子树所有可能的取值不大于bound (xl),即：
bound(xl) Abound(xl, x2) bound(xl,…，xn)
若某孩子结点的目标函数值超出目标函数的下界，则将该孩子结 点丢弃；否则，将该孩子结点保存在待处理结点表PT中。
再取PT表中目标函数极大值结点作为扩展的根结点，重复上述。 直到一个叶子结点时的可行解X=(xl，…,xn),及目标函数值 bound(xl,…，xn)。
三代码
ttinclude <stdio. h>
Sinclude <malloc. h>
#define NoEdge 1000
structMinHeapNode
(
intlcost; //子树费用的下界
int cc; 〃当前费用
intrcost; 〃x[s:n-1]中顶点最小出边费用和
int s; //根节点到当前节点的路径为x[0:s]
int *x; //需要进一步搜索的顶点是//x[s+l:n-1] structMinHeapNode *next;
｝； int n; //图G的顶点数
int **a; //图G的邻接矩阵
//intNoEdge; 〃图G的无边标记
int cc; //当前费用
intbestc; //当前最小费用
MinHeapNode* head = 0; /*堆头*/
MinHeapNode* Iq = 0; /*堆第一个元素*/
MinHeapNode* fq = 0; /*堆最后一个元素*/
intDeleteMin(MinHeapNode*&E)
{
MinHeapNode* tmp 二 NULL;
tmp = fq;
// w = fq->weight ;
E = fq；