您现在的位置：毕业论文 >> 论文 >> 正文

RFID的盲人导航系统路径搜索设计+物联网路径规划算法第6页

更新时间：2011-10-25: 来源：毕业论文

Dijkstra算法描述首先将网络结点分为最短距离已确定的结点集合（简称：确定结点集合）、最短距离未确定的结点集合（简称：未确定结点集合）；在搜索过程中，和确定结点相连通的未确定结点称为边缘结点[4]；算法的过程就是设置并逐步扩充确定结点集合。毕业论文http://www.youerw.com/
其次，确定结点集合在初始状态下只包含源结点，算法不断从边缘结点中搜索距源点路径权值最小的未确定结点加入确定结点集合，直至找到目标结点或者所有结点都加入确定结点才结束算法。
最后，算法在将未确定结点v加入确定结点集合时，还需考虑如下问题：
1．对于任意节点u有一对标记(du，pu)[5]，其中du是从起源结点s到结点u的最短路径权值（当s=u时，du=0），pu则是从源点s到u的最短路径中u点的前驱结点。
2．对于余下的每一个边缘结点u，如果通过权值为w(v，u)的边和v相连，当dv+w(v,u)<du时，把u的标记(du，pu)分别更新为(dv+w(v，u)，v )[6]。Dijkstra算法就是一个使用贪心选取法则填充表的for循环，伪代码如下：
void Graph：：dijktra（Vertex s）
{
for each Vertex v
{
  v.dist=INFINITY;//初始化所有节点
  v.knowm=false;//所有节点都设为未知
}s.dist=0;//设置节点到本身的距离为0
for( ; ;)原文请+QQ32491.14优,文~论^文"网
{Vertex v=smallest_unknown distance vertex;
if(v==NOT_A_VERTEX)  break;
v.knowm=ture;//当v点为最小未知节点时将v点设为已知节点
for each Vertex w adjacent to v
  if(!w.known)
   if(v.dist+cvw<w.dist)
   {
    //Update w
    decrease(w.dist to v.dist+cvw);
    w.path=v;// 更新du、pu}
从上面Dijkstra算法的描述及实现方法可以看出，Dijkstra的算法实现起来非常容易，由 Dijkstra算法的伪代码可以看出，Dijkstra中存在三个循环，它的时间复杂度为0（n²），由此也可以看出，顶点越多，循环次数越多，计算的时间也将成倍的增长，花费的时间也将急剧增加。
在实际情况中，一个道路网络的模型规模往往较大，道路的节点数往往数以万计，因此，单纯地使用Dijkstra算法在理论上是可行的，在实际的运用中却会出现计算时间过长，出现达不到实时性的效果，所以必须对道路网络进行优化，并对搜索范围进行限制。
4.1.3Dijkstra算法在盲人导航中的实际应用
在实际运用中，道路并没有固定的方向，所以在数据库的存储中，对于每条道路都存储了两个方向的数据，以便于Dijkstra算法的搜索，图4-1是一个实际例子，表4-1表示初始配置。第一个选择顶点为U1，路径长为0.该顶点标记为known。领接到U1的顶点是U2、U3、U4，这三个顶点的项得到调整，如表 4-2所示。图4-1 7实际道路模拟图毕业论文http://www.youerw.com/
表4-1 初始状态下节点状态表
U Known du pu
U1 F 0 0
U2 F ∞ 0
U3 F ∞ 0
U4 F ∞ 0
U5 F ∞ 0
U6 F ∞ 0
U7 F ∞ 0

表4-2 U1被声明为已知后的节点状态表
U Known du pu
U1 T 0 0
U2 F 5 U1
U3 F 4 U1
U4 F 1 U1
U5 F ∞ 0
U6 F ∞ 0
U7 F ∞ 0

U1被加入确定节点集合，根据Dijkstra算法，将不再搜索U1点，下一步选取U4并标记为known。顶点U2、U3、U5、U6、U7为领接的顶点，而他们实际上都需要调整，如表4-3所示。

上一页 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] ... 下一页 >>