題-1_100_100.jpg)
基本信息
- 項(xiàng)目名稱：
- 區(qū)域精準(zhǔn)導(dǎo)航系統(tǒng)
- 來(lái)源：
- 第十二屆“挑戰(zhàn)杯”省賽作品
- 小類：
- 信息技術(shù)
- 簡(jiǎn)介：
- 針對(duì)現(xiàn)有GPS導(dǎo)航系統(tǒng)在區(qū)域內(nèi)部精準(zhǔn)導(dǎo)航方面的欠缺，本項(xiàng)目從現(xiàn)實(shí)出發(fā)，實(shí)現(xiàn)了區(qū)域內(nèi)部任意兩個(gè)地點(diǎn)之間的精確導(dǎo)航。同時(shí)考慮到區(qū)域內(nèi)存在“路障”、“階梯”等特殊物體，本項(xiàng)目提供了“人行”和“車行”兩種行走模式。除了可以用文字對(duì)行走過(guò)程加以描述之外，本項(xiàng)目設(shè)計(jì)了專門的圖形用戶界面，可以更加直觀的顯示出行走的路線以及提供其他輔助功能。
- 詳細(xì)介紹：
- 全球定位導(dǎo)航系統(tǒng)（global positioning system）用于陸、海、空三大領(lǐng)域，提供實(shí)時(shí)、全天候和全球性的導(dǎo)航服務(wù)，并用于情報(bào)收集、核爆監(jiān)測(cè)和應(yīng)急通訊等一些軍事目的，在特定領(lǐng)域發(fā)揮著中重要的作用。隨著汽車工業(yè)的蓬勃發(fā)展，衛(wèi)星導(dǎo)航定位的應(yīng)用也日益普及。目前常用的導(dǎo)航系統(tǒng)有美國(guó)的GPS，歐洲的伽利略，中國(guó)的北斗等。以目前使用最廣泛的GPS導(dǎo)航為例，GPS導(dǎo)航的理論背景是通過(guò)把我國(guó)的一些常見(jiàn)地理位置標(biāo)注為“點(diǎn)”，然后把位置與位置之間的路徑定義為“邊”，進(jìn)而把整個(gè)國(guó)家抽象為一個(gè)很大的“圖”，然后利用圖論中的最短路徑和其他相關(guān)算法就能夠計(jì)算出一個(gè)地理位置到另外一個(gè)地理位置之間的最優(yōu)路徑。這些標(biāo)注點(diǎn)在GPS導(dǎo)航模塊中被“同等對(duì)待”，比如說(shuō)一個(gè)占地幾百平方米的酒店和一個(gè)占地幾平方公里的大學(xué)都被抽象為圖中的一個(gè)點(diǎn)，也就是這些標(biāo)注點(diǎn)并不能夠反映他們所代表相應(yīng)地理位置的實(shí)際規(guī)模。這樣做的一個(gè)后果是，當(dāng)目的地是一個(gè)規(guī)模較小的地理位置時(shí)（比如說(shuō)酒店），GPS能夠順利的導(dǎo)航至目的地。但是當(dāng)目的地是一個(gè)規(guī)模較大的區(qū)域內(nèi)部的某個(gè)地理位置時(shí)（比如說(shuō)某個(gè)大學(xué)的物理樓），此時(shí)要到達(dá)目的地只能分為“兩步走”。第一步就是借助GPS導(dǎo)航到達(dá)將此區(qū)域設(shè)置為標(biāo)注點(diǎn)的那個(gè)相應(yīng)地理位置（比如說(shuō)大門）；第二步就是通常借助人工咨詢的方式到達(dá)目的地，也就是說(shuō)此時(shí)GPS不能直接從出發(fā)點(diǎn)導(dǎo)航至目的地。一個(gè)可能的解決方案是將規(guī)模較大的區(qū)域內(nèi)部的所有地理位置都設(shè)置為標(biāo)注點(diǎn)，但是這樣做的后果是標(biāo)注點(diǎn)的數(shù)據(jù)庫(kù)將呈十倍甚至百倍的增加，從而導(dǎo)致計(jì)算數(shù)據(jù)庫(kù)中任意兩個(gè)標(biāo)注點(diǎn)之間的路徑將花費(fèi)很長(zhǎng)的時(shí)間，從而滿足不了導(dǎo)航系統(tǒng)所要求的最基本的“實(shí)時(shí)性”的要求，這也正是目前導(dǎo)航系統(tǒng)將規(guī)模較大區(qū)域只設(shè)置為其外圍的一個(gè)或者幾個(gè)標(biāo)注點(diǎn)的原因。因此該方案只具有理論上的可能性，而不具備任何現(xiàn)實(shí)意義。 本項(xiàng)目的提出正是為了解決上述“兩步走”中的“第二步”，也就是解決規(guī)模較大區(qū)域內(nèi)部任意兩個(gè)位置之間的路徑規(guī)劃問(wèn)題。同時(shí)考慮到區(qū)域內(nèi)部有“路障”和“臺(tái)階”等特殊物體的存在，本項(xiàng)目提供了“人行”、“車行”和兩種行走模式，此外還考慮到某些道路可能因?yàn)榕R時(shí)施工而無(wú)法通行的情況，本項(xiàng)目還將某些路徑標(biāo)注為“臨時(shí)施工”狀態(tài)。因此從本質(zhì)上可以認(rèn)為我們的項(xiàng)目為區(qū)域“專有”或者“特定”導(dǎo)航（region-specific navigation）。這樣我們的項(xiàng)目就解決了此區(qū)域內(nèi)的“路徑詢問(wèn)”這一重大需求問(wèn)題，比如當(dāng)區(qū)域?yàn)橐粋€(gè)大學(xué)時(shí)，本項(xiàng)目可以解決每年開(kāi)學(xué)期間大量新生和家長(zhǎng)的問(wèn)路咨詢問(wèn)題；而當(dāng)此區(qū)域?yàn)橐粋€(gè)風(fēng)景區(qū)時(shí)，本項(xiàng)目可以解決旅游高峰時(shí)期大量游客需要的景點(diǎn)路徑咨詢問(wèn)題。除了提供最基本的路徑導(dǎo)航之外，為了給區(qū)域內(nèi)部人員提供更多便利，本項(xiàng)目還提供了基本設(shè)施的使用查詢，例如學(xué)校內(nèi)部自動(dòng)提款機(jī)的位置查詢和手機(jī)營(yíng)業(yè)廳的查詢等。因此本項(xiàng)目具有較強(qiáng)的實(shí)用性和推廣性。 在程序具體實(shí)現(xiàn)的過(guò)程中，首先要確定尋徑算法的正確性以及數(shù)據(jù)錄入的準(zhǔn)確性，保證輸出的一定是兩點(diǎn)之間的最優(yōu)路徑；其次要考慮尋徑算法的時(shí)間復(fù)雜度，以及地名的查找速度，避免給用戶造成過(guò)長(zhǎng)的等待時(shí)間；第三要準(zhǔn)確生動(dòng)，圖文并茂的描繪出路徑信息，避免信息含糊誤導(dǎo)行人；第四要考慮程序的可擴(kuò)展性和可移植性，盡量使程序能夠較廣泛的應(yīng)用于相關(guān)領(lǐng)域；最后程序要擁有友好的用戶界面，用戶通過(guò)最基本、最簡(jiǎn)單的操作，就能獲得導(dǎo)航信息。 從上述需求出發(fā)，本項(xiàng)目基于基本的圖論算法，并輔以幾種數(shù)據(jù)結(jié)構(gòu)的支持，從而實(shí)現(xiàn)點(diǎn)對(duì)點(diǎn)的精確導(dǎo)航。其中核心算法為Dijkstra算法，用于計(jì)算出起始點(diǎn)到圖中所有點(diǎn)的距離，其性能直接與點(diǎn)集的表示方法有關(guān)，為了優(yōu)化尋徑算法，本項(xiàng)目利用優(yōu)先級(jí)隊(duì)列來(lái)改進(jìn)尋徑算法，在保證準(zhǔn)確性的前提下實(shí)現(xiàn)圖的高效搜索。在實(shí)地考察的過(guò)程中，發(fā)現(xiàn)大部分的區(qū)域在抽象以后都是稀疏圖，為了保證算法效率，程序采用鄰接表結(jié)構(gòu)來(lái)保存圖中信息。由于程序最終的輸出并非僅僅是數(shù)據(jù)結(jié)構(gòu)的圖中的路徑信息，本文又對(duì)算法計(jì)算出的路徑信息加以潤(rùn)色，同時(shí)結(jié)合圖中邊的通行屬性（即該邊是否能通車，以及是否正在施工）篩選出最優(yōu)路徑。為了節(jié)約存儲(chǔ)空間，有關(guān)點(diǎn)的所有信息（如點(diǎn)的坐標(biāo)，點(diǎn)的名稱等）都存儲(chǔ)在同一個(gè)數(shù)組之中，目的是便于維護(hù)和節(jié)省空間，邊信息也做類似處理，目的相同。程序內(nèi)部各數(shù)據(jù)結(jié)構(gòu)只需相互傳遞點(diǎn)的id號(hào)，因?yàn)橥ㄟ^(guò)id號(hào)就可以快速索引到對(duì)應(yīng)該id的點(diǎn)的所有信息，這樣做使得程序內(nèi)部的信息交互更為簡(jiǎn)潔。為實(shí)現(xiàn)地點(diǎn)名稱到結(jié)點(diǎn)id的快速映射，本項(xiàng)目采用高效哈希算法，將映射操作的時(shí)間復(fù)雜度控制在O（1），并解決了“一地對(duì)多名”的問(wèn)題。為了準(zhǔn)確的描述導(dǎo)航信息，除了提供導(dǎo)航圖之外，本項(xiàng)目還為用戶提供兩點(diǎn)之間的具體行走方法，并且不要求用戶在每次行走時(shí)都判斷東、南、西、北地理方位，而是根據(jù)用戶當(dāng)前的朝向自動(dòng)確定下一次的轉(zhuǎn)向，并以更易確定的前、后、左、右等邏輯方位來(lái)描述具體的轉(zhuǎn)向方位。描述導(dǎo)航文字信息的難點(diǎn)主要在于：點(diǎn)與點(diǎn)之間的地理方向（東南西北）是固定不變的，而其邏輯方向是隨著行人朝向的不同而變化的，程序需要針對(duì)行人的朝向，確定下一步的邏輯方向（前后左右）。為了克服這一問(wèn)題，本文提出了一種解決方案，其機(jī)理是利用數(shù)組模擬羅盤，從而模擬行人的行走過(guò)程，根據(jù)行人的行走確定下一步的邏輯方位。繪制導(dǎo)航圖的難點(diǎn)在于：不同區(qū)域的數(shù)據(jù)文件所基于的坐標(biāo)系可能不同，程序應(yīng)能根據(jù)整張圖的邊界點(diǎn)的橫縱坐標(biāo)來(lái)確定圖像實(shí)際顯示的大小，該問(wèn)題在本項(xiàng)目中已用特定算法解決。為符合軟件工程的基本思想，本項(xiàng)目嚴(yán)格按照模塊化程序設(shè)計(jì)的標(biāo)準(zhǔn)，對(duì)程序模塊進(jìn)行了嚴(yán)格的分類。本項(xiàng)目可劃分為計(jì)算部分，界面部分，和接口模塊。其中，計(jì)算部分又可劃分為四大模塊，其主要功能是實(shí)現(xiàn)主要數(shù)據(jù)結(jié)構(gòu)和基本算法，并利用算法獲得準(zhǔn)確的導(dǎo)航信息，計(jì)算部分和界面部分又以接口模塊連接起來(lái)。將計(jì)算部分與界面部分分離是為了獲得更好的擴(kuò)展性，即使是將該項(xiàng)目移植到其它平臺(tái)上，也只需重寫界面部分，并將接口稍加修改，而計(jì)算部分可以被完全復(fù)用，本項(xiàng)目的數(shù)據(jù)文件模塊、圖形顯示模塊之間和接口模塊之間相互獨(dú)立，滿足了模型-視圖-控制器設(shè)計(jì)模式，具有良好的可擴(kuò)展性，比如說(shuō)本項(xiàng)目以青島大學(xué)為例，可以實(shí)現(xiàn)青島大學(xué)任意兩個(gè)位置之間的路徑規(guī)劃。當(dāng)數(shù)據(jù)文件模塊更改為海爾工業(yè)園中的相應(yīng)位置信息時(shí)，就可以實(shí)現(xiàn)海爾工業(yè)園區(qū)中任意兩個(gè)位置之間的導(dǎo)航。在保證程序正確與高效運(yùn)行的同時(shí)，還要盡可能的節(jié)約存儲(chǔ)資源，以便程序可以適應(yīng)嵌入式工程所需要的苛刻條件。故在本項(xiàng)目中，最要求效率的計(jì)算部分采用C語(yǔ)言編寫，而對(duì)效率要求較低的界面部分用MFC實(shí)現(xiàn)，平衡了程序運(yùn)行速度和界面的友好性。 為檢測(cè)上述功能，本項(xiàng)目基于實(shí)際數(shù)據(jù)進(jìn)行了大量測(cè)試，已能夠準(zhǔn)確的描述導(dǎo)航信息。對(duì)于給定的數(shù)據(jù)文件，程序能準(zhǔn)確的將各點(diǎn)位置繪制在導(dǎo)航屏上，并以各邊所具備的不同屬性將邊進(jìn)行分類，然后以不同的顏色和線條將導(dǎo)航屏上的相應(yīng)點(diǎn)正確連接起來(lái)。根據(jù)本項(xiàng)目中程序所提供的幫助信息，用戶看圖即知各路徑的屬性，以及該區(qū)域中各地點(diǎn)的大致分布，再結(jié)合程序給出的導(dǎo)航信息，便可輕松的獲知到達(dá)目的地點(diǎn)的詳細(xì)走法。除了實(shí)現(xiàn)基本的點(diǎn)對(duì)點(diǎn)導(dǎo)航功能之外，本項(xiàng)目也已實(shí)現(xiàn)對(duì)基礎(chǔ)設(shè)施的查找功能，程序能夠根據(jù)用戶當(dāng)前所在的地點(diǎn)，自動(dòng)從若干基礎(chǔ)設(shè)施中選擇用戶最易到達(dá)的一個(gè)，同時(shí)輸出從當(dāng)前地點(diǎn)到該基礎(chǔ)設(shè)施的導(dǎo)航路徑及詳細(xì)走法。其中，查找基礎(chǔ)設(shè)施的導(dǎo)航路徑顏色和進(jìn)行普通導(dǎo)航時(shí)不同，目的是讓用戶對(duì)當(dāng)前進(jìn)行的是何種導(dǎo)航一目了然，所在地點(diǎn)和目的地點(diǎn)被用特殊顏色標(biāo)注，并被在圖上放大，以便用戶在圖中迅速定位。此外，用戶可以根據(jù)自己的實(shí)際需求，選擇進(jìn)行車行導(dǎo)航或是人行導(dǎo)航，本項(xiàng)目將針對(duì)用戶的具體選擇給出合適的導(dǎo)航路線。若用戶已位于目的地點(diǎn)，或是已在想要查找的基礎(chǔ)設(shè)施附近，程序?qū)⒔o出正確的提示信息，提醒用戶在原地仔細(xì)查找。對(duì)于較大的區(qū)域，往往無(wú)法將所有點(diǎn)一次全部顯示在導(dǎo)航屏中，用戶可以用鼠標(biāo)滾輪對(duì)地圖進(jìn)行放縮，也可用鼠標(biāo)右鍵移動(dòng)地圖，便于用戶詳細(xì)觀察導(dǎo)航圖。本項(xiàng)目中數(shù)據(jù)的錄入較為簡(jiǎn)潔，只需逐行向文本文件中添加點(diǎn)、邊信息即可，且基礎(chǔ)設(shè)施可以依用戶需求任意指定，且不受數(shù)量限制。
作品圖片
作品專業(yè)信息
撰寫目的和基本思路
- 撰寫目的：填補(bǔ)目前導(dǎo)航系統(tǒng)對(duì)較大規(guī)模區(qū)域內(nèi)部的導(dǎo)航精準(zhǔn)性的不足，提出可行的解決方案，并編寫軟件，解決規(guī)模較大區(qū)域內(nèi)部任意兩個(gè)位置之間的路徑規(guī)劃問(wèn)題。 基本思路：首先對(duì)項(xiàng)目進(jìn)行需求考察和分析，并按此需求對(duì)項(xiàng)目軟件進(jìn)行設(shè)計(jì)和規(guī)劃，同時(shí)列出項(xiàng)目計(jì)劃書(shū)的基本框架，嚴(yán)格按照模塊化程序設(shè)計(jì)要求編寫各軟件各模塊，在此過(guò)程中逐步完善項(xiàng)目計(jì)劃書(shū)。
科學(xué)性、先進(jìn)性及獨(dú)特之處
- 本項(xiàng)目的理論依據(jù)是經(jīng)典的圖論算法，該算法確保了項(xiàng)目中尋徑的準(zhǔn)確性。在準(zhǔn)確的基礎(chǔ)中，本項(xiàng)目豐富了圖中邊的屬性，可以針對(duì)人行，車行，以及臨時(shí)道路施工三種情況給出最可行的導(dǎo)航路徑。此外，本項(xiàng)目還具有較好的可擴(kuò)展性，對(duì)效率要求較高的核心算法和數(shù)據(jù)結(jié)構(gòu)部分采用C語(yǔ)言編寫，對(duì)用戶友好性要求較高的界面部分采用MFC編寫，核心部分和界面部分又以接口連接。可以較方便的移植到其他設(shè)備上，具有較好的可擴(kuò)展性。
應(yīng)用價(jià)值和現(xiàn)實(shí)意義
- 本項(xiàng)目解決了規(guī)模較大區(qū)域內(nèi)部任意兩個(gè)位置之間的路徑規(guī)劃問(wèn)題。同事考慮到區(qū)域內(nèi)部有“路障”和“臺(tái)階”等特殊物體的存在，本項(xiàng)目提供了“人行”和車型兩種行走模式，此外還考慮到某些道路可能因?yàn)榕R時(shí)施工而無(wú)法通行的情況，本項(xiàng)目還將某些路徑標(biāo)注為“臨時(shí)施工”狀態(tài)。這樣就解決了區(qū)域內(nèi)部的“路徑詢問(wèn)”這一需求問(wèn)題。此外，由于本項(xiàng)目采用模塊化程序設(shè)計(jì)，可以較方便的移植到其它平臺(tái)，可擴(kuò)展性較好。
學(xué)術(shù)論文摘要
- 針對(duì)現(xiàn)有GPS導(dǎo)航系統(tǒng)在區(qū)域內(nèi)部精準(zhǔn)導(dǎo)航方面的欠缺，本項(xiàng)目從現(xiàn)實(shí)出發(fā)，實(shí)現(xiàn)了區(qū)域內(nèi)部任意兩個(gè)地點(diǎn)之間的精確導(dǎo)航。整個(gè)區(qū)域被抽象為一個(gè)圖的數(shù)據(jù)結(jié)構(gòu)，區(qū)域內(nèi)的每個(gè)地點(diǎn)表示為圖中的一個(gè)頂點(diǎn)，而任意兩個(gè)地點(diǎn)之間的路徑以圖中所對(duì)應(yīng)點(diǎn)的有向邊來(lái)表示。選擇區(qū)域內(nèi)部的任意兩點(diǎn)，利用改進(jìn)的Dijkstra算法就可以計(jì)算出它們之間的最優(yōu)路徑。同時(shí)考慮到區(qū)域內(nèi)存在“路障”、“階梯”等特殊物體，本項(xiàng)目提供了“人行”和“車行”兩種行走模式。除了可以用文字對(duì)行走過(guò)程加以描述之外，本項(xiàng)目設(shè)計(jì)了專門的圖形用戶界面，可以更加直觀的顯示出行走的路線以及提供其他輔助功能。本項(xiàng)目的數(shù)據(jù)文件模塊、圖形顯示模塊之間和操作接口模塊之間相互獨(dú)立，滿足了模型-視圖-控制器設(shè)計(jì)模式，具有良好的可擴(kuò)展性。
獲獎(jiǎng)情況
- 無(wú)
鑒定結(jié)果
- 無(wú)
參考文獻(xiàn)
- 1、Ellis Horowitz,Sartaj Sahni,Susan Anderson-Freed著,朱仲濤 譯 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)（C語(yǔ)言版）（第二版）北京：清華大學(xué)出版社 2009 2、K.N.King著 呂秀鋒 黃倩 譯 C語(yǔ)言程序設(shè)計(jì)：現(xiàn)代方法（第二版） 北京：人民郵電出版社，2010 3、王曉東 編著 計(jì)算機(jī)算法設(shè)計(jì)與分析（第三版） 北京：電子工業(yè)出版社 2010 4、Thomas H. Cormen ,Charles E. Leiserson Ronald L. Rivest,Clifford Stein, Introduction to Algorithms(Third Edition),2009 5、Shimon Even.Graph Algorithms.Computer Science Press,1979
同類課題研究水平概述
- 全球定位導(dǎo)航系統(tǒng)（global positioning system）用于陸、海、空三大領(lǐng)域，提供實(shí)時(shí)、全天候和全球性的導(dǎo)航服務(wù)，并用于情報(bào)收集、核爆監(jiān)測(cè)和應(yīng)急通訊等一些軍事目的，在特定領(lǐng)域發(fā)揮著中重要的作用。隨著汽車工業(yè)的蓬勃發(fā)展，衛(wèi)星導(dǎo)航定位的應(yīng)用也日益普及。目前常用的導(dǎo)航系統(tǒng)有美國(guó)的GPS，歐洲的伽利略，中國(guó)的北斗等。以目前使用最廣泛的GPS導(dǎo)航為例，GPS導(dǎo)航的理論背景是通過(guò)把我國(guó)的一些常見(jiàn)地理位置標(biāo)注為“點(diǎn)”，然后把位置與位置之間的路徑定義為“邊”，進(jìn)而把整個(gè)國(guó)家抽象為一個(gè)很大的“圖”，然后利用圖論中的最短路徑和其他相關(guān)算法就能夠計(jì)算出一個(gè)地理位置到另外一個(gè)地理位置之間的最優(yōu)路徑。這些標(biāo)注點(diǎn)在GPS導(dǎo)航模塊中被“同等對(duì)待”，比如說(shuō)一個(gè)占地幾百平方米的酒店和一個(gè)占地幾平方公里的大學(xué)都被抽象為圖中的一個(gè)點(diǎn)，也就是這些標(biāo)注點(diǎn)并不能夠反映他們所代表相應(yīng)地理位置的實(shí)際規(guī)模。這樣做的一個(gè)后果是，當(dāng)目的地是一個(gè)規(guī)模較小的地理位置時(shí)（比如說(shuō)酒店），GPS能夠順利的導(dǎo)航至目的地。但是當(dāng)目的地是一個(gè)規(guī)模較大的區(qū)域內(nèi)部的某個(gè)地理位置時(shí)（比如說(shuō)某個(gè)大學(xué)的物理樓），此時(shí)要到達(dá)目的地只能分為“兩步走”。第一步就是借助GPS導(dǎo)航到達(dá)將此區(qū)域設(shè)置為標(biāo)注點(diǎn)的那個(gè)相應(yīng)地理位置（比如說(shuō)大門）；第二步就是通常借助人工咨詢的方式到達(dá)目的地，也就是說(shuō)此時(shí)GPS不能直接從出發(fā)點(diǎn)導(dǎo)航至目的地。一個(gè)可能的解決方案是將規(guī)模較大的區(qū)域內(nèi)部的所有地理位置都設(shè)置為標(biāo)注點(diǎn)，但是這樣做的后果是標(biāo)注點(diǎn)的數(shù)據(jù)庫(kù)將呈十倍甚至百倍的增加，從而導(dǎo)致計(jì)算數(shù)據(jù)庫(kù)中任意兩個(gè)標(biāo)注點(diǎn)之間的路徑將花費(fèi)很長(zhǎng)的時(shí)間，從而滿足不了導(dǎo)航系統(tǒng)所要求的最基本的“實(shí)時(shí)性”的要求，這也正是目前導(dǎo)航系統(tǒng)將規(guī)模較大區(qū)域只設(shè)置為其外圍的一個(gè)或者幾個(gè)標(biāo)注點(diǎn)的原因。因此該方案只具有理論上的可能性，而不具備任何現(xiàn)實(shí)意義。
