动态规划算法解决最优路径规划

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

#include “stdafx.h“
#include
#include
#include
#include
using namespace std;

//本函数功能为找出最优路径并输出到指定路径文件中
void diamond（int **aint m int n）
{   int b;

  //初始化一个全为0的数组d，用来存放最优路径中杂技演员处在每一行的列号：d[i][j]表示当小丑处在第i行第j个树桩上时，下一步跳上的树桩的列号（行号为i+1）
	int **d = new int*[m];  
    for（int i=0; i        d[i] = new int[n];
	for（int i=0;i		for（int j=0;j			d[i][j]=0;
	

	for（int i=1;i	{
   //考虑边界情况：当处在第0列时，下一步可能跳上的只可能是第0列和第1列，比较第m-i行这两列的值的大小并把较大者与a[m-i-1][0]上的数值相加存放在a[m-i-1][0]中
		if（a[m-i][0]>=a[m-i][1]）{            
			a[m-i-1][0]=a[m-i][0]+a[m-i-1][0];
			d[m-i-1][0]=0;
		}
		else{
		    a[m-i-1][0]=a[m-i][1]+a[m-i-1][0];
			d[m-i-1][0]=1;
		}


		if（m-i			for（int j=2;j				if（a[m-i][j-2]>=a[m-i][j-1]&&a[m-i][j-2]>=a[m-i][j]）{   //若第m-i行的第j-2个树桩上的钻石价值大于第j-1和第j个树桩上的钻石价值（连续的三个树桩）..
				  b=a[m-i][j-2];                                        //..就取第j-2个树桩..
				  d[m-i-1][j-1]=j-2;                                     //..将树桩的位置存放到数组d[m-i-1][j-1]中表示当小丑处在第m-i-1行第j-1个树桩上时，下一步跳上的树桩的列数，以下类似
				}
				else if（a[m-i][j-1]>=a[m-i][j-2]&&a[m-i][j-1]>=a[m-i][j]）{
				  b=a[m-i][j-1];
				  d[m-i-1][j-1]=j-1;
				}
				else{
				   b=a[m-i][j];
				  d[m-i-1][j-1]=j;
				} 
			    a[m-i-1][j-1]=b+a[m-i-1][j-1];
			}
		}
		else{       //与上方的 if（m-i=n，行数大于列数的情况
		//由于行数大于列数，此时除了考虑第0列的边界情况，还要考虑最后一列的边界情况.
		//处在第n-1列时，下一步可能跳上的只可能是第n-1列和第n列，比较第m-i行这两列的值的大小并把较大者与a[m-i-1][n-1]上的数值相加存放在a[m-i-1][n-1]中
			if（a[m-i][n-2]>=a[m-i][n-1]）{    
			   a[m-i-1][n-1]=a[m-i][n-2]+a[m-i-1][n-1];
			   d[m-i-1][n-1]=n-2;
			}
			else{
			    a[m-i-1][n-1]=a[m-i][n-1]+a[m-i-1][n-1];
			    d[m-i-1][n-1]=n-1;
			}

			//以下步骤同行数不大于列数的情况
			for（int j=2;j			   if（a[m-i][j-2]>=a[m-i][j-1]&&a[m-i][j-2]>=a[m-i][j]）{
				  b=a[m-i][j-2];
				  d[m-i-1][j-1]=j-2;
				}
				else if（a[m-i][j-1]>=a[m-i][j-2]&&a[m-i][j-1]>=a[m-i][j]）{
				  b=a[m-i][j-1];
				  d[m-i-1][j-1]=j-1;
				}
				else{
				   b=a[m-i][j];
				  d[m-i-1][j-1]=j;
				} 
			    a[m-i-1][j-1]=b+a[m-i-1][j-1];	
		    }  
		}
	}

	int *e = new int[m];  
	for（int i=0;i			e[i]=0;

	
	ofstream outfile;
	outfile.open（“..\output.txt“）;  //打开输出文件

	outfile<‘<<“1   （开始位置固定）“<<‘
‘;
	for（int i=1;i		e[i]=d[i-1][e[i-1]];
		outfile<‘;  //数组下标从0开始，因此此时要加1再输出到文件中表示位置
	}

	cout<	outfile.close（）;
	
}

void main（）
{
 int data;
 int i=0j=0;
           
 fstream infile;
 infile.open（“..\test.txt“ios::in）;  //打开源文件

 if（!infile）
 {
  cerr<<“File could not open.“;
  return;
 }                             

 int mn;
 infile>>data;    //读入行数
 m=data;
 infile>>data;   //读入列数
 n=data;


 //为原始二维数组a开辟空间
 int **a = new int*[m];  
 for（int i=0; i   a[i] 

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2013-06-05 20:23  algorithm
     目录           0  2013-06-04 21:30  algorithmalgorithm
     文件     9523200  2013-06-05 20:23  algorithmalgorithm.sdf
     文件         894  2013-05-22 14:43  algorithmalgorithm.sln
     文件       10752  2013-06-05 20:23  algorithmalgorithm.suo
     文件        3896  2013-06-04 21:32  algorithmalgorithmalgorithm.cpp
     文件        4403  2013-06-04 21:07  algorithmalgorithmalgorithm.vcxproj
     文件        1313  2013-05-22 14:43  algorithmalgorithmalgorithm.vcxproj.filters
     文件         143  2013-05-22 14:43  algorithmalgorithmalgorithm.vcxproj.user
     目录           0  2013-08-20 21:22  algorithmalgorithmDebug
     文件        1567  2013-05-22 14:43  algorithmalgorithmReadMe.txt
     文件         214  2013-05-22 14:43  algorithmalgorithmstdafx.cpp
     文件         233  2013-05-22 14:43  algorithmalgorithmstdafx.h
     文件         236  2013-05-22 14:43  algorithmalgorithm argetver.h
     文件        1539  2013-05-28 22:06  algorithmalgorithm est.txt
     目录           0  2013-06-04 21:32  algorithmDebug
     文件      684544  2013-06-04 21:31  algorithmDebugalgorithm.exe
     文件     1701256  2013-06-04 21:31  algorithmDebugalgorithm.ilk
     文件     2935808  2013-06-04 21:31  algorithmDebugalgorithm.pdb
     文件      955866  2013-06-04 21:32  algorithmDebugDebug.rar
     目录           0  2013-06-05 19:39  algorithmipch
     目录           0  2013-06-05 19:39  algorithmipchalgorithm-894a63aa
     文件     2359296  2013-06-05 19:39  algorithmipchalgorithm-894a63aaalgorithm-915631f3.ipch
     文件         557  2013-06-04 21:32  algorithmoutput.txt
     文件        1539  2013-05-28 22:06  algorithm est.txt