计算机毕业论文基于rfid的盲人导航系统路径搜索设计与实现

计算机毕业论文基于rfid的盲人导航系统路径搜索设计与实现内容摘要：

： char tem_sql[256]=select * from road where Roadfirst=。 char tem_sql0[256] = order by roadweight。 char tem_sql1[256] = = Roadthird))。 的关联道路的起点和终点 RFID 码查询该道路的完整路径 ： char tem_sql[256]=select * from road where Roadfirst=。 char tem_sql0[256] = and roadend=。 char tem_sql1[256] =。 连续的 三个点查询相关提示信息 ： char tem_sql[256]=select * from promp where Prompbf=。 char tem_sql0[256] = and Prompno=。 char tem_sql1[256] = and Prompend=。 char tem_sql2[256] =。 息 ： char tem_sql[256]=select * from promp where Promppy=。 sql 拼接成完整的 sqlite 查询语句 范例 ： sql = strcat(tem_sql,name)。 sql = strcat(sql,tem_sql0)。 sql = strcat(tem_sql,name)。 sql = strcat(sql,tem_sql1)。 Xx学院 2020届本科生毕业设计 10 4 算法设计 设计 算法介绍 解决单源最短路径问题的一个常用算法是 Dijkstra 算法 [24]，它由著名数学家 1959年提出，是按路径权值递增的次序产生最短路径的算法；可将本系统所涉及的盲道网络简化抽象为赋权网络，把盲道抽象为网络中的边，并以边的权值来表示盲道相关的参数，算法产生了赋权网络中从指定的结点到所有其它结点权值最小的路径。 其也是目前解决最短路径问题采用最多的理论基础。 算法 描述 首先将网络结点分为最短距离已确定的结点集合（简称：确定结点集合）、最短距离未确定的结点集合（简称 ：未确定结点集合）；在搜索过程中，和确定结点相连通的未确定结点称为边缘结点 [4]；算法的过程就是设置并逐步扩充确定结点集合。 其次，确定结点集合在初始状态下只包含源结点，算法不断从边缘结点中搜索距源点路径权值最小的未确定结点加入确定结点集合，直至找到目标结点或者所有结点都加入确定结点才结束算法。 最后，算法在将未确定结点 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 { =INFINITY。 //初始化所有节点 =false。 //所有节点都设为未知 } =0。 //设 置节点到本身的距离为 0 for(。 ) Xx学院 2020届本科生毕业设计 11 { Vertex v=smallest_unknown distance vertex。 if(v==NOT_A_VERTEX) break。 =ture。 //当 v点为最小未知节点时将 v点设为已知节点 for each Vertex w adjacent to v if(!) if(+cvw) { //Update w decrease( to +cvw)。 =v。 // 更新 du、 pu } } } 从上面 Dijkstra 算法的描述及实现方法可以看出， Dijkstra 的算法实现起来非常容易，由 Dijkstra 算法的伪代码可以看出， Dijkstra 中存在三个循环，它的时间复杂度为 0（ n178。 ），由此也可以看出，顶点越多，循环次数越多，计算的时间也将成倍的增长，花费的时间也将急剧增加。 在实际情况中，一个道路网络的模型规模往往较大，道路的节点数往往数以万计，因此，单纯地使用 Dijkstra 算法在理论上是可行的，在实际的运用中却会 出现计算时间过长，出现达不到实时性的效果，所以必须对道路网络进行优化，并对搜索范围进行限制。 算法 在盲人导航中的实际应用 在实际运用中，道路并没有固定的方向，所以在数据库的存储中，对于每条道路都存储了两个方向的数据，以便于 Dijkstra 算法 的搜索， 图 41 是一个实际例子 ， 表 41 表示初始配置。 第一个选择顶点为 U1，路径长为 为 known。 领接到 U1的顶点是 U U U4，这三个顶点的项得到调整，如表 42所示。 Xx学院 2020届本科生毕业设计 12 U 154251841 31 026U 2U 3U 4 U 5U 6 U 7 图 41 7实际道路 模拟 图 表 41 初始状态下节点状态表 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 表 42 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。 顶点 U U U U U7为领接的顶点，而他们实际上都需要调整，如表 43 所示。 Xx学院 2020届本科生毕业设计 13 表 43 U4被声明为已知后的节点状态表 U Known du pu U1 T 0 0 U2 F 4 U4 U3 F 3 U4 U4 T 1 U1 U5 F 3 U4 U6 F 9 U4 U7 F 5 U4 选择 U U5加入确定节点集合后， U2是领接的点，但不用进行调整，因为经过 U2的值为 3+10=13 而长为 4的路径是已知的。 同理可得 U U7的值也不变。 表44 显示了这些顶点被选取后的表。 表 44 U U5被声明为已知后的节点状态表 U Known du pu U1 T 0 0 U2 F 4 U4 U3 T 3 U4 U4 T 1 U1 U5 T 3 U4 U6 F 9 U4 U7 F 5 U4 由表 44 可知，下一个点是 U2，其值为 4，它没有领接顶点，所以不做调整。 再下一个点选取的是顶点 U7， U6下调到 5+1= 如 46所示。 表 45 U2被声明为已知后的节点状态表 U Known du pu U1 T 0 0 U2 T 4 U4 U3 T 3 U4 U4 T 1 U1 U5 T 3 U4 U6 F 9 U4 U7 F 5 U4 Xx学院 2020届本科生毕业设计 14 表 46 U7被声明为已知后的节点状态表 U Known du pu U1 T 0 0 U2 T 4 U4 U3 T 3 U4 U4 T 1 U1 U5 T 3 U4 U6 F 6 U7 U7 T 5 U4 最后 选取 U6节点加入确定节点完成全部搜索， 节点 U1到任意节点的最近距离都可知。 表 47 U6被声明为已知后的节点状态表 U Known du pu U1 T 0 0 U2 T 4 U4 U3 T 3 U4 U4 T 1 U1 U5 T 3 U4 U6 T 6 U7 U7 T 5 U4 虽然 Dijastra 算法是用于有向图的搜索中，可是通过数据库的双向存储，仍然可以满足实际需要，顺利完成最短路径的搜索。 Xx学院 2020届本科生毕业设计 15 U 154251841 31 026U 2U 3U 4 U 5U 6 U 7U 1 *54251841 31 026U 2U 3U 4 U 5U 6 U 70514∞ ∞∞ 1 2 U 1 *54251841 32U 2U 3U 4 * U 5U 6 U 704139 51 063 1 0604139 5U 1 *54251841 32U 2U 3 *U 4 * U 5 *U 6 U 73 3 4 1 0604139 5U 1 *54251841 32U 2 *U 3 *U 4 * U 5 *U 6 U 731 0604136 53U 1 *54251841 32U 2 *U 3 *U 4 * U 5 *U 6 U 7 * 5 6 1 0604136 5U 1 *54251841 32U 2 *U 3 *U 4 * U 5 *U 6 * U 7 *3 7 图 42 Dijkstra算法 在实际应用中 的各个阶段 利用反证法可以证明，该算法总是可以顺利工作，假定存在一个节点 Ux 有一个最短路径比它的前驱节点 Uy 到它的路径更短，可得知 Ux 比 Uy 先被设置为known， 那么就不可能存在 Uy为 Ux的前驱结点，由此可以得出，双方向的道路信息存储并不影响 Dijastra 算法最短路径的搜索。 Xx学院 2020届本科生毕业设计 16 多因素模糊算法 多因素模糊算法的提出 一般情况下，盲人从当前位置到达目标位置所需要考虑到的不只是最短的路径，而是综 合考虑多种因素后的最佳路径。 对盲人而言，出行还需要考虑到行走道路的 状况 、周围环境的 状况 、道路繁忙的 状况 ，甚至红绿灯的数量都是一个需要考虑的关键点，这些外在因素都是难以定量的。 为了得到在多模糊因素下盲人出行的最佳路径，就不仅需要考虑所有的外在因素，而且需要考虑这些外在因素的相对重要性 ，因此，本系统在考虑多个因素的影响下，提出多因素模糊算法来解决道路权值确定的问题。 多因素模。