tracksalesman.cpp

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

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

#include "StdAfx.h"
#include "TrackSalesMan.h"

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

void TrackBackSalesMan::TrackBack(int k,int  sum)

{
     if (tmpPath.size()>1)

         sum+=matrix[tmpPath[tmpPath.size()-2]][k];
     else
         sum+=matrix[0][k]; 

     if (sum>minValue) //界限函数，如果在某一点已经超过当前最小值，则返回

         return;
     if (tmpPath.size()==matrix.size()-1)

     {
         sum+=matrix[tmpPath[tmpPath.size()-1]][0];
         if (sum<minValue)

         {
              minValue=sum;
              path=tmpPath;
         }
         return;
     }
     //找下一点,且这一点不能与路径中已有的点重复
     for (int i=1;i<matrix.size();i++)
     {
         for (int j=0;j<tmpPath.size();j++)
              if (i==tmpPath[j])//看是否i与path中有相同的点

                   break;
         if (j==tmpPath.size())//没有相同的点

         {
              tmpPath.push_back(i);
              TrackBack(i,sum);
              tmpPath.pop_back();
         }        
     }    
}
void TrackBackSalesMan::Travel()
//回溯寻找特定的路径，即为寻找已知解
{
     path.clear(); 
     int sum=0;
     minValue=MAXNUM;
     for (int i=1;i<matrix.size();i++)
     {
         tmpPath.push_back(i);
         TrackBack(i,sum);
         tmpPath.pop_back();
     }
     cout<<"TrackBack minValue:"<<minValue<<endl;

     PrintPath();
     
}

TrackSalesMan::~TrackSalesMan()
{
	tmpPath.clear();

}