【文章內(nèi)容簡介】 ： char tem_sql[256]=select * from road where Roadfirst= 。 char tem_sql0[256] = order by roadweight。 char tem_sql1[256] = = Roadthird))。 的關(guān)聯(lián)道路的起點和終點 RFID 碼查詢該道路的完整路徑 ： char tem_sql[256]=select * from road where Roadfirst= 。 char tem_sql0[256] = and roadend= 。 char tem_sql1[256] = 。 連續(xù)的 三個點查詢相關(guān)提示信息 ： 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屆本科生畢業(yè)設(shè)計 10 4 算法設(shè)計 設(shè)計 算法介紹 解決單源最短路徑問題的一個常用算法是 Dijkstra 算法 [24]，它由著名數(shù)學家 1959年提出，是按路徑權(quán)值遞增的次序產(chǎn)生最短路徑的算法；可將本系統(tǒng)所涉及的盲道網(wǎng)絡簡化抽象為賦權(quán)網(wǎng)絡，把盲道抽象為網(wǎng)絡中的邊，并以邊的權(quán)值來表示盲道相關(guān)的參數(shù)，算法產(chǎn)生了賦權(quán)網(wǎng)絡中從指定的結(jié)點到所有其它結(jié)點權(quán)值最小的路徑。其也是目前解決最短路徑問題采用最多的理論基礎(chǔ)。 算法 描述 首先將網(wǎng)絡結(jié)點分為最短距離已確定的結(jié)點集合（簡稱：確定結(jié)點集合）、最短距離未確定的結(jié)點集合（簡稱 ：未確定結(jié)點集合）；在搜索過程中，和確定結(jié)點相連通的未確定結(jié)點稱為邊緣結(jié)點 [4]；算法的過程就是設(shè)置并逐步擴充確定結(jié)點集合。 其次，確定結(jié)點集合在初始狀態(tài)下只包含源結(jié)點，算法不斷從邊緣結(jié)點中搜索距源點路徑權(quán)值最小的未確定結(jié)點加入確定結(jié)點集合，直至找到目標結(jié)點或者所有結(jié)點都加入確定結(jié)點才結(jié)束算法。 最后，算法在將未確定結(jié)點 v加入確定結(jié)點集合時，還需考慮如下問題： 1． 對于任意節(jié)點 u有一對標記 (du， pu)[5]，其中 du是從起源結(jié)點 s到結(jié)點 u的最短路徑權(quán)值（當 s=u 時， du=0）， pu則是從源點 s 到 u的最短路徑中 u點的前驅(qū)結(jié)點。 2． 對于余下的每一個邊緣結(jié)點 u，如果通過權(quán)值為 w(v， u)的邊和 v 相連，當 dv+w(v,u)du時，把 u 的標記 (du， pu)分別更新為 (dv+w(v， u)， v )[6]。Dijkstra 算法就是一個使用貪心選取法則填充表的 for 循環(huán)，偽代碼如下： void Graph：： dijktra（ Vertex s） { for each Vertex v { =INFINITY。//初始化所有節(jié)點 =false。//所有節(jié)點都設(shè)為未知 } =0。//設(shè) 置節(jié)點到本身的距離為 0 for( 。 。) Xx學院 2020屆本科生畢業(yè)設(shè)計 11 { Vertex v=smallest_unknown distance vertex。 if(v==NOT_A_VERTEX) break。 =ture。//當 v點為最小未知節(jié)點時將 v點設(shè)為已知節(jié)點 for each Vertex w adjacent to v if(!) if(+cvw) { //Update w decrease( to +cvw)。 =v。// 更新 du、 pu } } } 從上面 Dijkstra 算法的描述及實現(xiàn)方法可以看出， Dijkstra 的算法實現(xiàn)起來非常容易，由 Dijkstra 算法的偽代碼可以看出， Dijkstra 中存在三個循環(huán)，它的時間復雜度為 0（ n178。），由此也可以看出，頂點越多，循環(huán)次數(shù)越多，計算的時間也將成倍的增長，花費的時間也將急劇增加。 在實際情況中，一個道路網(wǎng)絡的模型規(guī)模往往較大，道路的節(jié)點數(shù)往往數(shù)以萬計，因此，單純地使用 Dijkstra 算法在理論上是可行的，在實際的運用中卻會 出現(xiàn)計算時間過長，出現(xiàn)達不到實時性的效果，所以必須對道路網(wǎng)絡進行優(yōu)化，并對搜索范圍進行限制。 算法 在盲人導航中的實際應用 在實際運用中，道路并沒有固定的方向，所以在數(shù)據(jù)庫的存儲中，對于每條道路都存儲了兩個方向的數(shù)據(jù)，以便于 Dijkstra 算法 的搜索， 圖 41 是一個實際例子 ， 表 41 表示初始配置。第一個選擇頂點為 U1，路徑長為 為 known。領(lǐng)接到 U1的頂點是 U U U4，這三個頂點的項得到調(diào)整，如表 42所示。 Xx學院 2020屆本科生畢業(yè)設(shè)計 12 U 154251841 31 026U 2U 3U 4 U 5U 6 U 7 圖 41 7實際道路 模擬 圖 表 41 初始狀態(tài)下節(jié)點狀態(tài)表 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被聲明為已知后的節(jié)點狀態(tài)表 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被加入確定節(jié)點集合，根據(jù) Dijkstra 算 法，將不再搜索 U1點， 下一步選取 U4并標記為 known。頂點 U U U U U7為領(lǐng)接的頂點，而他們實際上都需要調(diào)整，如表 43 所示。 Xx學院 2020屆本科生畢業(yè)設(shè)計 13 表 43 U4被聲明為已知后的節(jié)點狀態(tài)表 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加入確定節(jié)點集合后， U2是領(lǐng)接的點，但不用進行調(diào)整，因為經(jīng)過 U2的值為 3+10=13 而長為 4的路徑是已知的。同理可得 U U7的值也不變。表44 顯示了這些頂點被選取后的表。 表 44 U U5被聲明為已知后的節(jié)點狀態(tài)表 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，它沒有領(lǐng)接頂點，所以不做調(diào)整。再下一個點選取的是頂點 U7， U6下調(diào)到 5+1= 如 46所示。 表 45 U2被聲明為已知后的節(jié)點狀態(tài)表 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屆本科生畢業(yè)設(shè)計 14 表 46 U7被聲明為已知后的節(jié)點狀態(tài)表 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節(jié)點加入確定節(jié)點完成全部搜索， 節(jié)點 U1到任意節(jié)點的最近距離都可知。 表 47 U6被聲明為已知后的節(jié)點狀態(tài)表 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 算法是用于有向圖的搜索中，可是通過數(shù)據(jù)庫的雙向存儲，仍然可以滿足實際需要，順利完成最短路徑的搜索。 Xx學院 2020屆本科生畢業(yè)設(shè)計 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算法 在實際應用中 的各個階段 利用反證法可以證明，該算法總是可以順利工作，假定存在一個節(jié)點 Ux 有一個最短路徑比它的前驅(qū)節(jié)點 Uy 到它的路徑更短，可得知 Ux 比 Uy 先被設(shè)置為known， 那么就不可能存在 Uy為 Ux的前驅(qū)結(jié)點，由此可以得出，雙方向的道路信息存儲并不影響 Dijastra 算法最短路徑的搜索。 Xx學院 2020屆本科生畢業(yè)設(shè)計 16 多因素模糊算法 多因素模糊算法的提出 一般情況下，盲人從當前位置到達目標位置所需要考慮到的不只是最短的路徑，而是綜 合考慮多種因素后的最佳路徑。對盲人而言，出行還需要考慮到行走道路的 狀況 、周圍環(huán)境的 狀況 、道路繁忙的 狀況 ，甚至紅綠燈的數(shù)量都是一個需要考慮的關(guān)鍵點，這些外在因素都是難以定量的。為了得到在多模糊因素下盲人出行的最佳路徑，就不僅需要考慮所有的外在因素，而且需要考慮這些外在因素的相對重要性 ，因此，本系統(tǒng)在考慮多個因素的影響下，提出多因素模糊算法來解決道路權(quán)值確定的問題 。 多因素模