现在的位置: 首页 > 综合 > 正文

动态规划——货郎担问题

2018年08月04日 ⁄ 综合 ⁄ 共 3842字 ⁄ 字号 评论关闭

最近做了个课题=动态规划——货郎担问题实现

在网上找了很就久才找到,下面把代码共享出来供大家参考;

#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;
}
 

抱歉!评论已关闭.