zhoumao.cpp

换乘次数最少是乘客出行时考虑的首要因素。描述了传 统的Dijkstra 算法,并分析了Dijkstra 算法不适合公交网络最优路径选择的原因。最后根据公交乘客可以步行小段 距离再转车的实际情况,提

/*这是我本次课程设计的第二种算法的实现-------2007年6月25日*/
//由于时间的关系这里就不做异常处理了，你们自己改改。。。。。。//
#include<iostream>
#include<string>
using namespace std;
string zhan[4][12];
int  JDZinFLnum[3];
int  JDZinLLnum[3];

void initdata()
{
zhan[1][7]="海运集团公司站";
zhan[1][6]="霞湖医院站";
zhan[1][5]="市旅游总公司站";
zhan[1][4]="海上城市站";
zhan[1][3]="海滨宾馆站";
zhan[1][2]="潜水运动学校站";
zhan[1][1]="农垦医院站";

zhan[2][1]="东华站";
zhan[2][2]="湾桥站";
zhan[2][3]="农垦医院站";
zhan[2][4]="啤酒厂站";
zhan[2][5]="俱乐部站";
zhan[2][6]="广医附院站";
zhan[2][7]="国贸站";
zhan[2][8]="广州湾站";
zhan[2][9]="建新东路站";
zhan[2][10]="霞湖医院站";
zhan[2][11]="霞山汽车运输总站";

zhan[3][1]="世纪广场站";
zhan[3][2]="人民大道中巴专线";
zhan[3][3]="湛江汽车南站";
zhan[3][4]="建设路站";
zhan[3][5]="广州湾站";
zhan[3][6]="儿童公园站";
zhan[3][7]="海滨宾馆站";
zhan[3][8]="海滨医院站";
}

void findJDZ(int QDZinline,int ZDZinline)
{   for(int i=0;i<3;i++)   
{   JDZinFLnum[i]=NULL;JDZinLLnum[i]=NULL;}
    if(1==QDZinline&&2==ZDZinline)
	{  JDZinFLnum[1]=1;JDZinLLnum[1]= 3;
       JDZinFLnum[2]=6;JDZinLLnum[2]= 10;
	}
    if(1==QDZinline&&3==ZDZinline)
	{  JDZinFLnum[1]=3;JDZinLLnum[1]=7;    }
    if(2==QDZinline&&3==ZDZinline)
	{    JDZinFLnum[1]=8;JDZinLLnum[1]=5;  }
    if(2==QDZinline&&1==ZDZinline)
	{   JDZinFLnum[1]=3;JDZinLLnum[1]=1;
        JDZinFLnum[2]=10;JDZinLLnum[2]=6;   
	}
    if(3==QDZinline&&1==ZDZinline)
	{    JDZinFLnum[1]=7;JDZinLLnum[1]=3; }
    if(3==QDZinline&&2==ZDZinline)
	{   JDZinFLnum[1]=5;JDZinLLnum[1]=8; }
}
main()
{ string  firstzhanname,lastzhanname; // 起点站名和终点站名
//下面定义的变量分别保存起点站的线、终点站的线、起点站在起点线上的编号、重点站在终点线上的编号
int QDZinline[3],ZDZinline[3],QDZinFLnum[3],ZDZinLLnum[3];
int lcount=0,fcount=0; //分别用来标记起点站和终点站所在的线的个数
bool zero=false;   // 标记是否存在0次换乘
initdata();  //初始化所有站点
cout<<"请输入起点站:";
cin>>firstzhanname;
cout<<"请输入终点站:";
cin>>lastzhanname;
int i,j;
for(i=1;i<4;i++)
for(j=1;j<12;j++)
{   if(zhan[i][j]==firstzhanname)
     { fcount++;
	    QDZinline[fcount]=i;QDZinFLnum[fcount]=j;
     }
    if(zhan[i][j]==lastzhanname)
	{  lcount++;
	   ZDZinline[lcount]=i;ZDZinLLnum[lcount]=j;  
	}
}
int fanan=0;// 标记第几条方案
for(i=1;i<=fcount;i++)
 for(j=1;j<=lcount;j++)
  if(QDZinline[i]==ZDZinline[j])
/*输出0次换乘所有方案 */
  {  fanan++;
     cout<<"零次换乘方案["<<fanan<<"]: ";   
	 if(QDZinFLnum[i]>ZDZinLLnum[j])
     { for(int f=QDZinline[i],n=QDZinFLnum[i];n>ZDZinLLnum[j];n--)
	   cout<<zhan[f][n]<<"-->";
       cout<<zhan[f][n]<<endl;
     }
    else
    {  for(int f=QDZinline[i],n=QDZinFLnum[i];n<ZDZinLLnum[j];n++)
	   cout<<zhan[f][n]<<"-->";
       cout<<zhan[f][n]<<endl;
    }
      zero=true;
  }
 
if(!zero)
{/*输出一次换乘所有方案 */
 
  for(i=1;i<=fcount;i++)
  for(j=1;j<=lcount;j++)
  {   int first=QDZinline[i];int last=ZDZinline[j];
	  findJDZ(first, last); //求交点站属于起点线的编号和属于终点线的编号
     for(int m=1;m<3;m++)
	 {     /* 输出起点到交点*/
	      if(QDZinFLnum[i]>JDZinFLnum[m]&&JDZinFLnum[m]!=NULL)
		  {fanan++;
		   cout<<"一次换乘方案["<<fanan<<"]: ";
		   for( int k=QDZinFLnum[i];k>JDZinFLnum[m];k--)
		   cout<<zhan[first][k]<<"-->";
          cout<<zhan[first][k]<<"[交点站]";
		  }
          if(QDZinFLnum[i]<JDZinFLnum[m]&&JDZinFLnum[m]!=NULL)
		  {   fanan++;
		   cout<<"一次换乘方案["<<fanan<<"]: ";
		   for(int k=QDZinFLnum[i] ;k<JDZinFLnum[m];k++)
		   cout<<zhan[first][k]<<"-->";
           cout<<zhan[first][k]<<"[交点站]";
		  }
         /*  输出交点到终点  */
          if( JDZinLLnum[m]>ZDZinLLnum[j]&&JDZinLLnum[m]!=NULL)
		  {for(int k= JDZinLLnum[m] ;k>ZDZinLLnum[j];k--)
		  cout<<zhan[last][k]<<"-->";
          cout<<zhan[last][k]<<endl;
		  }
	      if( JDZinLLnum[m]<ZDZinLLnum[j]&&JDZinLLnum[m]!=NULL)
		  {for(int k= JDZinLLnum[m] ;k<ZDZinLLnum[j];k++)
		   cout<<zhan[last][k]<<"-->";
           cout<<zhan[last][k]<<endl;
		  }
	 }
  }

}

return 0;
}


