/*ret为问题的解*/ int ret=INF;
q.push(star);
while(!q.empty()) {
node tmp=q.top(); q.pop();
if(tmp.k==n-1) {
/*找最后一个没有走的点*/ int p;
for(int i=1; i<=n; i++) {
if(tmp.visp[i]==0) {
p=i; break; } }
int ans=tmp.sumv+mp[p][tmp.st]+mp[tmp.ed][p]; node judge = q.top();
/*如果当前的路径和比所有的目标函数值都小则跳出*/ if(ans <= judge.lb) {
ret=min(ans,ret); break; }
/*否则继续求其他可能的路径和，并更新上界*/ else {
up = min(up,ans); ret=min(ret,ans); continue; } }
/*当前点可以向下扩展的点入优先级队列*/ node next;
for(int i=1; i<=n; i++) {
if(tmp.visp[i]==0) {
next.st=tmp.st;
/*更新路径和*/
next.sumv=tmp.sumv+mp[tmp.ed][i];
/*更新最后一个点*/ next.ed=i;
/*更新顶点数*/ next.k=tmp.k+1;
/*更新经过的顶点*/
for(int j=1; j<=n; j++) next.visp[j]=tmp.visp[j]; next.visp[i]=1;
/*求目标函数*/ next.lb=get_lb(next);
/*如果大于上界就不加入队列*/ if(next.lb>up) continue; q.push(next); } } }
return ret; }
int main() {
in();
printf(\ return 0; }
四、运行输出结果：
（贴出程序运行完成时的屏幕截图或者输出文件的内容） 这里采用相同的两组数据进行测试。 1、动态规划法
样例1：
样例2：
2、贪心法
样例1：
样例2：
贪心法只能求局部最优解，局部最优解不一定是全局最优解。
3、分支限界法 样例1：
样例2：
五、调试和运行程序过程中产生的问题及采取的措施：
1、动态规划法中输出错误，通过测试数据进行反复验证，并分块输出局部
结果，从而发现问题并解决。
2、贪心法对第二组样例的解不正确，因为局部最优解不一定是全局最优解。 3、分支限界法对于测试样例输出随机值，solve()函数在每次返回的时候结果不一致。通过反复观察代码，发现循环跳出的条件有问题，应该是当前的解小于或等于队列中的目标函数值才跳出。
六、对算法的程序的讨论、分析，改进设想，其它经验教训：
1、动态规划法算法时间复杂度为O(n（oj上的测试样例n最大值为15）
2*2n)，在oj上的测试时间如下：
2、贪心法只能求局部最优解，不一定是全局最优解。所以第二组样例的解不正确。
3、分支限界法的复杂度是根据数据的不同而不同，搜索的节点越少，复杂度越低，跟目标函数的选择有很大关系。目标函数值的计算也会需要一定时间，
2n比如此文章中的目标函数值求解的复杂度是O()。
在oj上的测试时间如下：
在设置节点的时候，用数组标记经过的顶点，visp[i]=1，则说明i点已经经过了，由于
是静态分配空间，所以每次创建新的节点，都会增加空间。所以可以考虑动态分配空间，把不用的节点的空间释放掉。
4、对于顶点少的TSP问题，还可以采用蛮力法。时间复杂度为O(n!)，但实现起来比较简单，这里使用了stl中生成全全排列的函数next_permutation()。
在oj上的测试时间如下：
（测试时限为5000ms）
下面给出蛮力法的代码： #include
scanf(\ for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(i==j) {
mp[i][j]=INF; continue;
}
scanf(\ } } }
int a[22],b[22],c[22]; int solve() {
int ret=99999;
for(int i=1;i<=n;i++) {
a[i]=i; b[i]=i; c[i]=i; } do {
int tmp[22];
for(int i=1;i<=n;i++) {
tmp[i]=b[a[i]]; }
int sum=0;
for(int i=2;i<=n;i++) {
sum+=mp[tmp[i-1]][tmp[i]]; }
sum+=mp[tmp[n]][tmp[1]]; if(sum ret=sum; for(int i=1;i<=n;i++) c[i]=tmp[i]; } }while(next_permutation(a+1,a+1+n)); return ret; } int main() { in(); printf(\ return 0; }