Visual Studio C#.NET+SQL Server公交信息系统 第6页
第三章 最优路径搜索
3.1 最优路径选择模型的目标函数及约束条件
一般情况下，从起始站点到终止站点，系统可以搜索到几十甚至几百种可能的乘车方案。但对乘客来说，往往只需要其中的一种或几种，这就是说，必须对所有系统搜索到的乘车方案按照乘客所认为的最优目标进行优选排序，然后提供给乘客合理的乘车路线。
在求出的路径中，我们定义 N 为换乘次数，L 为出行距离，T 为出行时间。则我们定义目标函数:
F = Na * Tb * Lc
F越小表示此路径是比较优的路径。a，b，c为三个参数，表示换乘次数，出行距离，出行时间之间的相对重要程度，在此模型中我们选择的首要目标是换乘车次最少，其次是时间最短，第三是距离最短。因此就选择a>b>c，以达到最好的效果。另外还可以根据需要调整参数的值。
根据实际情况或乘客需要，我们要给目标函数加上一定的约束条件，如规定最大换乘次数n，最大出行时间t，则目标函数中要满足N<n，T<t。
3.2 最短路径搜索
在经典的最短路径算法之中，迪杰斯特拉（Dijkstra）算法是最适合用来进行公交网络中最短路径搜索的，所以，在现有的电子地图开发中，该算法被广泛运用。其基本思路是由近及远的寻找起点到其他所有节点的最短路径，当刚好找到所求终点的最短路径的时候，算法终止。
3.2.1 迪杰斯特拉（Dijkstra）算法基本思想
迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路径的算法，其本质是一个贪心算法。基本思想描述如下：
把网中所有顶点分成两组，第一组是已求出最短路径的顶点集合S，S集合的初值是源点（设为V1）;第二组是尚未确定最短路径的顶点集合T（即V - S）,T集合的的初值是除源点之外网中的所有顶点。按路径长度递增的顺序逐个把T集合中的顶点加到S集合中去，直至从源点V1出发可以到达的所有顶点都在S集合中。在这个过程中，总保持从V1到S集合各顶点的最短路径长度不大于从V1到T集合的任何顶点的最短路径长度。另外，每个顶点对应一个距离，S集合中顶点的距离是从V1到此顶点的最短路径长度，T集合中顶点的距离是V1到此顶点的只包括以S中顶点为中间顶点的当前最短路径长度。
3.2.2 迪杰斯特拉（Dijkstra）算法的具体实现
迪杰斯特拉（Dijkstra）算法具体的实现方法如下：
1、 假设用带权的邻接矩阵 cost 来表示有n个顶点的带权有向图。 cost [ i ] [ j ]表示弧< Vi，Vj >上的权值。若< Vi，Vj >不存在，则置cost[ i ] [ j ]为 ∞（可设表示无穷大的值为INT_MAX）。S为已找到从源点V出发的最短路径的终点的集合，它的初始值为V。那么，从V出发到图中其余各顶点（终点）Vi可能达到的最短路径的长度的初值为Dist[ i ] =cost [ V ][ i ]。
2、从T集合中选择w，使得Dist[ w ]=MIN{Dist[ i ] | Vi ∈V - S}，w就是当前求得的一条从V出发的最短路径的终点。从T集合中删除w，并入S集合，令S＝S∪{w}。
3、 修改从V出发到T集合中各顶点的最短路径长度。如果Dist[ w ]+cost[ w ][ i ]< Dist[ i ],则修改Dist[ i ]使Dist[ i ] = Dist [ w ]+cost [ w ][ i ]。
4、重复步骤2、3共 n - 1 次。数组 Dist 记录了从源点到图中其余各顶点的最短路径。
迪杰斯特拉（Dijkstra）算法用C语言描述如下：
#define INT_MAX 32767;
#define SIZE 11;
Dijkstra(int cost[][MAX],int v,int n)/*n为顶点个数，v为源点顶点序号*/
{ /*set为集合s，dist为最短路径长度*/
int set[MAX],dist[MAX];
int i,j,w,sum,ii=0; /*ii为一个判断量，set[i]=1时，表示i是S集合中的点，set[i]=0时，表示i时集合T中的点*/
for (i=0,i<n,i++)
{
dist[i]=cost[v][i];
set[i]=0;
}
set[v]=++ii;
for(i=1;i<n;i++)
{
w=mincost(dist,set,n);
set[w]++ii;
for(j=0;j<n;j++)
if(set[j]==0)
{
sum=dist[w]+cost[w][j];
dist[j]=(dist[j]<sum)?dist[j]:sum;
}
}
}
int mincost(int dist[],int set[],int n)
{
int i,tmp=INF,w=2;
for(i=0;i<n;i++)
if((set[i]==0)&&(dist[i]<tmp))
{
tmp=dist[i];
w=1;
return(w);
}
}
用迪杰斯特拉算法求从起点到终点的最短路径，算法终止于终点离开T集合，加入到S集合时。
3.2.3 对Dijkstra算法的改进
经典Dijkstra算法是基于图论基础上建立的，图的概念在理论领域具有非常广泛的代表性。它几乎可以建立自然界和日常生活中一切相关联的对象的模型。但是正是因为这种广泛性，很多建立在图论基础上的问题处理方法因为需要照顾不同具体领域的运用，而设计的非常复杂，Dijkstra算法就是这样一个例子。为了照顾网络路由算法、车辆导航、邮政策划等等众多领域，Dijkstra算法给出的是一个普遍适用的过程。
当在把Dijkstra算法使用到公交信息系统中时，应当更多的考虑交通道路网络的特殊性，使Dijkstra算法变得简洁，从而缩短路径搜索时间。
在公交网络中，每个节点对应于公交线路中的一个公交站点。在公交网络中每个节点可以直接到达的节点数目总是有限个。所以Dijkstra算法过程中，对已访问节点的下一节点进行计算，更新其他节点的数据的时候，就可以只考虑每个已访问点的邻近节点，而网络拓扑数据集中其他众多的非邻近节点就可以忽略不计。
基于以上的思想，Dijkstra算法可以改进为以下的具体过程：
在原来Dijkstra算法的基础上，增加三个数组：Path[SIZE]、MinDis[SIZE]、InS2[SIZE]。其中，Path[SIZE]用来存放算法中生成的从起点到终点的最短路径的前一点；MinDis[SIZE]用来存放算法中计算出的最短路径的长度；InS2[SIZE]是一个bool数组，用来标记该节点是否已经找到最短路径。
算法的流程图如图3.1所示。
开 始 初 始 化 终点？ 找出已访问标注点的所有未标注邻接点 找出MinDis最小的点，使其InS2=1 由MinDis求出 最短路径长度 结 束 更新Path, MinDis Y N 图3.1 改进的Dijkstra算法流程图
3.3 最少换乘路径搜索
Dijkstra算法的思想是对节点赋以标号，在迭代过程中不断更新标号。每一步的节点标号代表从起点至该点有向路径长度的上界。迭代结束时，节点的标号就是从某点到其余各点最短有向路的准确长度及所经路径。但是在人们日常的乘车过程中，考虑的首要问题是换乘次数最少，然后才是路径最短。如果用Dijkstra算法计算出来的结果可能是:从A站到B站需要转好几次或十几次车才能到达。这样的计算结果是没有什么意义的。因此，能够搜索最少换乘的路径是本系统主要实现的功能。
3.3.1 最少换乘的计算机抽象
基于最少换乘次数的最优路径的思想起源于人们乘车时的一般思路，下面我们逐步把这个思路抽象到计算机的实现中来。
1、搜索是否有直达车。在这一步的实现中，我们只需要搜索经过起始站点的所有线路和经过终止站点的所有线路，找出那些相同的线路，即为直达线路。
2、若没有直达车，则搜索一次换乘是否可达。一般我们在发现没有直达车的时候，会想，从起始站点到达哪个站之后，那个站可以直达终止站点。这一步转化成程序为，从起始站点开始搜索，找出经过它的所有线路，然后通过这些线路，得到起始站点所能够直达的所有站，当然要注意行车方向，同样，也从终止站点开始，找出经过终止站点的所有线路，然后通过这些线路，得出所有能够直达终止站点的那些站，通过对站的ID的匹配，得到中转站，最后再反算出线路。
3、二次或者两次以上的换乘，实现方法与一次换乘方案类似，依然是从站点查找线路，再从线路查找经过站点，再从站点查找经过线路，如此继续下去，直到找到相同站点为止。
3.3.2 广度优先搜索（BFS）算法的基本思想
广度优先搜索（Breadth-First Search）类似于树的按层次遍历。设图 G 的初态是所有顶点均未访问过，在 G 中任选一顶点 V1 为初始出发点，则广度优先搜索的基本思想是：首先访问出发点 V1 ，接着依次访问 V1 的所有邻接点 W1 ,W2 ,……Wt ，然后，再依次访问与 W1 ,W2 ,……Wt 邻接的所有未曾访问过的顶点，依次类推，直至
上一页 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] ... 下一页 >>