18-伪代码详解

6.3.4　伪代码详解

（1）定义结点结构体

struct Node      //定义结点，记录当前结点的解信息
{
     double cl;  //当前已走过的路径长度
     int id;     //景点序号
     int x[N];   //记录当前路径
     Node() {}
     Node(double _cl,int _id)
     {
          cl = _cl;
          id = _id;
     }
};

（2）定义优先队列的优先级

以cl为优先级，cl值越小，越优先。

bool operator <(const Node &a, const Node &b)
{
     return a.cl>b.cl;
}

（3）优先队列式分支限界法搜索函数

//Travelingbfs 为优先队列式分支限界法搜索
double Travelingbfs()
{
     int t;                  //当前处理的景点序号t
     Node livenode,newnode;  //定义当前扩展结点livenode,生成新结点newnode
     priority_queue<Node> q; //创建优先队列，优先级为已经走过的路径长度cl，cl值越小，越优先
     newnode=Node(0,2);      //创建根节点
     for(int i=1;i<=n;i++)
     {
         newnode.x[i]=i;     //初时化根结点的解向量
     }
     q.push(newnode);        //根结点加入优先队列
     while(!q.empty())
     {
          livenode=q.top();  //取出队头元素作为当前扩展结点livenode
          q.pop();           //队头元素出队
          t=livenode.id;     //当前处理的景点序号
          // 搜到倒数第2个结点时个景点的时候不需要往下搜索
          if(t==n)           //立即判断是否更新最优解，
          //例如当前找到一个路径（1243），到达4号结点时，立即判断g[4][3]和g[3][1]是否有边相连，如果有边则判断当前路径长度cl+g[4][3]+g[3][1]<bestl，满足则更新最优值和最优解
          {
              //说明找到了一条更好的路径，记录相关信息
              if(g[livenode.x[n-1]][livenode.x[n]]!=INF&&g[livenode.x[n]][1]!=INF)
                if(livenode.cl+g[livenode.x[n-1]][livenode.x[n]]+g[livenode.x[n]][1]<bestl)
                {
                    bestl=livenode.cl+g[livenode.x[n-1]][livenode.x[n]]+g[livenode.x[n]][1];
                    for(int i=1;i<=n;i++)
                    {
                      bestx[i]=livenode.x[i];//记录最优解
                    }
                 }
               continue;
          }
          //判断当前结点是否满足限界条件，如果不满足不再扩展
         if(livenode.cl>=bestl)
              continue;
          //扩展
          //没有到达叶子结点
          for(int j=t; j<=n; j++)//搜索扩展结点的所有分支
          {
            if(g[livenode.x[t-1]][livenode.x[j]]!=INF)//如果x[t-1]景点与x[j]景点有边相连
               {
                    double cl=livenode.cl+g[livenode.x[t-1]][livenode.x[j]];
                    if(cl<bestl)//有可能得到更短的路线
                    {
                         newnode=Node(cl,t+1);
                         for(int i=1;i<=n;i++)
                         {
                           newnode.x[i]=livenode.x[i];//复制以前的解向量
                         }
                         swap(newnode.x[t], newnode.x[j]);//交换x[t]、x[j]两个元素的值
                         q.push(newnode);//新结点入队
                    }
               }
          }
     }
     return bestl;                       //返回最优值
}