货郎担问题程序

/*salesman.h*/
#pragma once
#include
#include
#include
using namespace std;
class SalesMan
{
protected:
enum{MAXNUM=999}; //最大值设为无穷大

vector > matrix; //对应的邻接矩阵
vector path; //记录走过的最小成本路径

int minValue;//最小路径长度

public:
SalesMan();
virtual ~SalesMan(){matrix.clear();path.clear();}

void PrintMatrix(); //打印矩阵值

void PrintPath(); //打印路径

virtual void Travel(){}; //主要寻找路径的函数，将在子类里面实现
};
/*salesman.cpp*/
#include "StdAfx.h"
#include "SalesMan.h"
SalesMan::SalesMan() //构造函数，从文件中读取数值，生成图的邻接矩阵，

{//认为矩阵结点从0开始
fstream fin("in.txt");
if (!fin)
{
cout<<"file open failed!"<return;
}
int n;
fin>>n;
path.resize(n-1); //路径记录中间的那些结点
//从文件里取值
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;jcout<cout<}
}
/*DysalesMan.h*/
#pragma once
#include "salesman.h"
class DySalesMan :
public SalesMan

{
protected:
int g(int i,vector v,vector bv); //计算j最小值得函数，被动态规划法调用

int j(int i,vector v,vector bv); //再走一遍计算过程，以便记路径，被动态规划法调用

public:
void Travel();

};
/*DysalesMan.cpp*/
#include "StdAfx.h"
#include "DySalesMan.h"
int DySalesMan::j(int i,vector v,vector bv)

{
//动态规划中，寻找路径的函数实现，实际上是再走一遍计算过程，但是这次走只按树的一条分支找
bool flag=true;
for (unsigned int j=0;j
{
flag&=bv[j];
}
if (flag)//如果全访问过了，即集合v为空集
{
return i;

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

int cost,node;

for ( j=0;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;
}
ret

urn node;

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

{ //计算最小值的函数的实现
bool flag=true;
for (unsigned int j=0;j
flag&=bv[j];
if (flag)//如果全访问过了，即集合v为空集
return matrix[i][0];

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

int cost,node;

for ( j=0;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 initV;

vector boolV;

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

int cost;
boolV[0]=true;
int node;//记录走过的结点
for (i=1;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<cout<<"dynamic minValue:"<
PrintPath();
}
/*ExamSalesMan.h*/

// ExamSalesMan.h: interface for the ExamSalesMan class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_EXAMSALESMAN_H__B6869D00_D2C5_4D7E_913D_C060A268B38E__INCLUDED_)
#define AFX_EXAMSALESMAN_H__B6869D00_D2C5_4D7E_913D_C060A268B38E__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

class ExamSalesMan
{
public:
ExamSalesMan();
virtual ~ExamSalesMan();

};

#endif // !defined(AFX_EXAMSALESMAN_H__B6869D00_D2C5_4D7E_913D_C060A268B38E__INCLUDED_)
/*ExamSalesMan.cpp*/
#include "StdAfx.h"
#include "SalesMan.h"
#include "DySalesMan.h"
int main()

{
DySalesMan sm;
sm.PrintMatrix();
sm.Travel();
return 0;
}