5 017 1 基于導(dǎo)航最優(yōu)路徑算法的設(shè)計(jì)與實(shí)現(xiàn) 學(xué)生姓名： 指導(dǎo)教師： 基于導(dǎo)航最優(yōu)路徑算法 的設(shè)計(jì)與實(shí)現(xiàn) 研究背景與意義 畢設(shè)的研究框架 畢設(shè)的主要工作 主要結(jié)論與展望 5 017 3 研究意義和背景 由于交通擁擠而造成的損失逐年增加，由此出現(xiàn)了建設(shè)智能交通系統(tǒng)的熱潮。人們已經(jīng)逐漸認(rèn)識(shí)到單純依靠增加道路基礎(chǔ)設(shè)施建設(shè)不可能從根本上解決車(chē)輛的快速增長(zhǎng)與交通設(shè)施滯后之間的矛盾，由此便提出了用計(jì)算機(jī)去探索最優(yōu)路徑的概念。 5 017 4 畢設(shè)研究框架 5 017 5 畢設(shè)的主要工作 硬件平臺(tái) ： 通用 軟件平臺(tái) ： 發(fā)語(yǔ)言及開(kāi)發(fā)技術(shù)： 開(kāi)發(fā)語(yǔ)言： C+語(yǔ)言 主要技術(shù)： 圖算法、 A*算法、 時(shí)器技術(shù) 5 017 6 畢設(shè)的主要工作 a、繪圖原理 b、功能實(shí)現(xiàn) 1、背景的繪制 5 017 7 畢設(shè)的主要工作 2、 A*算法搜索最優(yōu)路徑 估值公式表示為： f(n)=g(n)+h(n) 5 017 8 畢設(shè)的主要工作 3、 中頂點(diǎn)作中間頂點(diǎn)的最短路徑長(zhǎng)度 5 017 9 畢設(shè)的主要工作 4、 Gi,j = Gi,j, Gi,k+Gk,j） 5 017 10 畢設(shè)的主要工作 5、動(dòng)態(tài)界面繪制 利用 5 017 11 畢設(shè)的主要工作 6、選取起點(diǎn)、終點(diǎn)， 變更道路連通性 其他功能實(shí)現(xiàn) 5 017 12 畢設(shè)的主要工作 7、算法計(jì)時(shí)功能 實(shí)踐證明按效率高低排序?yàn)椋?A*算法 5 017 13 畢設(shè)的主要工作 節(jié)點(diǎn)數(shù) 搜索速度 A*算法 （ 16 1 2 32 4 4 2 43 7 8 3 62 15 21 5 78 25 47 7 18、三種算法之間的比較 節(jié)點(diǎn)數(shù) A*算法 16 15(100%) 12(80%) 15(100%) 32 31(100%) 25(81%) 29(94%) 43 42(100%) 32(76%) 38(90%) 62 61(100%) 40(66%) 56(92%) 78 77(100%) 45(58%) 71(92%) 017 14 成果展示 最短路徑的搜索 5 017 15 成果展示 界面操作功能 5 017 16 成果展示 算法計(jì)時(shí)功能 5 017 17 錄屏演示 5 017 18 主要結(jié)論與展望 經(jīng)過(guò)本次的畢業(yè)設(shè)計(jì)，使我對(duì)三種最短路徑算法（ A*算法、 了較為深入的了解，并能比較在各種情況下運(yùn)用這三種算法解決路徑搜索問(wèn)題的優(yōu)勢(shì)與劣勢(shì)。 并且也在這次的經(jīng)歷中，讓我對(duì) 圖算法有了較為深入的了解，這對(duì)我今后的職業(yè)生涯也是很有幫助的。 5 017 19 致謝 感謝南昌航空大學(xué)和東軟實(shí)訓(xùn)中心的老師們的悉心指導(dǎo)，讓我在大學(xué)期間學(xué)到了很多的知識(shí)，收獲了很多，也成長(zhǎng)了很多。也感謝劉丹老師對(duì)我畢業(yè)設(shè)計(jì)的指導(dǎo)，使我對(duì)大學(xué)