enumsalesman.cpp

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

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

#include "EnumSalesMan.h"
#include "StdAfx.h"
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

void EnumSalesMan::Travel()
{
     vector<int> B;     

     B.resize(path.size());
     for (unsigned int i=0;i<B.size();i++)

     {
         B[i]=i+1;
     }
     minValue=Cost(B);//初始化路径的长度
     Enumerate(B,0);
     //把路径打印出来以及路径长度
     cout<<"Enumerate  minValue:"<<minValue<<endl; 
     PrintPath();
}

int EnumSalesMan::Cost(vector<int> A)

{
     //获取A中保存的路径的路径长度
     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 EnumSalesMan::Enumerate(vector<int> A,int i)
//利用枚举法求最短的那条路径,参数A中保存的路径可能经多的点
{
     if (i==A.size()-1)

     {
         if (minValue>Cost(A))

         {
              minValue=Cost(A);
              path=A;
         }
     }
     else
     {
         for (unsigned int k=i;k<A.size();k++)
         {
              int tmp=A[i];A[i]=A[k];A[k]=tmp;

              Enumerate(A,i+1);
              tmp=A[i];A[i]=A[k];A[k]=tmp;
         }
     }
}