47-伪代码详解

5.7.4　伪代码详解

（1）数据结构

我们用二维数组g[][]表示地图的带权邻接矩阵，即如果从顶点i到顶点j有边，就让g[i][j]=<i，j>的权值，否则g[i][j]=∞（无穷大）。x[]记录当前路径，bestx[]记录当前最优路径。

（2）按限界条件搜索求解

t表示当前扩展结点在第t层，cl表示当前已走过的城市所用的路径长度，bestl表示当前找到的最短路径的路径长度。

如果t>n，表示已经到达叶子结点，记录最优值和最优解，返回。否则，扩展节点沿着排列树的某个分支扩展时需要判断约束条件和限界条件，如果满足，则进入深一层继续搜索；如果不满足，则剪掉该分支。搜索到叶子结点时，即找到当前最优解。搜索直到全部的活结点变成死结点为止。

void Traveling(int t)
{
     if(t>n)
     {    //到达叶子结点
          //推销货物的最后一个城市与住地城市有边相连并且路径长度比当前最优值小
          //说明找到了一条更好的路径，记录相关信息
          if(g[x[n]][1]!=INF && (cl+g[x[n]][1]<bestl))
          {
               for(int j=1;j<=n;j++)
                   bestx[j]=x[j];
               bestl=cl+g[x[n]][1];
          }
     }
     else
     {
          //没有到达叶子结点
          for(int j=t; j<=n; j++)
          {
               //搜索扩展结点的所有分支
               //如果第t-1个城市与第j个城市有边相连并且有可能得到更短的路线
               if(g[x[t-1]][x[j]]!=INF&&(cl+g[x[t-1]][x[j]]<bestl))
               {
                    //保存第t个要去的城市编号到x[t]中，进入到第t+1层
                    swap(x[t], x[j]);//交换两个元素的值
                    cl=cl+g[x[t-1]][x[t]];
                    Traveling(t+1); //从第t+1层的扩展结点继续搜索
                    //第t+1层搜索完毕，回溯到第t层
                    cl=cl-g[x[t-1]][x[t]];
                    swap(x[t], x[j]);
               }
          }
     }
}