boundlesalesman.cpp

货郎但问题的VC++实现,供大家参考学习,

// BoundleSalesMan.cpp: implementation of the BoundleSalesMan class.
//
//////////////////////////////////////////////////////////////////////

#include "StdAfx.h"
#include "BoundSalesMan.h"
#include "Node.h"
#include <queue>
#include <vector>

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

int BoundSalesMan::SimMatrix(vector<vector<int> > & m)
//将m规约
{
     int result=0;

     int col=(int)m.size()-1;
     bool boolMax,boolZone;

     //对行进行规约
     for (int i=0;i<=col;i++)
     {
         boolMax=true,
         boolZone=false;
         for (int j=0;j<=col;j++)
         {
              boolMax=boolMax && (m[i][j]==MAXNUM); //所有都是无穷大

              boolZone=boolZone || (m[i][j]==0) ; //是否有一个是0

         }
         if ((boolMax) || (boolZone))

         //如果本行所有数据元素都是无穷大，或者有一个是0，本行已经规约
              continue;//继续下一行
         else  //否则
         {
              //从本行中找到最小的一个值，减去他，约数加上这个值
              int min=m[i][0];

              for (int k=1;k<=col;k++)

              {
                   if (min>m[i][k])

                       min=m[i][k];
              }
              for (int k=0;k<=col;k++)

              {
                   if (m[i][k]!=MAXNUM)  //如果是无穷值，则不变

                    m[i][k]-=min;
              }
              result+=min;
         }
     }    
     //对列进行规约
     for (int i=0;i<=col;i++)
     {
         boolMax=true,
         boolZone=false;
         for (int j=0;j<=col;j++)
         {
              boolMax=boolMax && (m[j][i]==MAXNUM); //所有都是无穷大

              boolZone=boolZone || (m[j][i]==0) ; //是否有一个是0

         }
         if ((boolMax) || (boolZone))

         //如果本列所有数据元素都是无穷大，或者有一个是0，本列已经规约
              continue;//继续下一列
         else  //否则
         {
              //从本列中找到最小的一个值，减去他，约数加上这个值
              int min=m[0][i];

              for (int k=1;k<=col;k++)

              {
                   if (min>m[k][i])

                       min=m[k][i];
              }
              for (int k=0;k<=col;k++)

              {
                   if (m[k][i]!=MAXNUM) //如果是无穷值，则不变

                    m[k][i]-=min;
              }
              result+=min;
         }
     }
     return result;

}
int  BoundSalesMan::SetIMatrix(int i,int k,vector<vector<int> > & im)

//生成第i点的规约矩阵
{
     int cols=im.size()-1;

     //先将k行 和i列置为无穷
     for (int j=0;j<=cols;j++)
     {
         im[k][j]=MAXNUM;   
         im[j][i]=MAXNUM;
     }
     //再将i行0列置为无穷
     im[i][0]=MAXNUM;   
     //再进行规约，记录规约值
     return SimMatrix(im);
}
 
int BoundSalesMan::Cost(vector<int> A)

//获取A中保存的路径的路径长度
{
     int i=A.size();

     int sum=matrix[0][A[0]];//先求从0到第一个点的距离

     for (unsigned int i=1;i<A.size();i++)

     {
         sum+=matrix[A[i-1]][A[i]];
     }
     sum+=matrix[A[i-1]][0];//再加上最后一个点到0点的距离
     return sum;
}
void BoundSalesMan::Travel()
{
     path.clear();
     vector<vector<int> > simpleM=matrix; //0点的规约矩阵
     int n0=SimMatrix(simpleM);

     int cols=matrix.size()-1;   

     priority_queue<Node> p;
     Node firstNode(n0,0,0,path,simpleM); 
     p.push(firstNode);                    //0结点入队列
     Node node;
     while (! p.empty() && p.top().level<cols )

     {
         node=p.top();
         p.pop();
         for (int i=1;i<=cols;i++)
         {
              for (int j=0;j<node.states.size();j++)

              {
                   if (i==node.states[j]) //路径里有这个点了

                       break;
              }
              if (j<node.states.size()) 

                   continue;  
              //否则
              simpleM=node.m;
              int tmp=node.num;

              tmp+=simpleM[node.position][i];
              tmp+=SetIMatrix(i,node.position ,simpleM); //对第i点的矩阵进行处理                       vector<int> tmpPath=node.states;

              tmpPath.push_back(i);
              Node newNode(tmp,node.level+1,i,tmpPath,simpleM);
              p.push(newNode);
         }
     }
     path=p.top().states;
     cout<<"Bound MinValue:"<<Cost(path)<<endl;

     PrintPath();
}