货郎担问题的四种实现方法

过货郎担问题的实现

一．源程序文件

// ExamSaleMan.cpp : 定义控制台应用程序的入口点。

/******************************************************************

* 问题：货郎担问题 实现方法：枚举，回溯，动态规划，分支界限法     *

* 联系：[e-mail]                                *

* 工作平台： WinXP，ViaualC++.net                                 *

*******************************************************************/

目录结构 ：有一个基类SalesMan，放置基本数据和操作，然后从salesman继承了4个类，是四种方法的实现，分别是EnumSalesMan,DySalesMan,TrackBakSalesMan,BoundSalesMan，对应的头文件EnumSalesMan。h,DySalesMan.h,TrackBakSalesMan.h,BoundSalesMan.h; Node.h为用到的struct节点

 

/*文件名：ExamSalesMan.cpp  主工程文件*/

#include "stdafx.h"

#include "SalesMan.h"

#include "DySalesMan.h"

#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  货郎担基类头文件  */

#pragma once

#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)

     {   

         cerr<<"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;j

              cout<

         cout<

     }

}

 

/* 文件名：EnumSalesMan.h  枚举法  */

#pragma once

#include "salesman.h"

class EnumSalesMan :

     public SalesMan

{

protected:

     int Cost(vector A); //获取A中保存的路径的路径长度，被被枚举法调用

     void Enumerate(vector A,int i); //利用枚举法求最短的那条路径，被被枚举法调用

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(B,0);

     //把路径打印出来以及路径长度

     cout<<"Enumerate  minValue:"<

     PrintPath();

}

int EnumSalesMan::Cost(vector A)

