huo.c

货郎担问题和野人过河问题

////////////////////////////////////////////////////////////////////////////////////////////////////////////
//程序说明：                                                                                              //
//           本程序为知识工程－－货郎担问题例程，采用穷举法计算出所有路径的权值，后比较权值选出最佳路径。 //
//           采用穷举法可以得到此问题的精确解。另有一种解法为登山法，也叫贪心法，即在每一个城市选出       //
//           可走路径中权值最小的路径走，此方法得不到精确解,故舍弃。                                      //
//                                                                                                        //
//程序作者： 北京理工大学机电工程学院模式识别与智能系统专业2002级硕S3班                                   //
//                                                                                                        //
//           姓名：尹伟    学号：20202122                                                                 //
//                                                                                                        //
//完成时间： 2002.10.1.                                                                                   //
//                                                                                                        //
////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include"stdio.h"
main()
{
	int i,j,k,t;                        ///循环变量
    int nQuanSum,nMinQuanSum=10000;     ///权值和，最小权值和=10000
	int nBestWay[6];                    ///最佳路径

	///// 权值矩阵，其中行坐标代表起始城市，纵坐标代表目的城市，
	///// 元素值代表从起始城市到目的城市的花费权值，矩阵中的10000代表错误路径
	int nQuanValue[5][5]={10000,7,6,10,13,
		                  7,10000,7,10,10,
						  6,7,10000,5,9,
						  10,10,5,10000,6,
						  13,10,9,6,10000};
	
	///// 01234分别代表ABCDE 五个城市
	int nCity[5]={0,1,2,3,4};

	for(i=1;i<=4;i++)             /////////四重循环搜索权值最小的路径
	{  
	   for(j=1;j<=4;j++)
	   {  if(j!=i)                ////舍弃已走过的城市
	      {  
	         for(k=1;k<=4;k++)
			 {
			  if(k!=i&&k!=j)      ////舍弃已走过的城市
			  {
               for(t=1;t<=4;t++)
			   {
				 if(t!=i&&t!=j&&t!=k)   ////舍弃已走过的城市
				 {  
				  nQuanSum=nQuanValue[0][i]+nQuanValue[i][j]+nQuanValue[j][k]+nQuanValue[k][t]+nQuanValue[t][0];  ////计算权值和
				  printf("0  %d  %d  %d  %d  0       %d\n",nCity[i],nCity[j],nCity[k],nCity[t],nQuanSum);
				  if(nQuanSum<nMinQuanSum)     /////寻找权值和最小的路径权值和，找到后记录下最佳路径
				  {
					  nMinQuanSum=nQuanSum;
                      nBestWay[0]=0;
                      nBestWay[1]=i;
					  nBestWay[2]=j;
					  nBestWay[3]=k;
					  nBestWay[4]=t;
					  nBestWay[5]=0;
				  }
				 }//if(t)
			   }//for(t)
			  }//if(k)	    	   
			 }//for(k)
	   }//if(j)
	   }//for(j)
	}//for(i)

    printf("NOTE: The numbers 0,1,2,3,4,5 stand for the five cities A,B,C,D,E, and the start city is A(0).\n");
	printf("The best way is  %d--->%d--->%d--->%d--->%d--->%d\n",nBestWay[0],nBestWay[1],nBestWay[2],nBestWay[3],nBestWay[4],nBestWay[5]);
    printf("The least quan zhi is  %d\n\n\n",nMinQuanSum);
}