/*文件名：ExamSalesMan.cpp??主工程文件*/
/*
#include?“EnumSalesMan.h“
#include?“TrackBackSalesMan.h“
#include?“BoundSalesMan.h“
int?_tmain（int?argc?_TCHAR*?argv[]）

{
?????DySalesMan?sm;
?????sm.PrintMatrix（）;
?????sm.Travel（）;
?????EnumSalesMan?sm2;
?????sm2.Travel（）;
?????TrackBackSalesMan?sm3;
?????sm3.Travel（）;
?????BoundSalesMan?sm4;
?????sm4.Travel（）;
?????return?0;
}
/*?文件名：SalesMan。H??貨郎擔(dān)基類頭文件??*/

#pragma?once
#include?
#include?
using?namespace?std;
class?SalesMan
{
protected:
?????enum{MAXNUM=999};?//最大值設(shè)為無窮大

?????vector?>??matrix;?//對(duì)應(yīng)的鄰接矩陣
?????vector?path;?//記錄走過的最小成本路徑

?????int?minValue;//最小路徑長度

public:
?????SalesMan（）;
?????virtual?~SalesMan（）{matrix.clear（）;path.clear（）;}

?????void?PrintMatrix（）;?//打印矩陣值

?????void?PrintPath（）;??//打印路徑?

?????virtual?void?Travel（）{};?//主要尋找路徑的函數(shù)，將在子類里面實(shí)現(xiàn)
};
/*?文件名：SalesMan。Cpp?貨郎擔(dān)基類源文件??*/

//#include?“StdAfx.h“
///#include?“SalesMan.h“
SalesMan::SalesMan（）?//構(gòu)造函數(shù)，從文件中讀取數(shù)值，生成圖的鄰接矩陣，

{//認(rèn)為矩陣結(jié)點(diǎn)從0開始
?????fstream?fin（“in.txt“）;
?????if?（!fin）
?????{????
?????????cerr<<“file?open?failed!“<
?????????return;
?????}
?????int?n;
?????fin>>n;
?????path.resize（n-1）;?//路徑記錄中間的那些結(jié)點(diǎn)
?????//從文件里取值
?????for?（int?i=0;i?????{
?????????vector?col;???????

?????????for?（int?j=0;j?????????{
??????????????int?num;

??????????????fin>>num;
??????????????col.push_back（num）;
?????????}????????????
?????????matrix.push_back（col）;
?????}
?????fin.close（）;
}
void?SalesMan::PrintPath（）
{
?????cout<<0<<“\t“;
?????for?（unsigned?int?i=0;i
?????????cout<?????cout<<“0“<}
void?SalesMan::PrintMatrix（）
{
?????int?n=（int）matrix.size（）;
?????for?（int?i=0;i?????{
?????????for?（int?j=0;j??????????????cout<
?????????cout<?????}
}
?
/*?文件名：EnumSalesMan.h??枚舉法??*/

#pragma?once
#include?“salesman.h“
class?EnumSalesMan?:
?????public?SalesMan

{
protected:
?????int?Cost（vector?A）;?//獲取A中保存的路徑的路徑長度，被被枚舉法調(diào)用

?????void?Enumerate（vector?Aint?i）;?//利用枚舉法求最短的那條路徑，被被枚舉法調(diào)用

public:
?????void?Travel（）;

};
/*??文件名：EnumSalesMan.cpp??枚舉法??*/

#include?“StdAfx.h“
#include?“EnumSalesMan.h“
void?EnumSalesMan::Travel（）
{
?????vector?B;?????

?????B.resize（path.size（））;
?????for?（unsigned?int?i=0;i
?????{
?????????B[i]=i+1;
?????}
?????minValue=Cost（B）;//初始化路徑的長度
?????Enumerate（B0）;
?????//把路徑打印出來以及路徑長度
?????cout<<“Enumerate??minValue:“<?????PrintPath（）;
}
int?EnumSalesMan::Cost（vector?A）

{
?????//獲取A中保存的路徑的路徑長度
?????int?sum=matrix[0][A[0]];//先求從0到第一個(gè)點(diǎn)的距離

?????for?（unsigned?int?i=1;i
?????{
?????????sum+=matrix[A[i-1]][A[i]];
?????}
?????sum+=matrix[A[i-1]][0];//再加上最后一個(gè)點(diǎn)到0點(diǎn)的距離
?????return?sum;
}
void?EnumSalesMan::Enumerate（vector?Aint?i）
//利用枚舉法求最短的那條路徑參數(shù)A中保存的路徑可能經(jīng)多的點(diǎn)
{
?????if?（i==A.s

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----

?????文件??????86016??2007-10-24?21:03??貨擔(dān)郎\Debug\vc60.pdb

?????文件??????14266??2007-10-24?21:03??貨擔(dān)郎\貨擔(dān)郎.cpp

?????文件???????4221??2007-10-24?21:02??貨擔(dān)郎\貨擔(dān)郎.dsp

?????文件????????520??2007-10-24?21:02??貨擔(dān)郎\貨擔(dān)郎.dsw

?????文件??????25600??2007-10-24?23:28??貨擔(dān)郎\貨擔(dān)郎.ncb

?????文件??????????0??2007-10-24?21:03??貨擔(dān)郎\貨擔(dān)郎.plg

?????文件??????99840??2007-10-24?21:04??貨擔(dān)郎\貨郎擔(dān).doc

?????目錄??????????0??2009-08-06?09:54??貨擔(dān)郎\Debug

?????目錄??????????0??2009-08-06?09:54??貨擔(dān)郎

-----------?---------??----------?-----??----

???????????????230463????????????????????9