{

     //获取A中保存的路径的路径长度

     int sum=matrix[0][A[0]];//先求从0到第一个点的距离

     for (unsigned int i=1;i

     {

         sum+=matrix[A[i-1]][A[i]];

     }

     sum+=matrix[A[i-1]][0];//再加上最后一个点到0点的距离

     return sum;

}

void EnumSalesMan::Enumerate(vector A,int i)

//利用枚举法求最短的那条路径,参数A中保存的路径可能经多的点

{

     if (i==A.size()-1)

     {

         if (minValue>Cost(A))

         {

              minValue=Cost(A);

              path=A;

         }

     }

     else

     {

         for (unsigned int k=i;k

         {

              int tmp=A[i];A[i]=A[k];A[k]=tmp;

              Enumerate(A,i+1);

              tmp=A[i];A[i]=A[k];A[k]=tmp;

         }

     }

}

 

/*  文件名：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 (unsigned int 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 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 (unsigned int 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 (unsigned int 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(); 

}

/*  文件名：TrackSalesMan.h  回溯法  */

#pragma once

#include "salesman.h"

 

class TrackBackSalesMan :

     public SalesMan

{

protected:

     vector tmpPath;

     void TrackBack(int k,int  sum);

public: 

     void Travel();

     ~TrackBackSalesMan(){tmpPath.clear();}

};

/*  文件名：TrackSalesMan.cpp  回溯法  */

#include "StdAfx.h"

#include "TrackBackSalesMan.h"

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=sum;

              path=tmpPath;

         }

         return;

     }

     //找下一点,且这一点不能与路径中已有的点重复

     for (int i=1;i

     {

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

     {

         tmpPath.push_back(i);

         TrackBack(i,sum);

         tmpPath.pop_back();

     }

     cout<<"TrackBack minValue:"<

     PrintPath();

    

}

/* 文件名：Node.h  为BoundSalesMan所调用，结点数据结构 */

#pragma once

#include

using namespace std;

struct Node

{

public:

     int num;//约数

     int level; //层级

     int position; //当前结点

     vector > m; //当前结点的矩阵

     vector states; //当前路径状态集

     Node(){};

     Node(int n,int l,int position,vector path,vector > mValue);

     bool operator< (const Node & B)const

     {

          return num>B.num;

     }

};

/* 文件名：Node.cpp  为BoundSalesMan所调用，结点数据结构的实现 */

#include "StdAfx.h"

#include "Node.h"

Node::Node(int n,int l,int pos,vector path,vector > mValue)

{

     num=n;  level=l;  position=pos;  states=path;  m=mValue;

}

/*  文件名：BoundleSalesMan.h   限界函数法   */

#pragma once

#include "salesman.h"

#include

#include "Node.h"

class BoundSalesMan :

     public SalesMan

{

protected:

     int SetIMatrix(int i,int k,vector > & im);//生成第i点的规约矩阵,并返回约数,k点为其父结点

     int Cost(vector A); //获取A中保存的路径的路径长度

     int SimMatrix(vector< vector > & m); //将m规约

public: 

     void Travel();

};

/*  文件名：BoundleSalesMan.cpp   限界函数法   */

#include "StdAfx.h"

#include "BoundSalesMan.h"

#include "Node.h"

#include

#include

int BoundSalesMan::SimMatrix(vector > & m)

//将m规约

{

     int result=0;

     int col=(int)m.size()-1;

     bool boolMax,boolZone;

     //对行进行规约

     for (int i=0;i<=col;i++)

     {

         boolMax=true,

         boolZone=false;

         for (int j=0;j<=col;j++)

         {

              boolMax=boolMax && (m[i][j]==MAXNUM); //所有都是无穷大

              boolZone=boolZone || (m[i][j]==0) ; //是否有一个是0

         }

         if ((boolMax) || (boolZone))

         //如果本行所有数据元素都是无穷大，或者有一个是0，本行已经规约

              continue;//继续下一行

         else  //否则

         {

              //从本行中找到最小的一个值，减去他，约数加上这个值

              int min=m[i][0];

              for (int k=1;k<=col;k++)

              {

                   if (min>m[i][k])

                       min=m[i][k];

              }

              for (int k=0;k<=col;k++)

              {

                   if (m[i][k]!=MAXNUM)  //如果是无穷值，则不变

                    m[i][k]-=min;

              }

              result+=min;

         }

     }   

     //对列进行规约

     for (int i=0;i<=col;i++)

     {

         boolMax=true,

         boolZone=false;

         for (int j=0;j<=col;j++)

         {

              boolMax=boolMax && (m[j][i]==MAXNUM); //所有都是无穷大

              boolZone=boolZone || (m[j][i]==0) ; //是否有一个是0

         }

         if ((boolMax) || (boolZone))

         //如果本列所有数据元素都是无穷大，或者有一个是0，本列已经规约

              continue;//继续下一列

         else  //否则

         {

              //从本列中找到最小的一个值，减去他，约数加上这个值

              int min=m[0][i];

              for (int k=1;k<=col;k++)

              {

                   if (min>m[k][i])

                       min=m[k][i];

              }

              for (int k=0;k<=col;k++)

              {

                   if (m[k][i]!=MAXNUM) //如果是无穷值，则不变

                    m[k][i]-=min;

              }

              result+=min;

         }

     }

     return result;

}

int  BoundSalesMan::SetIMatrix(int i,int k,vector > & im)

//生成第i点的规约矩阵

{

     int cols=im.size()-1;

     //先将k行 和i列置为无穷/

     for (int j=0;j<=cols;j++)

     {

         im[k][j]=MAXNUM;  

         im[j][i]=MAXNUM;

     }

     //再将i行0列置为无穷

     im[i][0]=MAXNUM;  

     //再进行规约，记录规约值

     return SimMatrix(im);

}

 

int BoundSalesMan::Cost(vector A)

//获取A中保存的路径的路径长度

{

     int i=A.size();

     int sum=matrix[0][A[0]];//先求从0到第一个点的距离

     for (unsigned int i=1;i

     {

         sum+=matrix[A[i-1]][A[i]];

     }

     sum+=matrix[A[i-1]][0];//再加上最后一个点到0点的距离

     return sum;

}

void BoundSalesMan::Travel()

{

     path.clear();

     vector > simpleM=matrix; //0点的规约矩阵

     int n0=SimMatrix(simpleM);

     int cols=matrix.size()-1;  

     priority_queue p;

     Node firstNode(n0,0,0,path,simpleM);

     p.push(firstNode);                    //0结点入队列

     Node node;

     while (! p.empty() && p.top().level

     {

         node=p.top();

         p.pop();

         for (int i=1;i<=cols;i++)

         {

              for (int j=0;j

              {

                   if (i==node.states[j]) //路径里有这个点了

                       break;

              }

              if (j

                   continue; 

              //否则

              simpleM=node.m;

              int tmp=node.num;

              tmp+=simpleM[node.position][i];

              tmp+=SetIMatrix(i,node.position ,simpleM); //对第i点的矩阵进行处理                       vector tmpPath=node.states;

              tmpPath.push_back(i);

              Node newNode(tmp,node.level+1,i,tmpPath,simpleM);

              p.push(newNode);

         }

     }

     path=p.top().states;

     cout<<"Bound MinValue:"<

     PrintPath();

}

// stdafx.h : 标准系统包含文件的包含文件，

// 或是常用但不常更改的项目特定的包含文件

#pragma once

#include

#include

二．测试数据及结果

1．

5

999 20  30  10  11

15  999 16  4   2

3   5  999  2   4

19  6   18  999 3

16  4    7  16  999 

对应结果：

2．

4

999 10   15   20

5   999   9   10

6   13    999 12

8   8     9   999

对应结果：

阅读(16310) | 评论(1) | 转发(0) |

0

上一篇：[转载]郎咸平教授清华演讲全文实录

下一篇：Ruby Rails在windows下开发环境的搭建

给主人留下些什么吧！~~

chinaunix网友2008-08-18 13:08:54

我把它原样放到C＋＋中，为什么说我Cannot open include file: 'stdafx.h': No such file or directory出错啊。。。郁闷，不会啊。。。

回复 | 举报

评论热议

请登录后评论。

登录 注册

关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6