過貨郎擔(dān)問題的實(shí)現(xiàn)

1、過貨郎擔(dān)問題的實(shí)現(xiàn)一源程序文件/ ExamSaleMan.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。/* 問題：貨郎擔(dān)問題 實(shí)現(xiàn)方法：枚舉，回溯，動態(tài)規(guī)劃，分支界限法     * 聯(lián)系：guojie_flying                               

2、; * 工作平臺： WinXP，ViaualC+.net                                 */目錄結(jié)構(gòu) ：有一個基類SalesMan，放置基本數(shù)據(jù)和操作，然后從salesman繼承了4個類，是四種方法的實(shí)現(xiàn)，分別是EnumSalesMan

3、,DySalesMan,TrackBakSalesMan,BoundSalesMan，對應(yīng)的頭文件EnumSalesMan。h,DySalesMan.h,TrackBakSalesMan.h,BoundSalesMan.h; Node.h為用到的struct節(jié)點(diǎn) /*文件名：ExamSalesMan.cpp  主工程文件*/#include "stdafx.h"#include "SalesMan.h"#include "DySalesMan.h"#include "EnumSalesMan.h"

4、;#include "TrackBackSalesMan.h"#include "BoundSalesMan.h"int _tmain(int argc, _TCHAR* argv)     DySalesMan sm;     sm.PrintMatrix();     sm.Travel();     EnumSalesMan sm2;     sm2.

5、Travel();     TrackBackSalesMan sm3;     sm3.Travel();     BoundSalesMan sm4;     sm4.Travel();     return 0;/* 文件名：SalesMan。H  貨郎擔(dān)基類頭文件  */#pragma once#include <vector>#include <fs

6、tream>using namespace std;class SalesManprotected:     enumMAXNUM=999; /最大值設(shè)為無窮大     vector<vector<int> >  matrix; /對應(yīng)的鄰接矩陣     vector<int> path; /記錄走過的最小成本路徑     int minValue;/最小路徑長度public:

7、0;    SalesMan();     virtual SalesMan()matrix.clear();path.clear();     void PrintMatrix(); /打印矩陣值     void PrintPath();  /打印路徑      virtual void Travel(); /主要尋找路徑的函數(shù)，將在子類里面實(shí)現(xiàn);/* 文件名：SalesMan。Cpp 貨郎擔(dān)

8、基類源文件  */#include "StdAfx.h"#include "SalesMan.h"SalesMan:SalesMan() /構(gòu)造函數(shù)，從文件中讀取數(shù)值，生成圖的鄰接矩陣，/認(rèn)為矩陣結(jié)點(diǎn)從0開始     fstream fin("in.txt");     if (!fin)               

9、   cerr<<"file open failed!"<<endl;         return;          int n;     fin>>n;     path.resize(n-1); /路徑記錄中間的那些結(jié)點(diǎn)     /從文

10、件里取值     for (int i=0;i<n;i+)              vector<int> col;                for (int j=0;j<n;j+)       &

11、#160;               int num;              fin>>num;              col.push_back(num);  

12、60;                           matrix.push_back(col);          fin.close();void SalesMan:PrintPath()     cout<<0<

13、;<"t"     for (unsigned int i=0;i<path.size();i+)         cout<<pathi<<"t"     cout<<"0"<<endl;void SalesMan:PrintMatrix()     int n=(int)ma

14、trix.size();     for (int i=0;i<n;i+)              for (int j=0;j<n;j+)              cout<<matrixij<<"t"    

15、0;     cout<<endl;      /* 文件名：EnumSalesMan.h  枚舉法  */#pragma once#include "salesman.h"class EnumSalesMan :     public SalesManprotected:     int Cost(vector<int> A); /獲取A中保存的路徑的路徑長度，

16、被被枚舉法調(diào)用     void Enumerate(vector<int> A,int i); /利用枚舉法求最短的那條路徑，被被枚舉法調(diào)用public:     void Travel();/*  文件名：EnumSalesMan.cpp  枚舉法  */#include "StdAfx.h"#include "EnumSalesMan.h"void EnumSalesMan:Travel()   &

