【正文】 感謝這些同學和朋友們！ 最后，感謝論文評審委員會的老師們對我的論文給予悉心指點。 同時，論文的順 利完成，離不開同學和朋友的關(guān)心和幫助。他嚴謹、求真、務實的求學態(tài)度給我留下了深 刻 的印象，是我今后工作，學習的榜樣！同時 王老師 淵博的學識、嚴謹?shù)闹螌W態(tài)度、精益求精的工作作風和誨人不倦的高尚師德， 讓我學到了很多我在書本上學不到的知識！ 本文在編寫過程終 參 考了國內(nèi)外大量寶貴的文獻資料，在此謹向文獻資料的作者表示誠摯的敬意和衷心的感謝 !本人還要感謝已經(jīng)畢業(yè) 2020 屆嵌入式實驗室的師兄。 在這里我要特別感謝我的指導老師 王震 老師， 在 我做畢業(yè)設(shè)計的每個階段，從選題到查閱資料，論文提綱的確定，中期論文的 修改，后期 論文格式 調(diào)整等各個環(huán)節(jié)中都給予了我悉心的指導。站在這個人生的轉(zhuǎn)折點上，一種感恩之情油然而生。《盲人導航系統(tǒng)的路徑規(guī)劃研究》。 mangrendaohang=1。k++) printf( %d ,rfid[k])。 for(k=1。 nowid=rfid[0]2。 lujingshengcheng(od,rfid)。 sqliteDB_opt_selectmd(last,lastid)。 extern mangrendaohang。 int od[2]。 [12] 王建宇 、 許震洪 、 周獻中 ：《 基于數(shù)字地圖的多屬性最優(yōu)路徑問題的算法研究 》 [J]， 測繪信息與工程 2020 年第 28卷第 4 期，第 911頁。 [10] 宋久元 、 滕國庫 、 胡麗霞 ：《 路徑規(guī)劃算法的改進及在車載導航中的應用 》 [J]， 計算機與數(shù)字工程 2020 年第 38 卷第 8期，第 9598 頁。 [8] 吳其昌 、 陳天澤 、 粟毅 ：《 基于多目標模糊決策的最佳路徑分析 》 [J]，計算機仿真 2020 年第 22 卷 12期，第 106109 頁、第 123 頁。 [6] ANANY LEVITIN(著 )、 潘彥 (譯 )：《 算法設(shè)計與分析基礎(chǔ) 》 [M]， 清華大學出版社 2020 年，第 246247 頁。 [4] 陳文杰 ：《 路徑選擇中合理路徑集的研究與應用 》 [D]， 中山大學 2020年。 [2] ：《 A note on two problems in connection with graphs》[J]， Numerical Mathematics1959 年第 1 期，第 269271 頁。 （ 2） 對于盲人這一特殊群體，通過矩形算法對搜索區(qū)域的限制，可能會影響路徑的正常搜索 ， 仍 需進一步優(yōu)化 。 并且 該算法也已經(jīng)應用于盲人導航系統(tǒng)中， 取得了良好的效果。 Xx學院 2020屆本科生畢業(yè)設(shè)計 25 6 總結(jié) 與以往的大多是路徑規(guī)劃相比較，本文所述的情況比較特殊 —— 采用的技術(shù)不單是 GPS 技術(shù)，而是采用 RFID 射頻識別技術(shù)；同時本系統(tǒng)的使用者也是存在一定生理缺陷的盲人，路徑的規(guī)劃考慮的問題往往和車載導 航存在差別。而優(yōu)化的 Dijkstra 算法的大大的簡化了搜索的過程，其搜索規(guī)模和搜索時間分別為經(jīng)典 Dijkstra 算法的 %和 %。對于不同的起點和終點進行最短路徑搜索比較，限于篇幅有限，無法一一列出我校任意兩點之間搜索情況，此處只給出了我校 學生一飯?zhí)玫交堑乃阉髑闆r，如下： 圖 51 經(jīng)典 Dijkstra算法的搜素結(jié)果 圖 52 優(yōu)化的 Dijkstra算法的搜索結(jié)果 兩圖中的線條表示響應算法在搜索最短路徑過程中所考慮過的盲道，而其中加粗的線條則為搜索到的最短路徑。 break。(NodeTurn[v].to_node[j]==w))。//決定節(jié)點轉(zhuǎn)彎阻抗 Xx學院 2020屆本科生畢業(yè)設(shè)計 22 if((NodeTurn[v].fr_node[j]==Father[v])amp。jModeTurn[v].num_turn。 turn_imp=0。//尋找 vw 對應路段 if(v==WayInfo[edge].fnode)//決定路段方向阻抗 c[v][v_adj[w]]=WayInfo[edge].ft_imp。w++)。 for(w=0。//判斷節(jié)點是否落在限制矩形內(nèi) if(v=u0)break。amp。amp。amp。 heap_extract_min(A,v)。rn。//由 u0x、 u0y、 v0x、 v0y計算 A、 B、 a、 b、 θ ，構(gòu)造橢圓方程 rectangle_parameter()。i++)//將 v0領(lǐng)接節(jié)點對應權(quán)值插入堆中 heap_insert(A,D[v0_adj[i]])。 for(i=0。final[v0]=TURE。設(shè)起點和終點坐標分別為 (x1， y1)， (x2，y2)，則橢圓方程為： 1/)](c o s)(s i n[/)](s i n)([ c o s 2222 ????????? BbyaxAbyax ???? (412) 式 (412)中 ： )/()a r c ta n ( 1212 xxyy ???? ， 2/)( 21 xxa ?? ， Xx學院 2020屆本科生畢業(yè)設(shè)計 21 2/)( 21 yyb ?? , 2/])()[( 2/1212212 xxyyA ???? ? ， 2/12122122 ]4/])()[([ xxyyAB ????? , 對 x， y分別求偏導，得 2/12222m a x )s i nc o s( ?? BAax ??? , 2/12222m in )s i nc o s( ?? BAax ??? , 2/12222m a x )c o ss i n( ?? BAay ??? , 2/12222m in )c o ss i n( ?? BAay ??? , 這樣 (xmax， ymax)， (xmin， ymin)， (xmax， ymin)， (xmin， ymax)為頂點的矩形就構(gòu)成了搜索區(qū)域 。 表 49節(jié)點坐標表 列名 說明 數(shù)據(jù)類型 約束 Roadno 結(jié)點的 RFID標簽碼 int 主碼 Longitude 結(jié)點的經(jīng)度 double 非空 Latitude 結(jié)點的緯度 double 非空 對于第二個問題，不妨定義比例系數(shù)γ = E / P [12]，其中 P為起始點和目標點兩點間的直線距離， E 則為兩點的大致極限距離。 對此我們有兩個問題需要解決：其一，結(jié)點的坐標從何而來；其二，限制區(qū)域如何求得。其基本思想是求出限制橢圓Xx學院 2020屆本科生畢業(yè)設(shè)計 20 的最小包含矩陣，以此作為限制區(qū)域，既減少了搜索的規(guī)模，又避免了大量復雜的運算。 圖 44樣本元素比值分布圖 矩形算法的利用 然而算法在判斷邊緣結(jié)點是否在橢圓內(nèi)，需要執(zhí)行大 量的乘積和開方計算，同時還需采用更為精細的數(shù)據(jù)結(jié)構(gòu)，存在著一定的局限性。對于不同路況的地區(qū)， 也 可使用不同的 γ 值進行計算。鑒于這個原因，一些學者提出了橢圓限制搜素區(qū)域的最短路徑算法 [3]，以起始點和目標點作為橢圓的兩個焦點，畫出一個合適的橢圓，當判斷是否擴展某個邊緣結(jié)點時，以是否落在橢圓內(nèi)為依據(jù)。由于其全向搜索，依然有大量的冗余計算。 Xx學院 2020屆本科生畢業(yè)設(shè)計 18 對每條道路進行評分計算，得到式 (48)中非數(shù)值因素的模糊綜合函數(shù)值： ? ?? )n,2(),( 32 ?? iCBxxxfu z z iin (49) 對于式 (48)，假設(shè) A=2， B=1；則道路最后權(quán)值為： )),(2()(i s t)x,( 321n21 nxxxfu z zxDxxW ?? ??? (410) 此處，還需要說明，對于每一條道路的評分向量 C，采用數(shù)據(jù)庫建立路況信息表進行描述；并在算法實施過程中，采用多表連接查詢的方式。 ：優(yōu) —— 無紅綠燈。中 —— 人流量＜ 75 或 400＜人流量 ≤550 。 （人流量，單位：人 /h）：優(yōu) —— 100≤ 人流量 ≤250 。中 — — dB＜噪聲 ≤ dB （輕度污染）。 （城市區(qū)域環(huán)境噪聲等級）：優(yōu) —— 噪聲 ≤ dB （好）。中 —— 中級 結(jié)、泥結(jié)碎石或級配碎（爍）石、半整齊石塊路面。 對于每條道路，分別對 其 4 個因素進行評分，得到它的評分向量 C ＝｛ C1，C 2， C 3， C 4｝，對于各個因素評分的標準如下： （城市道路類型）：優(yōu) —— 高級 水泥混凝土、瀝青混凝土、整齊石塊或石條。假設(shè)對多因Xx學院 2020屆本科生畢業(yè)設(shè)計 17 素模糊綜合評價為 fuzz（ x2，?， xn），則得到的評價結(jié)果為 01 之間的一個實數(shù)，而 Fuzz(x2,x3,?,x n)與 Dist（ x1）之間存在著一定的關(guān)系，則可表示為： ),()(i s t/),( 32132 nn xxxfu z zmxDxxxF u z z ?? ?? (45) 將公式 45代入 式 (41)中可得： )(i s t),()(i s t)x,( 1321n21 xDxxxfu z zbmxaDxxW n ???? ?? (46) 提取 Dist（ x1）后， 式 (46)轉(zhuǎn)化為： )),(()(i s t)x,( 321n21 nxxxb m fu z zaxDxxW ?? ??? (47) 采用 A、 B表示系數(shù)常量后，得到多因素情況下道路權(quán)值的確定公式： )),(()(i s t)x,( 321n21 nxxxB fu z zAxDxxW ?? ??? (48) 由公式可知， A、 B 反映了距離 Dist（ x1）與模糊綜合評價 fuzz（ x2，?，xn）對道路權(quán)值 W（ x1， x2，?， xn）的影響 程度， A 的值越大，距離 Dist（ x1）對道路權(quán)值的影響程度就越大， B的值越大，模糊綜合評價 fuzz（ x2，?， xn）對道路權(quán)值的影響程度就越大。而權(quán)值應該看作由 距離因素和其他需要采用模糊隸屬度來表示的盲道因素兩部分組成 [7]： ),()(i s t)x,( 321n21 nxxxb F u z zxaDxxW ?? ?? (41) 式 (41)中， Dist(x1)表示道路距離函數(shù)， Fuzz(x2,x3,?,x n)表示如路面狀況 、周圍 環(huán)境 狀況、道路繁忙狀況、紅綠燈狀況 等非數(shù)值因素的模糊綜合函數(shù)， a、 b為系數(shù)常量，由實際情況調(diào)整。為了得到在多模糊因素下盲人出行的最佳路徑，就不僅需要考慮所有的外在因素，而且需要考慮這些外在因素的相對重要性 ，因此，本系統(tǒng)在考慮多個因素的影響下，提出多因素模糊算法來解決道路權(quán)值確定的問題 。 Xx學院 2020屆本科生畢業(yè)設(shè)計 16 多因素模糊算法 多因素模糊算法的提出 一般情況下，盲人從當前位置到達目標位置所需要考慮到的不只是最短的路徑，而是綜 合考慮多種因素后的最佳路徑。 表 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ù)庫的雙向存儲，仍然可以滿足實際需要，順利完成最短路徑的搜索。再下一個點選取的是頂點 U7， U6下調(diào)到 5+1= 如 46所示。表44 顯示了這些頂點被選取后的表。 Xx學院 2020屆本科生畢業(yè)設(shè)計