dysalesman.cpp

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

// DySalesMan.cpp: implementation of the DySalesMan class.
//
//////////////////////////////////////////////////////////////////////
#include "StdAfx.h"
#include "DySalesMan.h"

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

int DySalesMan::j(int i,vector<int> v,vector<bool> bv)

{
     //动态规划中，寻找路径的函数实现，实际上是再走一遍计算过程，但是这次走只按树的一条分支找
     bool flag=true;
     for (unsigned int j=0;j<bv.size();j++)

     {
         flag&=bv[j];
     }
     if (flag)//如果全访问过了，即集合v为空集
     {
         return i;

     }
     int min=MAXNUM;//不妨定义一个最大值作为初始

     int cost,node;

     for (unsigned int j=0;j<v.size();j++)

     {
         if (bv[j]==true)//

              continue;
         bv[j]=true;
         cost=matrix[i][j]+g(j,v,bv);
         if (min>cost)

         {
              //遇到更短的路径
              min=cost;
              node=j;
         }
         bv[j]=false;       
     }    
     return node;

}
int DySalesMan::g(int i,vector<int> v,vector<bool> bv)

{    //计算最小值的函数的实现
     bool flag=true;
     for (unsigned int j=0;j<bv.size();j++)

         flag&=bv[j];
     if (flag)//如果全访问过了，即集合v为空集
         return matrix[i][0];

     int min=MAXNUM;//不妨定义一个最大值作为初始

     int cost,node;

     for (unsigned int j=0;j<v.size();j++)

     {
         if (bv[j]==true)//

              continue;
         bv[j]=true;
         cost=matrix[i][j]+g(j,v,bv);                   
         if (min>cost)

         {
              //遇到更短的路径
              min=cost;
              node=j;
         }
         bv[j]=false;       
     }    
     return min;
}
void DySalesMan::Travel()
//动态规划法求最小成本路径
{
     path.clear();//清空路径 
     vector<int> initV;

     vector<bool> boolV;

     for (unsigned int i=0;i<matrix.size();i++)

     {
         initV.push_back(i);
         boolV.push_back(false);//initV里的元素全未访问过
     }
     int min=999;

     int cost;
     boolV[0]=true;
     int node;//记录走过的结点
     for (unsigned int i=1;i<initV.size();i++)

     {
         boolV[i]=true;
         cost=matrix[0][i]+g(i,initV,boolV);
         if (min>cost)

         {
              min=cost;
              node=i;
         }
         boolV[i]=false;        
     }
     if (min>=MAXNUM)

     {
         cerr<<"无路径到达！";
         exit(0);
     }
     path.push_back(node);
     int nextNode;

     boolV[node]=true;
     nextNode=j(node,initV,boolV);
     while (node!=nextNode)

     {
         path.push_back(nextNode);
         node=nextNode;
         boolV[node]=true;
         nextNode=j(node,initV,boolV);
     }
     cout<<endl;
     cout<<"dynamic minValue:"<<min<<endl;

     PrintPath();  
}