这两天学习公交换乘算法总结如下：

一、公交换乘问题的算法分为两个步骤：

1、构造并求解换乘矩阵，获得公交换乘方案(即从起点到终点最少换乘次数，及换乘站点)。
有三种实现形式：
①、求得所有节点T矩阵，两个节点直达设为1，两个节点不通或需要换乘设为0；参见《公共交通系统最佳路径算法》
②求得所有线路的T矩阵，两条线路相交设为1，两个线路不相交设为0；参见《基于邻接矩阵的公交换乘算法的研究》(注该算法属于理想化算法)
③通过上述第2个步骤缩小范围，然后用第一个步骤求得精确结果

2、根据最少换乘次数，缩小求解范围，求解起始站点与目标站点间的最短路径，进而得到最佳路径。
最短路径获得有以下几种形式：
①、最简单的实现方法：如果上面1的最少换乘次数、换乘站点都能求解出来，只需要查询换乘次数最少的情况下，所有可能的路径中站点数最少的线路即为所求(前提，假设所有站点之间的距离大致相等)；
②、如果上面1只求出来最少换乘次数，这时需要用算法求最短路径，常用的方法是改进Dijkstra算法，也就是在Diskstra算法中增加了一条判断最少换乘算法的一项；
③、在游戏设计程序中，经常要涉及到最短路径的上述，最常采用的算法是A*算法，参见《游戏地图最短路径搜索设计与实现》和《A算法》
④、K(<=3)条渐次短路径搜索算法，这种算法国外用的比较多，由于该算法比较麻烦，国内研究不太多，参见《K(≤3)条渐次短路径搜索算法的研究》、《一种新的Kth最短路径搜索算法》和《城市轨道交通换乘票务清分模型的研究》(硕士论文)
⑤、蚂蚁算法，参见《一种仿Dijkstra的蚂蚁算法》
其中，②③④⑤步骤中都需要依靠最少换乘次数来达到降低复杂度的目的。

二、上述算法如能得到很好的实现，需要建立一个好的数据结构

1、数据存储形式
我曾问过两个实际搞过这方面的人，一个人采用数组来存储，另外一个所采用链表与数组相结合的方式(即长链表采用数组，其它采用链表的方式)，其实，之所以有上述两个存储形式，主要是因为这两个人算法中侧重面不同，前一个侧重实现最少换乘次数，后一个则侧重最短路径的实现。
2、数据结构存储，可参考《城市公交网络出行路径选择的计算机算法研究》、《基于GIS的标准公交基础信息系统》《基于GIS的公交乘客出行路径选择模型》，考虑到公交换乘，所以通常情况下，把相近的站点(站点名一样但地理位置不同的、站点名不一样但地理位置很接近的)作为公交网络拓扑结构中一个节点。
3、两个节点之间弧段权值的选取(计算最短路径需要)：通常情况下，用两个节点之间的距离代替，但也有人用公交车在这两个节点之间的速度或行车时间来作为权值。下图是沈阳公交网给出来的环路车参数，根据该参数和两个站点之间的距离可以求出站点之间的行车时间(正常)。当然因素考虑的越齐全，越人性化，但是程序上就增加了很多难度， 比如：考虑“等车时间、站点距离、线路的热度(通往商业区)、时间(上班高峰期等)”等因素，这些因素都很难量化，所以，通常情况下，最简单的方法用距基于宽度优先遍历树的公交线路换乘算法
到终点为止，输出起点至终点的出行
路径。