資源描述：
《地圖中最短路徑的搜索算法研究 畢業(yè)論文》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、本科生畢業(yè)論文題目地圖中最短路徑的搜索算法研究系別計算機與信息工程班級計算機科學(xué)與技術(shù)082姓名李小坤學(xué)號084632241答辯時間2012年5月新疆農(nóng)業(yè)大學(xué)計算機與信息工程學(xué)院目錄摘要11問題分析21.1技術(shù)分析21.2需求分析22系統(tǒng)總體框架及算法設(shè)計32.1系統(tǒng)總體框架32.2算法設(shè)計32.2.1廣度優(yōu)先算法32.2.2深度優(yōu)先算法52.2.3A*算法63程序運行結(jié)果與分析83.1圖中各種算法的運行效果83.1.1廣度優(yōu)先算法運行結(jié)果83.1.2深度優(yōu)先算法運行結(jié)果93.13A*算法運行結(jié)果103.2算法的總
2、體比較與分析104結(jié)論12參考文獻13謝辭14地圖中最短路徑的搜索算法研究姓名：李小坤指導(dǎo)老師：董巒摘要：目前為止,國內(nèi)外大量專家學(xué)者對“最短路徑問題”進行了深入的研究。本文通過理論分析,結(jié)合實際應(yīng)用，從各個方面較系統(tǒng)的比較了廣度優(yōu)先搜索算法(BFS)、深度優(yōu)先搜索算法(DFS)、A*算法的優(yōu)缺點，并描述了算法之間的一些關(guān)系，以及每種算法的適用情況。廣度優(yōu)先搜索算法占內(nèi)存多但速度較快，深度優(yōu)先搜索算法占內(nèi)存少但速度較慢，A*算法是啟發(fā)式搜索算法，適合于解決小規(guī)模、大規(guī)模以及超大規(guī)模的問題。程序通過調(diào)試運行，實現(xiàn)了設(shè)
3、計的目標(biāo)。關(guān)鍵詞：最短路徑算法；廣度優(yōu)先算法；深度優(yōu)先算法；A*算法；TheResearchofSearchAlgorithmofShortestPathinMapName:LiXiaokunTutor:DongLuanAbstract:Sofar,alargenumberofdomesticandforeignexpertsandscholarsonthe"shortestpathproblem"in-depthstudy.Inthispaper,throughtheoreticalanalysisandprac
4、ticalapplication,comprisewiththebreadth-firstsearchalgorithm(BFS),depth-firstsearchalgorithm(DFS)andtheA*algorithmsfromanyaspectsofsystematic.Anddescribessomerelationshipsbetweenthealgorithms,andtheapplicationofeachalgorithm.Breadth-firstsearchalgorithmneedmor
5、ememorybutfast,depth-firstsearchalgorithmneedlessmemorybutslow.A*algorithmisaheuristicsearchalgorithmwhicesuitableforsmall,bigandlarge-scaleproblems.Runninganddebuggingtheprogrammakethedesignedgoalcometrue.Keywords:Shortestpathalgorithm;Breadth-firstalgorithm;
6、Algorithm;A*algorithm;14地圖中最短路徑的搜索算法很早就廣泛的應(yīng)用于各個領(lǐng)域，最短路徑問題也是圖論研究中的一個經(jīng)典問題，旨在尋找圖（由結(jié)點和路徑組成的）中兩結(jié)點之間的最短路徑。用于解決最短路徑問題的算法被稱做“最短路徑算法”，有時被簡稱作“路徑算法”[1]。此次畢業(yè)設(shè)計，是大學(xué)生走進社會的最后一次學(xué)校學(xué)習(xí)，也是一次鍛煉，本設(shè)計基于VC++的基礎(chǔ)上，自主構(gòu)建若干個固定結(jié)點，并描述各個結(jié)點之間的路徑關(guān)系，然后用深度優(yōu)先算法、廣度優(yōu)先算法和A*算法求出圖中兩個結(jié)點的最短路徑，并進行全面的分析。1問題
7、分析1.1技術(shù)分析C++是一種靜態(tài)類型，支持多重編程范式的通用程序設(shè)計語言[1]。它廣泛的支援多種程序設(shè)計風(fēng)格（程序化程序設(shè)計、資料抽象化、面向?qū)ο蟪绦蛟O(shè)計、泛型程序設(shè)計）。它是由C語言發(fā)展而來的，既可以用于面向過程的結(jié)構(gòu)化程序設(shè)計，也可以用于面向?qū)ο蟮某绦蛟O(shè)計,是一門功能強大的程序設(shè)計語言[2]。VisualC++6.0是Microsoft公司在1998年推出的基于Windows9X和WindowsNT一個優(yōu)秀集成開發(fā)環(huán)境[3]。該開發(fā)環(huán)境為用戶提供了良好的可視化編程環(huán)境，程序員可以利用該開發(fā)環(huán)境輕松地訪問C++
8、源代碼編輯器、資源編輯器和使用內(nèi)部調(diào)試器，并且可以創(chuàng)建項目文件。VisualC++6.0不僅包括編譯器，而且它還包括許多有用組件，如程序向?qū)ppWizard、類向?qū)lassWizard等，通過這些組件的協(xié)同工作，可以在VisualC++6.0集成開發(fā)環(huán)境中輕松的完成創(chuàng)建源文件、編輯資源，以及對程序的編譯、連接和調(diào)試等各項工作[4]。1.2需求分析本系統(tǒng)是