17、#160; vector<int> B;          B.resize(path.size();     for (unsigned int i=0;i<B.size();i+)              Bi=i+1;          minValue

18、=Cost(B);/初始化路徑的長度     Enumerate(B,0);     /把路徑打印出來以及路徑長度     cout<<"Enumerate  minValue:"<<minValue<<endl;      PrintPath();int EnumSalesMan:Cost(vector<int> A)   &#

19、160; /獲取A中保存的路徑的路徑長度     int sum=matrix0A0;/先求從0到第一個點(diǎn)的距離     for (unsigned int i=1;i<A.size();i+)              sum+=matrixAi-1Ai;          sum+=matrixAi-10;/

20、再加上最后一個點(diǎn)到0點(diǎn)的距離     return sum;void EnumSalesMan:Enumerate(vector<int> A,int i)/利用枚舉法求最短的那條路徑,參數(shù)A中保存的路徑可能經(jīng)多的點(diǎn)     if (i=A.size()-1)              if (minValue>Cost(A)    

21、60;                  minValue=Cost(A);              path=A;                 

22、0; else              for (unsigned int k=i;k<A.size();k+)                       int tmp=Ai;Ai=Ak;Ak=tmp;    

23、0;         Enumerate(A,i+1);              tmp=Ai;Ai=Ak;Ak=tmp;               /*  文件名：DySalesMan。h  動態(tài)規(guī)劃法  */#pragma

24、 once#include "salesman.h"class DySalesMan :     public SalesManprotected:     int g(int i,vector<int> v,vector<bool> bv);  /計算j最小值得函數(shù)，被動態(tài)規(guī)劃法調(diào)用     int j(int i,vector<int> v,vector<bool> bv);  /再走

25、一遍計算過程，以便記路徑，被動態(tài)規(guī)劃法調(diào)用public:     void Travel(); /*  文件名：DySalesMan。cpp  動態(tài)規(guī)劃法  */#include "StdAfx.h"#include "DySalesMan.h"int DySalesMan:j(int i,vector<int> v,vector<bool> bv)     /動態(tài)規(guī)劃中，尋找路徑的函數(shù)實(shí)現(xiàn)，實(shí)際上是再走一遍計算

26、過程，但是這次走只按樹的一條分支找     bool flag=true;     for (unsigned int j=0;j<bv.size();j+)              flag&=bvj;          if (flag)/如果全訪問過了，即集合v為空集  

27、60;           return i;          int min=MAXNUM;/不妨定義一個最大值作為初始     int cost,node;     for (unsigned int j=0;j<v.size();j+)         &

28、#160;    if (bvj=true)/              continue;         bvj=true;         cost=matrixij+g(j,v,bv);       &

29、#160; if (min>cost)                       /遇到更短的路徑              min=cost;         

30、     node=j;                  bvj=false;                     return node;int DySalesMan:g(int i,vector<int> v

31、,vector<bool> bv)    /計算最小值的函數(shù)的實(shí)現(xiàn)     bool flag=true;     for (unsigned int j=0;j<bv.size();j+)         flag&=bvj;     if (flag)/如果全訪問過了，即集合v為空集    

32、0;    return matrixi0;     int min=MAXNUM;/不妨定義一個最大值作為初始     int cost,node;     for (unsigned int j=0;j<v.size();j+)              if (bvj=true)/   

33、           continue;         bvj=true;         cost=matrixij+g(j,v,bv);                

34、60;           if (min>cost)                       /遇到更短的路徑              min=cost;&

35、#160;             node=j;                  bvj=false;                     r

36、eturn min;void DySalesMan:Travel()/動態(tài)規(guī)劃法求最小成本路徑     path.clear();/清空路徑      vector<int> initV;     vector<bool> boolV;     for (unsigned int i=0;i<matrix.size();i+)       

37、0;      initV.push_back(i);         boolV.push_back(false);/initV里的元素全未訪問過          int min=999;     int cost;     boolV0=true;     int

38、 node;/記錄走過的結(jié)點(diǎn)     for (unsigned int i=1;i<initV.size();i+)              boolVi=true;         cost=matrix0i+g(i,initV,boolV);         if

39、(min>cost)                       min=cost;              node=i;           

40、60;      boolVi=false;                  if (min>=MAXNUM)              cerr<<"無路徑到達(dá)！"      &

41、#160;  exit(0);          path.push_back(node);     int nextNode;     boolVnode=true;     nextNode=j(node,initV,boolV);     while (node!=nextNode)      

42、;        path.push_back(nextNode);         node=nextNode;         boolVnode=true;         nextNode=j(node,initV,boolV);     &

43、#160;    cout<<endl;     cout<<"dynamic minValue:"<<min<<endl;     PrintPath();  /*  文件名：TrackSalesMan.h  回溯法  */#pragma once#include "salesman.h" class TrackBackSalesMan :

44、0;    public SalesManprotected:     vector<int> tmpPath;     void TrackBack(int k,int  sum);public:       void Travel();     TrackBackSalesMan()tmpPath.clear();/*  文件名：TrackSalesMan.cp

45、p  回溯法  */#include "StdAfx.h"#include "TrackBackSalesMan.h"void TrackBackSalesMan:TrackBack(int k,int  sum)     if (tmpPath.size()>1)         sum+=matrixtmpPathtmpPath.size()-2k;    

46、 else         sum+=matrix0k;      if (sum>minValue) /界限函數(shù)，如果在某一點(diǎn)已經(jīng)超過當(dāng)前最小值，則返回         return;     if (tmpPath.size()=matrix.size()-1)         

47、     sum+=matrixtmpPathtmpPath.size()-10;         if (sum<minValue)                       minValue=sum;     

48、;         path=tmpPath;                  return;          /找下一點(diǎn),且這一點(diǎn)不能與路徑中已有的點(diǎn)重復(fù)     for (int i=1;i<matrix.size();i+)

49、              for (int j=0;j<tmpPath.size();j+)              if (i=tmpPathj)/看是否i與path中有相同的點(diǎn)             &#

50、160;     break;         if (j=tmpPath.size()/沒有相同的點(diǎn)，                       tmpPath.push_back(i);      

51、60;       TrackBack(i,sum);              tmpPath.pop_back();                          void Trac

52、kBackSalesMan:Travel()/回溯尋找特定的路徑，即為尋找已知解     path.clear();      int sum=0;     minValue=MAXNUM;     for (int i=1;i<matrix.size();i+)              tmpPath.pus

53、h_back(i);         TrackBack(i,sum);         tmpPath.pop_back();          cout<<"TrackBack minValue:"<<minValue<<endl;     PrintPath

54、();     /* 文件名：Node.h  為BoundSalesMan所調(diào)用，結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu) */#pragma once#include <vector>using namespace std;struct Nodepublic:     int num;/約數(shù)     int level; /層級     int position; /當(dāng)前結(jié)點(diǎn)     vector&l

55、t;vector<int> > m; /當(dāng)前結(jié)點(diǎn)的矩陣     vector<int> states; /當(dāng)前路徑狀態(tài)集     Node();     Node(int n,int l,int position,vector<int> path,vector<vector<int> > mValue);     bool operator< (const Node

56、 & B)const               return num>B.num;     ;/* 文件名：Node.cpp  為BoundSalesMan所調(diào)用，結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn) */#include "StdAfx.h"#include "Node.h"Node:Node(int n,int l,int pos,vector<int> path

57、,vector<vector<int> > mValue)     num=n;  level=l;  position=pos;  states=path;  m=mValue;/*  文件名：BoundleSalesMan.h   限界函數(shù)法   */#pragma once#include "salesman.h"#include <vector>#include "Node.h"cl

58、ass BoundSalesMan :     public SalesManprotected:     int SetIMatrix(int i,int k,vector<vector<int> > & im);/生成第i點(diǎn)的規(guī)約矩陣,并返回約數(shù),k點(diǎn)為其父結(jié)點(diǎn)     int Cost(vector<int> A); /獲取A中保存的路徑的路徑長度     int SimMatrix(v

59、ector< vector<int> > & m); /將m規(guī)約public:       void Travel();/*  文件名：BoundleSalesMan.cpp   限界函數(shù)法   */#include "StdAfx.h"#include "BoundSalesMan.h"#include "Node.h"#include <queue>#include <vector&

60、gt;int BoundSalesMan:SimMatrix(vector<vector<int> > & m)/將m規(guī)約     int result=0;     int col=(int)m.size()-1;     bool boolMax,boolZone;     /對行進(jìn)行規(guī)約     for (int i=0;i<=col;i+) 

61、             boolMax=true,         boolZone=false;         for (int j=0;j<=col;j+)              &

62、#160;        boolMax=boolMax && (mij=MAXNUM); /所有都是無窮大              boolZone=boolZone | (mij=0) ; /是否有一個是0               &

63、#160;  if (boolMax) | (boolZone)         /如果本行所有數(shù)據(jù)元素都是無窮大，或者有一個是0，本行已經(jīng)規(guī)約              continue;/繼續(xù)下一行         else  /否則    &#

64、160;                  /從本行中找到最小的一個值，減去他，約數(shù)加上這個值              int min=mi0;              for

65、 (int k=1;k<=col;k+)                                 if (min>mik)            &#

66、160;          min=mik;                            for (int k=0;k<=col;k+)        &

67、#160;                        if (mik!=MAXNUM)  /如果是無窮值，則不變                    mik-=min;

68、60;                           result+=min;                       /對列進(jìn)行規(guī)約 &#

69、160;   for (int i=0;i<=col;i+)              boolMax=true,         boolZone=false;         for (int j=0;j<=col;j+)     &

70、#160;                 boolMax=boolMax && (mji=MAXNUM); /所有都是無窮大              boolZone=boolZone | (mji=0) ; /是否有一個是0      &

71、#160;           if (boolMax) | (boolZone)         /如果本列所有數(shù)據(jù)元素都是無窮大，或者有一個是0，本列已經(jīng)規(guī)約              continue;/繼續(xù)下一列      

72、0;  else  /否則                       /從本列中找到最小的一個值，減去他，約數(shù)加上這個值              int min=m0i;     

73、60;        for (int k=1;k<=col;k+)                                 if (min>mki)    &

74、#160;                  min=mki;                            for (int k=0;k<=col;k+)

75、                                 if (mki!=MAXNUM) /如果是無窮值，則不變              

76、      mki-=min;                            result+=min;                

77、0;  return result;int  BoundSalesMan:SetIMatrix(int i,int k,vector<vector<int> > & im)/生成第i點(diǎn)的規(guī)約矩陣     int cols=im.size()-1;     /先將k行 和i列置為無窮/     for (int j=0;j<=cols;j+)       

78、60;      imkj=MAXNUM;            imji=MAXNUM;          /再將i行0列置為無窮     imi0=MAXNUM;        /再進(jìn)行規(guī)約，記錄規(guī)約值     return

79、SimMatrix(im); int BoundSalesMan:Cost(vector<int> A)/獲取A中保存的路徑的路徑長度     int i=A.size();     int sum=matrix0A0;/先求從0到第一個點(diǎn)的距離     for (unsigned int i=1;i<A.size();i+)           &

80、#160;  sum+=matrixAi-1Ai;          sum+=matrixAi-10;/再加上最后一個點(diǎn)到0點(diǎn)的距離     return sum;void BoundSalesMan:Travel()     path.clear();     vector<vector<int> > simpleM=matrix; /0點(diǎn)的規(guī)約矩陣 

81、;    int n0=SimMatrix(simpleM);     int cols=matrix.size()-1;        priority_queue<Node> p;     Node firstNode(n0,0,0,path,simpleM);      p.push(firstNode);                    /0結(jié)點(diǎn)入隊列     Node node;&