最近做了个课题=动态规划——货郎担问题实现
在网上找了很就久才找到,下面把代码共享出来供大家参考;
#pragma once
#include <vector>
#include <fstream>
using namespace std;
class SalesMan
{
protected:
enum{MAXNUM=999}; //最大值设为无穷大
vector<vector<int> > matrix; //对应的邻接矩阵
vector<int> path; //记录走过的最小成本路径
int minValue;//最小路径长度
public:
SalesMan();
virtual ~SalesMan(){matrix.clear();path.clear();}
void PrintMatrix(); //打印矩阵值
void PrintPath(); //打印路径
virtual void Travel(){}; //主要寻找路径的函数,将在子类里面实现
};
#include "StdAfx.h"
#include "SalesMen.h"
#include "iostream"
SalesMan::SalesMan() //构造函数,从文件中读取数值,生成图的邻接矩阵,
{//认为矩阵结点从0开始
fstream fin("in.txt");
if (!fin)
{
cerr<<"file open failed!"<<endl;
return;
}
int n;
fin>>n;
path.resize(n-1); //路径记录中间的那些结点
//从文件里取值
for (int i=0;i<n;i++)
{
vector<int> col;
for (int j=0;j<n;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<path.size();i++)
cout<<path[i]<<"/t";
cout<<"0"<<endl;
}
void SalesMan::PrintMatrix()
{
int n=(int)matrix.size();
for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
cout<<matrix[i][j]<<"/t";
cout<<endl;
}
}
#pragma once
#include "SalesMen.h"
#include "iostream"
class DySalesMan :
public SalesMan
{
protected:
int g(int i,vector<int> v,vector<bool> bv); //计算j最小值得函数,被动态规划法调用
int j(int i,vector<int> v,vector<bool> bv); //再走一遍计算过程,以便记路径,被动态规划法调用
public:
void Travel();
};
* 文件名:DySalesMan。cpp 动态规划法 */
#include "StdAfx.h"
#include "DySalesMen.h"
int DySalesMan::j(int i,vector<int> v,vector<bool> bv)
{
//动态规划中,寻找路径的函数实现,实际上是再走一遍计算过程,但是这次走只按树的一条分支找
bool flag=true;
for (unsigned int j=0;j<bv.size();j++)
{
flag&=bv[j];
}
if (flag)//如果全访问过了,即集合v为空集
{
return i;
}
int min=MAXNUM;//不妨定义一个最大值作为初始
int cost,node;
for (j=0;j<v.size();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 node;
}
int DySalesMan::g(int i,vector<int> v,vector<bool> bv)
{ //计算最小值的函数的实现
bool flag=true;
for (unsigned int j=0;j<bv.size();j++)
flag&=bv[j];
if (flag)//如果全访问过了,即集合v为空集
return matrix[i][0];
int min=MAXNUM;//不妨定义一个最大值作为初始
int cost,node;
for (j=0;j<v.size();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<int> initV;
vector<bool> boolV;
for (unsigned int i=0;i<matrix.size();i++)
{
initV.push_back(i);
boolV.push_back(false);//initV里的元素全未访问过
}
int min=999;
int cost;
boolV[0]=true;
int node;//记录走过的结点
for (i=1;i<initV.size();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<<endl;
cout<<"dynamic minValue:"<<min<<endl;
PrintPath();
}
// TestSalesMen.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "SalesMen.h"
#include "DySalesMen.h"
int main(int argc, char* argv[])
{
DySalesMan sm;
sm.PrintMatrix();
sm.Travel();
return 0;
}