-最短路徑圖形結(jié)構(gòu)算法及應(yīng)用

[13]。本章節(jié)以宿遷學(xué)院的平面圖為例，后面章節(jié)中不做說明，也采用該簡(jiǎn)化地圖進(jìn)行示范。首先在百度地圖上搜索后獲取到宿遷學(xué)院的簡(jiǎn)略平面地圖見圖10，為便于分析，需先將地圖轉(zhuǎn)換成只有黑白色塊的地圖。使用Java代碼導(dǎo)入圖像并設(shè)置像素閾值，將地圖劃分成黑白兩色，白色的像素點(diǎn)視為道路，其余像素點(diǎn)視作障礙物，用黑色表示，將其柵格化成圖11。在圖11中白色代表道路，橋梁等可行走區(qū)域，黑色則代表湖泊，小山以及各類建筑障礙物等無法行穿行的區(qū)域。圖10宿遷學(xué)院地圖圖11柵格化宿遷學(xué)院地圖從結(jié)果來看，柵格化后的宿遷學(xué)院地圖比較完整的體現(xiàn)了原地圖的道路網(wǎng)，道路之間基本通暢，比例大小，障礙物的位置均原地圖一致，適合作為A*算法的地圖數(shù)據(jù)。3.2計(jì)算最短路線將柵格化處理后的地圖文件用java代碼編寫的A*算法進(jìn)行計(jì)算，分析出最短路線，展示在軟件上，運(yùn)行結(jié)果見圖12，并將數(shù)據(jù)匯總至表1：圖12Java代碼A*算法運(yùn)行結(jié)果圖A*算法運(yùn)行結(jié)果如圖12所示，觀察發(fā)現(xiàn)算法搜尋時(shí)間很短，運(yùn)行效率高，尋找的路線與最短路線基本吻合，軟件可以正常展示A*算法的特點(diǎn)和運(yùn)行結(jié)果。表1Java代碼A*算法運(yùn)行數(shù)據(jù)實(shí)驗(yàn)次數(shù)12345起點(diǎn)2，912，912，9120，179156，122終點(diǎn)19，65156，151215，93281，264，33花費(fèi)時(shí)間(ms)14236157是否找到路線是是是是否行走步數(shù)842232644990openList節(jié)點(diǎn)數(shù)2791466111448899107一共執(zhí)行的搜索次數(shù)13014465714535133470189575由表1中數(shù)據(jù)不難發(fā)現(xiàn)，1、2、3、4次均成功找到路線，且花費(fèi)時(shí)間隨著移動(dòng)的距離變短而變短，說明若搜尋的兩個(gè)點(diǎn)初始距離越近，花費(fèi)時(shí)間越短，這也是符合理論的。第5次實(shí)驗(yàn)終點(diǎn)選在了無法抵達(dá)的區(qū)域(左上角)，因此未能找到結(jié)果，花費(fèi)的時(shí)間最長且相近，說明算法遍歷了整個(gè)地圖，openList中所有方格都被遍歷也未搜尋到路線。表格中可以看出最終行走的距離并不是影響搜索效率的關(guān)鍵因素，維護(hù)的openList列表以及執(zhí)行的搜索次數(shù)才是影響算法效率的關(guān)鍵所在。而路徑越是復(fù)雜往往需要越多的搜索資源去搜索。后續(xù)改進(jìn)應(yīng)該著重從減少搜索次數(shù)和改進(jìn)算法搜索效率入手。4A*算法的改進(jìn)一般來說，作為普遍應(yīng)用的導(dǎo)航算法，A*算法在實(shí)際應(yīng)用中應(yīng)該考慮更多的因素，例如路況(路況好與壞影響行進(jìn)的速度)，客戶需求(由于路況不同導(dǎo)致速度不通，最短路往往不是最快路線，若客戶趕時(shí)間，此時(shí)最基本的A*算法便不適用)，另外還有紅路燈數(shù)量，限號(hào)限行，是否優(yōu)先考慮高速公路等等。隨著人們對(duì)生活質(zhì)量的追求，越來越多的需求也促使人們對(duì)A*算法的不斷改進(jìn)。對(duì)于算法本身來說，A*算法隨著地圖的擴(kuò)大，運(yùn)算量呈指數(shù)級(jí)增加，如何在不減少算法精度的情況下減少運(yùn)算量，提升算法效率成為最需要解決的問題。就目前的情況來看，一個(gè)既精準(zhǔn)又快速還不怎么占存儲(chǔ)空間的算法是不存在的，某些情況下犧牲了精準(zhǔn)度從而提升了速度，又或許花費(fèi)額外的時(shí)間提升精準(zhǔn)度，還有一些通過對(duì)地圖預(yù)處理，加快搜索速度，用空間代價(jià)交換時(shí)間代價(jià)的一種策略。本章將選取其中部分問題進(jìn)行改進(jìn)并得出結(jié)論。4.1減少轉(zhuǎn)向從A到B本可以只轉(zhuǎn)向一次就可到達(dá)的最短路徑，有時(shí)算法給出了另一條階梯狀的最短路徑，雖然從路程上來說而這并沒有區(qū)別，但在實(shí)際生活中，如圖13所示，在不考慮其他因素的情況下，同樣的路程如果多次轉(zhuǎn)向?qū)囕v、燃料都會(huì)造成不必要的損耗。圖13A*算法尋路圖在算法中，G值代表代價(jià)，為了使算法在相同F(xiàn)值的情況下轉(zhuǎn)向和直行中選擇直行，需要對(duì)轉(zhuǎn)彎適度的增加一定代價(jià)，每轉(zhuǎn)一次彎，G值除了路程上的代價(jià)增加，還應(yīng)該在每次轉(zhuǎn)向時(shí)增加一個(gè)轉(zhuǎn)向代價(jià)g即Gn=Gn+gn，運(yùn)行圖14改進(jìn)權(quán)值后A*算法尋路圖需要注意的是g的大小不應(yīng)該大于單元格長度/期望行走的最大路線，否則隨著路線的不斷搜尋，有可能導(dǎo)致最后尋找的路線并不是最短路線，使算法不夠準(zhǔn)確。4.2柵格化精度的選取4.2.1柵格精度對(duì)算法計(jì)算效率和準(zhǔn)確性的影響地圖在柵格化處理的時(shí)候如果追求精度，將地圖的像素劃分的非常細(xì)小，無疑會(huì)指數(shù)級(jí)的增加算法的運(yùn)算時(shí)間，而劃分的過大又會(huì)導(dǎo)致路線不精確，甚至提供錯(cuò)誤的路線。如何設(shè)定一個(gè)在滿足精度的基礎(chǔ)上，提升運(yùn)行速度的柵格化方法是提升效率的關(guān)鍵。本文使用的方法是以最窄的可通過道路的寬度為1個(gè)柵格基準(zhǔn)，這樣可以盡可能地壓縮地圖，增加運(yùn)算效率。但這會(huì)導(dǎo)致地圖精度不夠，有可能會(huì)造成這樣一種結(jié)局：導(dǎo)航提示你到了目標(biāo)點(diǎn)，然而實(shí)際上目標(biāo)點(diǎn)還在你的右邊十米處。顯然這種結(jié)局不是所有人都能接受的，因此在接近目的地時(shí)應(yīng)細(xì)化柵格，使導(dǎo)航更加精確。4.2.2針對(duì)柵格精度的改進(jìn)方案在初期使用精度比較低的搜索方案，設(shè)定一個(gè)范圍，當(dāng)closeList中的點(diǎn)進(jìn)入目標(biāo)點(diǎn)周圍的范圍的時(shí)候說明你距離目標(biāo)已經(jīng)“足夠近”了,這時(shí)重新劃分精度，從當(dāng)前點(diǎn)進(jìn)行比較細(xì)致的A*搜索，這種方法也許找到的路線不是全局最優(yōu)路線而是局部最優(yōu)，但在長距離搜索時(shí)可以大大節(jié)約時(shí)間。在游戲領(lǐng)域這種方案應(yīng)該更為廣泛的應(yīng)用——鼠標(biāo)點(diǎn)擊后游戲人物必須迅速響應(yīng)，如果直接進(jìn)行長距離的高精度A*搜索可能會(huì)出現(xiàn)人物“卡住”一下再移動(dòng)的情況，降低玩家的游戲體驗(yàn)，而先進(jìn)行低精度的A*搜索，讓人物先動(dòng)起來，在移動(dòng)的時(shí)候再進(jìn)行高精度的A*搜索，玩家不會(huì)有卡頓的感覺而且最終路線和最優(yōu)路線不會(huì)有太大偏差。如圖15起點(diǎn)為紅色方格，終點(diǎn)為藍(lán)色小方格，對(duì)其直接進(jìn)行A*算法搜索，注意此時(shí)選取的柵格化精度較高。圖15高精度A*算法初始圖算法運(yùn)算結(jié)果如圖16所示，綠色方格是被搜索的方格，藍(lán)色方格是被確定的最短路線。圖16高精度A*算法運(yùn)行結(jié)果圖現(xiàn)在降低柵格化的精度，轉(zhuǎn)化成大方格A*算法尋路(3*3的小方格轉(zhuǎn)換成1個(gè)大方格)，再次使用A*算法進(jìn)行計(jì)算，運(yùn)行結(jié)果如圖17所示。圖17低精度A*算法運(yùn)行結(jié)果圖在搜索到目標(biāo)地3×3的黃色區(qū)域后轉(zhuǎn)化回小方格，采用高精度A*搜索，效果如圖18和圖19。圖18低精度A*算法的接近目標(biāo)點(diǎn)區(qū)域圖19近目標(biāo)點(diǎn)區(qū)域的高精度A*算法運(yùn)算結(jié)果拼接后得到的最終行進(jìn)路線見圖20：圖20先低精度后高精度A*算法總路徑算法具體運(yùn)算數(shù)據(jù)匯總見表2。表2不同柵格精度的A*算法運(yùn)行結(jié)果算法高精度先低精度后高精度花費(fèi)時(shí)間(ms)31是否找到路線是是行走步數(shù)4951openList節(jié)點(diǎn)數(shù)88311搜索次數(shù)1972861分析：先通過低精度A*算法向前行進(jìn)，接近目標(biāo)點(diǎn)后再使用高精度A*算法，通過犧牲小部分最終路線的精度，大大提升了算法搜索的效率，且最終路線不會(huì)與最短路偏差太大，極大的節(jié)約了運(yùn)算資源。如果運(yùn)算資源較為充裕，可以縮短低精度A*算法的行走距離，在行走一段距離后即采用高精度A*算法，可以最大限度的提升路線的精度，又減少了等待的時(shí)間。例如在網(wǎng)絡(luò)實(shí)時(shí)對(duì)戰(zhàn)的游戲中，可以先進(jìn)行低精度的A*算法，然后只行進(jìn)一小段例如5%的路程，使玩家操作的角色迅速動(dòng)起來，在移動(dòng)5%路程后，利用這段時(shí)間計(jì)算機(jī)能夠計(jì)算好后續(xù)的高精度A*算法的路線，從而使得后面95%的路線都是極為精確的最短路線。而隨著計(jì)算機(jī)性能的不斷完善，這5%的路程會(huì)被不斷縮小，所產(chǎn)生的誤差對(duì)玩家的游戲體驗(yàn)來說已經(jīng)可以忽略不計(jì)了。這種注重目的地而不怎么考慮路程的思想也可以在估價(jià)函數(shù)H中加入一個(gè)權(quán)值實(shí)現(xiàn)——越接近目標(biāo)點(diǎn)，這個(gè)函數(shù)就會(huì)計(jì)算的越精確，反之可以降低函數(shù)的精度，使一開始的路線不怎么耗費(fèi)運(yùn)算資源。4.3對(duì)地圖進(jìn)行節(jié)點(diǎn)化處理對(duì)于長距離移動(dòng)來說，我們不應(yīng)該也不可能對(duì)每一步都進(jìn)行A*算法計(jì)算，即使采取降低柵格精度的策略有時(shí)也難以有效的降低算法復(fù)雜度，這時(shí)就要果斷放棄柵格化，采用節(jié)點(diǎn)化的地圖。在進(jìn)行導(dǎo)航時(shí)，人們往往對(duì)細(xì)節(jié)精確到每一條道路，每一個(gè)路口，如果劃分的再細(xì)致些也沒有過多的意義，因?yàn)闆]有人會(huì)在意自己怎么通過一條沒有岔路的直行道，反而會(huì)消耗硬件大量的算力，衛(wèi)星的定位也難以精確到人的每一步上，因此不如只在路口處設(shè)置節(jié)點(diǎn)，最后導(dǎo)航的結(jié)果以道路名展示，用戶只需沿著道路走即可到達(dá)目標(biāo)點(diǎn)。對(duì)圖10宿遷學(xué)院地圖進(jìn)行黑白二值化處理，然后對(duì)每個(gè)路口標(biāo)記節(jié)點(diǎn)，效果如圖21所示：圖21以A*算法計(jì)算節(jié)點(diǎn)化地圖初始圖

原本數(shù)萬像素的地圖，在每個(gè)分叉路口設(shè)置一個(gè)節(jié)點(diǎn)，變成了僅有68個(gè)主節(jié)點(diǎn)的節(jié)點(diǎn)圖。現(xiàn)在我們想從A點(diǎn)向B點(diǎn)進(jìn)發(fā)，尋路時(shí)：分別找到起點(diǎn)和終點(diǎn)周圍哈夫曼距離最近的主節(jié)點(diǎn)保存下來。用經(jīng)典A*算法進(jìn)行計(jì)算起始點(diǎn)到各自最近主節(jié)點(diǎn)的最短路線，因?yàn)榫嚯x通常較短，計(jì)算量很低。對(duì)兩個(gè)已存儲(chǔ)的主節(jié)點(diǎn)進(jìn)行A*搜索，因?yàn)橹鞴?jié)點(diǎn)的數(shù)量很少，計(jì)算量也很少。將三段路線進(jìn)行拼接，最后得到的路線就是節(jié)點(diǎn)化處理的最短路線。運(yùn)行后得到路線見圖22。圖22A*算法計(jì)算節(jié)點(diǎn)化地圖運(yùn)算結(jié)果算法幾乎是瞬間完成了計(jì)算，兩條綠色路線是起始點(diǎn)到主節(jié)點(diǎn)的最短路線，紅色路線是兩個(gè)主節(jié)點(diǎn)中的最短路線。不難看出最終行進(jìn)的路線非常接近最短路線。優(yōu)點(diǎn)：極大的提升了搜索效率，在長距離導(dǎo)航中優(yōu)勢(shì)明顯。缺點(diǎn)：最終的路線不一定是最短路線，且在短距離尋路時(shí)可能會(huì)因節(jié)點(diǎn)過少而繞路，因此短距離時(shí)不應(yīng)采用此方法。5結(jié)論與展望5.1結(jié)論A*算法結(jié)合了Dijkstra和BFS啟發(fā)式思想，保證最短路的同時(shí)提升了效率，在實(shí)際應(yīng)用中表現(xiàn)出色，尋路效率高，用時(shí)短。是現(xiàn)在被廣泛使用的最短路算法。本文在經(jīng)典A*算法的基礎(chǔ)上加以改進(jìn)，增加了轉(zhuǎn)向時(shí)的權(quán)值，使得算法在多條相同預(yù)期的道路時(shí)，總會(huì)優(yōu)先選擇不怎么轉(zhuǎn)向的道路。針對(duì)柵格化地圖的A*算法，考慮到地圖尺寸以及精度的需求，可能會(huì)造成的算法效率緩慢，用時(shí)過長的結(jié)果。采用先低精度后高精度的A*算法，減少了算法在初期的運(yùn)算量，使用者不會(huì)體驗(yàn)到算法運(yùn)行所產(chǎn)生的卡頓感，在軟件性能有限的情況下非常實(shí)用。對(duì)于大地圖道路網(wǎng)的導(dǎo)航，不需要對(duì)全圖都進(jìn)行柵格化，轉(zhuǎn)換成在每個(gè)有道路連接的路口處設(shè)置節(jié)點(diǎn)，節(jié)點(diǎn)與節(jié)點(diǎn)之間的距離就是道路的長度。算法運(yùn)算時(shí)只需要先將人導(dǎo)航到距離最近的節(jié)點(diǎn)，然后在節(jié)點(diǎn)中使用A*算法，可以大大提升算法效率。5.2展望 本文為方便計(jì)算將路徑導(dǎo)航抽象成二維空間中正方形節(jié)點(diǎn)的尋路問題，且僅有4鄰域移動(dòng)方向，與現(xiàn)實(shí)生活中有較大差異，后續(xù)研究應(yīng)該以更復(fù)雜的情況例如6鄰域8鄰域?yàn)檠芯繉?duì)象，移動(dòng)方向應(yīng)有更多選擇，對(duì)應(yīng)的估價(jià)函數(shù)H也應(yīng)由原本的曼哈頓距離改為歐氏距離或者其他更加準(zhǔn)確的估價(jià)函數(shù)。在計(jì)算一段路線的移動(dòng)代價(jià)時(shí)，只采用路徑長度作為代價(jià)是不準(zhǔn)確的，相同長度的道路在不同的路況影響下，通過時(shí)有較大的時(shí)間差異，后續(xù)研究應(yīng)該加上路況的影響，以路線長度和路況好壞的綜合評(píng)價(jià)結(jié)果作為移動(dòng)的代價(jià)。 文中演示的道路節(jié)點(diǎn)大多道路連接分布均勻，而實(shí)際生活中的道路網(wǎng)存在大量無標(biāo)度網(wǎng)絡(luò)，應(yīng)當(dāng)進(jìn)一步研究和調(diào)整，使算法適應(yīng)更多不同網(wǎng)絡(luò)。參考文獻(xiàn)：郭陽.動(dòng)態(tài)復(fù)雜網(wǎng)絡(luò)的最短路徑研究[D].遼寧大學(xué),2019.梁娟.網(wǎng)絡(luò)最短路徑問題的研究與應(yīng)用[D].南京郵電大學(xué),2015.劉宏魁.基于A-star算法的地圖查詢系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].電子技術(shù)與軟件工程,2018(22):44.李坤,蔣莉莉.分布式計(jì)算中基于A-star的工作流調(diào)度改進(jìn)算法研究[J].計(jì)算機(jī)工程與科學(xué),2013,35(03):38-42.宋巖.基于A-Star算法的進(jìn)路搜索研究[D].西南交通大學(xué),2014.劉熙明,魏旭,竇立剛,覃洪波,楊露溪.基于A-Star算法的AdHoc無線網(wǎng)絡(luò)最優(yōu)路由模型研究[J].佛山科學(xué)技術(shù)學(xué)院學(xué)報(bào)(自然科學(xué)版),2019,37(04):38-42.劉微,肖華勇.復(fù)雜網(wǎng)絡(luò)中近似最短路徑問題[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2016,25(05):107-112.時(shí)也.基于A-Star算法與模糊控制融合的移動(dòng)機(jī)器人路徑規(guī)劃[D].武漢科技大學(xué),2012.王恒青,宋如敏.最短路徑算法Dijkstra算法在路由選擇中的應(yīng)用[J].科技信息(學(xué)術(shù)研究),2008(32):569-570.向志華,賴小平.基于BFS算法的有阻斷路徑的最短路徑算法研究[J].信息通信,2019(11):41-42.謝暉,張達(dá)奇,馮李.結(jié)合曼哈頓距離的A-star算法在光纜尋址中的應(yīng)用[J].信息通信,2019(01):34-36.吳健.基于A-star改進(jìn)路徑規(guī)劃算法研究[D].安徽工業(yè)大學(xué),2019.萬平.基于A-star算法的航路規(guī)劃算法設(shè)計(jì)與仿真研究[J].中國水運(yùn).航道科技,2018(04):58-65.致謝時(shí)光荏苒，4年的大學(xué)生活如白駒過隙般轉(zhuǎn)瞬即逝，宿遷學(xué)院大校園生活給了我許多快樂和驚喜。大學(xué)的學(xué)習(xí)生活讓我學(xué)到了為人處世的原則和專業(yè)的知識(shí)理論，而我已不再是從前那個(gè)無知的少年，衷心祝愿母校未來發(fā)展得更好！首先我要感謝蔣濤導(dǎo)師在對(duì)我的指導(dǎo)和講解，從論文材料的收集、題目的確認(rèn)和理解、創(chuàng)新點(diǎn)的研究、論文的反復(fù)修改一直到最終的論文定稿，蔣老師都給了我非常多的幫助，讓我對(duì)選題有了一個(gè)深刻的理解和認(rèn)識(shí)，期間對(duì)我的提問也是熱心解答。中期檢查時(shí)指出我論文的不足，并協(xié)助我完善內(nèi)容。疫情期間無法見面討論，導(dǎo)師督促我們抓緊完成論文后網(wǎng)上對(duì)我們進(jìn)行了指導(dǎo)。可以看出導(dǎo)師為了協(xié)助我完成論文順利畢業(yè)付出了很多，態(tài)度也是一絲不茍，不容有一點(diǎn)錯(cuò)誤，這種嚴(yán)謹(jǐn)踏實(shí)的風(fēng)格令我十分尊敬。尤其是在我的論文進(jìn)展出現(xiàn)問題時(shí)，老師即使提醒和指導(dǎo)，使論文進(jìn)度得以正常進(jìn)行。其次還要感謝在宿遷學(xué)院的各科的任課老師在校期間對(duì)我的栽培，正是有了他們的督促，我沒有虛度四年的大學(xué)時(shí)光，用在校時(shí)間學(xué)習(xí)很多理論知識(shí)。還要感謝高燕輔導(dǎo)員，在日常生活中和學(xué)習(xí)工作上對(duì)我的大力支持，輔導(dǎo)員的認(rèn)真負(fù)責(zé)讓我的學(xué)習(xí)生活很少遇到阻礙，很多事情在輔導(dǎo)員的幫助下迎刃而解，感謝宿遷學(xué)院的老師們，使我順利完成這篇論文！還要感謝各位對(duì)我論文做出幫助的同學(xué)，很多小問題例如格式，一些零散的知識(shí)點(diǎn)，在學(xué)校沒有完善的部分，是多虧了同學(xué)們的幫助，在小問題上節(jié)約了我大量的精力，讓我可以騰出時(shí)間去鉆研論文，感謝你們的一路陪伴！最后對(duì)本次論文的評(píng)閱專家致以最誠摯的敬意！附錄package讀取;importjava.io.BufferedReader;importjava.io.File;importjava.io.FileReader;importjava.io.IOException;importjava.util.ArrayList;importjava.util.List;importjava.awt.Color;importjava.awt.Graphics;importjava.awt.event.MouseEvent;importjava.awt.event.MouseListener;importjavax.swing.JFrame;importjavax.swing.JPanel;publicclassAStar{ staticint[][]NODES=newint[292][260]; staticint[][]DRAW=newint[292][260]; staticint[][]point=newint[2][2];staticintpointNumber=0;staticArrayList<Node>arrayList=newArrayList<Node>();publicstaticfinalintSTEP=10;privateArrayList<Node>openList=newArrayList<Node>();privateArrayList<Node>closeList=newArrayList<Node>();publicNodefindMinFNodeInOpneList(){NodetempNode=openList.get(0);for(Nodenode:openList){if(node.F<tempNode.F){tempNode=node;}}returntempNode;}publicArrayList<Node>findNeighborNodes(NodecurrentNode){ArrayList<Node>arrayList=newArrayList<Node>();inttopX=currentNode.x;inttopY=currentNode.y-1;if(canReach(topX,topY)&&!exists(closeList,topX,topY)){arrayList.add(newNode(topX,topY));}intbottomX=currentNode.x;intbottomY=currentNode.y+1;if(canReach(bottomX,bottomY)&&!exists(closeList,bottomX,bottomY)){arrayList.add(newNode(bottomX,bottomY));}intleftX=currentNode.x-1;intleftY=currentNode.y;if(canReach(leftX,leftY)&&!exists(closeList,leftX,leftY)){arrayList.add(newNode(leftX,leftY));}intrightX=currentNode.x+1;intrightY=currentNode.y;if(canReach(rightX,rightY)&&!exists(closeList,rightX,rightY)){arrayList.add(newNode(rightX,rightY));}returnarrayList;}publicbooleancanReach(intx,inty){if(x>=0&&x<NODES.length&&y>=0&&y<NODES[0].length){returnNODES[x][y]==0;}returnfalse;}publicNodefindPath(NodestartNode,NodeendNode){openList.add(startNode);while(openList.size()>0){NodecurrentNode=findMinFNodeInOpneList();openList.remove(currentNode);closeList.add(currentNode);ArrayList<Node>neighborNodes=findNeighborNodes(currentNode);for(Nodenode:neighborNodes){if(exists(openList,node)){foundPoint(currentNode,node);}else{notFoundPoint(currentNode,endNode,node);}}if(find(openList,endNode)!=null){returnfind(openList,endNode);}}returnfind(openList,endNode);}privatevoidfoundPoint(NodetempStart,Nodenode){intG=calcG(tempStart,node);if(G<node.G){node.parent=tempStart;node.G=G;node.calcF();}}privatevoidnotFoundPoint(NodetempStart,Nodeend,Nodenode){node.parent=tempStart;node.G=calcG(tempStart,node);node.H=calcH(end,node);node.calcF();openList.add(node);}privateintcalcG(Nodestart,Nodenode){intG=STEP;intparentG=node.parent!=null?node.parent.G:0;returnG+parentG;}privateintcalcH(Nodeend,Nodenode){intstep=Math.abs(node.x-end.x)+Math.abs(node.y-end.y);returnstep*STEP;}privatestaticvoidflash(){ NodestartNode=newNode(point[0][0],point[0][1]); NodeendNode=newNode(point[1][0],point[1][1]); Nodeparent=newAStar().findPath(startNode,endNode); while(parent!=null){ arrayList.add(newNode(parent.x,parent.y)); parent=parent.parent; } System.out.println("\n"); for(inti=0;i<NODES.length;i++){ for(intj=0;j<NODES[0].length;j++){ if(exists(arrayList,i,j)){ System.out.print("@,"); }else{ System.out.print(NODES[i][j]+","); } } System.out.println(); }}publicstaticvoidmain(String[]args)throwsIOException{ Filef=newFile("D://QAP.txt"); BufferedReaderbuf=newBufferedReader(newFileReader(f)); int[][]city=newint[292][260]; intline=0; Stringstr=null; while((buf.read())!=-1){ str=buf.readLine(); String[]date=str.split(""); Strings=date[0]; int[]a=newint[s.length()]; for(inti=0;i<s.length();i++){a[i]=Integer.parseInt(String.valueOf(s.charAt(i)));} for(inti=0;i<a.length;i++){NODES[line][i]=a[i];DRAW[line][i]=a[i];} line++; } NodestartNode=newNode(point[0][0],point[0][1]); NodeendNode=newNode(point[1][0],point[1][1]); Nodeparent=newAStar().findPath(startNode,endNode); while(parent!=null){ arrayList.add(newNode(parent.x,parent.y)); parent=parent.parent; } System.out.println("\n"); JFramejFrame=newJFrame(); JPaneljpanel=newJPanel(){ publicvoidpaint(Graphicsgraphics){ super.paint(graphics); for(inti=0;i<NODES.length;i++){ for(intj=0;j<NODES[0].length;j++){ if(exists(arrayList,i,j)){ graphics.setColor(Color.BLUE); graphics.fillRect(3*j,3*i,3,3); }elseif(NODES[i][j]==1){ graphics.setColor(Color.BLACK); graphics.fillRect(3*j,3*i,3,3); }elseif(DRAW[i][j]==2){ graphics.setColor(Color.RED); graphics.fillRect(3*j,3*i,3,3); } } System.out.println(); } } }; jFrame.add(jpanel); jFrame.setSize(680,900); jFrame.setVisible(true); jpanel.addMouseListener(newMouseListener(){ @Override publicvoidmouseClicked(MouseEvente){ DRAW[(int)(e.getY()/3)][(int)(e.getX()/3)]=2; System.out.println(e.getX()); System.out.println(e.getY()); pointNumber++; point[pointNumber-1][0]=(int)(e.getY()/3); point[pointNumber-1][1]=(int)(e.getX()/3); flash(); jpanel.repaint(); } @Override publicvoidmouseEntered(MouseEventarg0){ } @Override publicvoidmouseExited(MouseEventarg0){ } @Override publicvoidmousePressed(MouseEventarg0){ } @Override publicvoidmouseReleased(MouseEventarg0){ } }); }publicstaticNodefind(List<Node>nodes,Nodepoint){for(Noden:nodes)if((n.x==point.x)&&(n.y==point.y)){returnn;}returnnull;}publicstaticbooleanexists(List<Node>nodes,Nodenode){for(Noden:nodes){if((n.x==node.x)&&(n.y==node.y)){

HYPERLINK電腦文件整理懶招從來都是不會(huì)經(jīng)常整理文件的，不過時(shí)間一長，眾多的文檔分布在硬盤的各個(gè)角落，用目錄進(jìn)行整理保存，工作量大、查看起來也不方便且還會(huì)浪費(fèi)不少的磁盤空聞；用壓縮工具打包，盡管可以節(jié)約空間但是卻無法直接編輯修改或查看壓縮包中的文件。這些招，懶人怎么會(huì)用，他們自有妙招!再多再亂的文件也能整理得井井有條，關(guān)鍵是不費(fèi)力哦!

懶招1，自動(dòng)提取亂中取勝

小張起初將照片、Office文檔、電影、音樂等文件一股腦地存放在某一個(gè)磁盤分區(qū)，剛開始文件少使用起來倒也方便，但隨著時(shí)間的推移，文件數(shù)量劇增，每次找所需的文件都要瞪大眼睛，不過有了MY文檔管理器(下載地址：)就不用擔(dān)心了。

第一步，下載MY文檔管理器，解壓到任意目錄，直接雙擊其中的可執(zhí)行性文件即可使用。依次單擊“節(jié)點(diǎn)操作→添加節(jié)點(diǎn)”，分別添加多個(gè)節(jié)點(diǎn)，如“辦公文檔”、“電影”等分類，這樣做的目的是方便歸類。

第二步，在小張的F盤中的TEST目錄下有眾多的RM、MP3、JPG、DOC、TXT格式的文件，現(xiàn)在他要把JPG格式的文件提取到“照片”類別中。依次單擊“系統(tǒng)配置→文件過濾”選項(xiàng)，打開Dialog對(duì)話框，輸入“*.doc”，單擊“添加”按鈕，意思是過濾掉所有類型為“.DOC”的文件。然后按照同樣的方法，將“*.txt”、“*.rm”、“*.MP3”一一添加進(jìn)來。

第三步，雙擊左側(cè)窗格中的“照片”節(jié)點(diǎn)，然后依次單擊“記錄操作→導(dǎo)入記錄樹”命令，在打開的對(duì)話框中單擊瀏覽按鈕，打開“F:\test”目錄，單擊“確定”按鈕之后就可以將格式為JPG的文件提取出來并添加到“照片”節(jié)點(diǎn)中了。

懶招2，不同的電腦統(tǒng)一的管理

小張是電愛的Fans，工作之余常常為雜志寫稿，他寫完的和正在處理的稿件一般都存在一個(gè)稿件文件夾里。不過時(shí)間一長，家里的電腦(PC1)和單位的電腦(PC2)上都有這個(gè)文件夾。時(shí)常需要通過移動(dòng)硬盤(U盤)在兩臺(tái)電腦之間傳遞，使用和管理都很不方便。不過他現(xiàn)在用優(yōu)盤就可以統(tǒng)一管理了。

第一步，將上文提到的那個(gè)MY文檔管理器解壓后直接拷貝到優(yōu)盤上。把優(yōu)盤插到PC1上，并運(yùn)行軟件，依次單擊“記錄操作→導(dǎo)入記錄樹”命令，在隨后彈出的對(duì)話框中設(shè)置好“稿件”文件夾的根目錄，將“導(dǎo)入深度”設(shè)置為“5”，單擊“確定”后，稍等片刻，軟件就把PC1上的“稿件”導(dǎo)入到MY文檔管理器中。

小提示：通過這種方式導(dǎo)入到程序中的僅僅是文件的路徑、文件名等屬性信息，并不是文件本身。

第二步，把優(yōu)盤插到PC2上，按照同樣的方法導(dǎo)入PC2上的“稿件”文件。以后要編輯“稿件”里的文件，你自己根本不用記住哪臺(tái)電腦的哪個(gè)路徑，只要把優(yōu)盤插入到電腦，運(yùn)行MY文檔管理器，就可以直接編輯了。

第三步，為方便在異地使用，小張決定為當(dāng)前正在處理的稿件增加一個(gè)副本。在需要異地處理的稿件上右鍵單擊，選擇“復(fù)制文件到(自動(dòng)添加副本)”命令，在彈出的對(duì)話框中將保存目錄設(shè)置為優(yōu)盤上的某個(gè)目錄即可。這樣，就可以在優(yōu)盤上編輯PC1或PC2的稿件了。

小提示：對(duì)于PC1、PC2上的同名文件，MY文檔管理器以不同的磁盤號(hào)+文件路徑來標(biāo)識(shí)文件記錄，因此，對(duì)于不同電腦上的同名文件，甚至是路徑和文件名完全相同的文件，程序也可以準(zhǔn)確識(shí)別哪個(gè)是哪個(gè)。

懶招3多種文件批量移動(dòng)

要將文件管理得井然有序，就免不了要進(jìn)行復(fù)制、刪除、移動(dòng)等等操作，如果一個(gè)個(gè)進(jìn)行操作，工作量是非常巨大的。這時(shí)我們就需要借助于BelvedereAutomated(下載地址：.com/assets/resources/2008/03/Belvedere%200.3.exe)進(jìn)行批量操作了。例如我們想把“F:\test”目錄中的所有照片移動(dòng)到F盤中的“北京游照片”目錄中，可以按以下方法進(jìn)行。

第一步，建立“F:\test”目錄后在“rule”一欄中，單擊“+”按鈕，建立一個(gè)規(guī)則。在“Descriptior”文本框中為當(dāng)前規(guī)則起一個(gè)名字如“批量整理移動(dòng)”。單擊第一個(gè)下拉列表，在這里可以選擇Name(文件名)、Extension(擴(kuò)展名)、Size(大小)等進(jìn)行操作，這里選擇擴(kuò)展名“Extension”。單擊第二個(gè)下拉列表，在這里設(shè)置的是操作條件，有is(是)、isnot(不是)、contains(包含)等操作可供選擇，這里選擇的是“is”。接下來，在最后的文本框中輸入圖片文件的擴(kuò)展名，示例中是“JPG”。定義的規(guī)則合起來的意思就是“擴(kuò)展名是JPG”。

第二步，在“Dothefollowing”區(qū)域設(shè)置操作動(dòng)作，單擊第一個(gè)下拉列表進(jìn)行操作動(dòng)作的選擇，有“Movefile(移動(dòng))、Renamefile(重命名)、Deletefile(刪除)”等動(dòng)作可供選擇，我們要批量移動(dòng)，那就選擇重命名“Movefile(移動(dòng)文件)”。接下來，單擊后面的按鈕選擇“F:\北京游照片”目錄。

第三步，規(guī)則設(shè)置完畢，單擊“Test”按鈕應(yīng)用規(guī)則，程序即可一次性地將所有擴(kuò)展名為“JPG”的圖片文件移動(dòng)到“F:\北京游照片”目錄中了。

懶招4提綱挈領(lǐng)一點(diǎn)即得

在前面幾大懶招的幫助下，你電腦里的文件應(yīng)該已經(jīng)有點(diǎn)類別了吧。如果從此想告別懶人的生活，那就要養(yǎng)成管理文件的好習(xí)慣了。

第一步，在你保存資料的電腦分區(qū)中，要接類別建立多個(gè)文件夾，可以按用途分為：學(xué)習(xí)、娛樂、暫存、工作、下載，在娛樂下又可以建立二級(jí)目錄：電影、歌曲、動(dòng)畫等。也可以按照常見的文件性質(zhì)進(jìn)行分類，例如分為：圖片、電影、電子書、安裝文件等，當(dāng)然也可以按照你的需要再建立二級(jí)目錄，以后每有文件需要保存就按這個(gè)類別保存到相應(yīng)的目錄。

第二步，雖然現(xiàn)在已經(jīng)把文件分門別類存放了，但時(shí)間長了，目錄太深，一層一層查找也很麻煩的，在EXCEL里建一個(gè)目錄就可以統(tǒng)一管理了。運(yùn)行EXCEL后，新建一個(gè)表格，然后按照我們的分類方式隔行輸入：圖片、電影、電子書，在圖片分類下再建立二級(jí)目錄名，例如明星、汽車、壁紙等。

第三步，右鍵單擊“圖片文字”，選擇“超鏈接”，在彈出的對(duì)話框中選擇電腦里圖片目錄文件夾，單擊“確定”后EXCEL里的“圖片”文字就變成彩色。用同樣的方法為一級(jí)目錄的“電影、電子書”和二級(jí)目錄的“明星、汽車、壁紙”等添加超鏈接。然后將這個(gè)EXCEL文件命名為文件目錄，保存到桌面上，以后打開這個(gè)文檔，直接單擊相應(yīng)的文字，比如單擊“壁紙”，就可以切換到壁紙文件夾了。

小提示：如果要更改某個(gè)超鏈接，直接右鍵單擊該文字，選擇“編輯超鏈接”就可以了。本人的電腦分類原則簡(jiǎn)述如下。

硬盤的第一層(請(qǐng)?jiān)谧约旱募A中右鍵“按組排列”查看)

第一位字母表示A生活?yuàn)蕵稡教學(xué)C工作D安裝程序

第二位字母表示只是流水號(hào)

AA影視

AB音樂

AC閱讀

AD圖片

AE相冊(cè)

生活?yuàn)蕵?/p>

BA計(jì)算機(jī)

BB英語

BC運(yùn)動(dòng)

BD游戲攻略

BE衣食住行

BF文藝

教學(xué)

CA管理制度

CB流程圖

CC程序文件

工作

DA娛樂

DB其它

安裝程序

硬盤的第二層(進(jìn)入“AA影視”的文件夾舉例)

第一位字母表示只是流水號(hào)

第二位字母表示只是流水號(hào)

AA電影

BA電視劇

CAMTV

硬盤的第三級(jí)(進(jìn)入“AA電影”的文件夾舉例)

第一位字母表示A動(dòng)作片B劇情片C動(dòng)畫片

第二位字母表示A未看過B已看過

AA導(dǎo)火線

AB尖峰時(shí)刻

動(dòng)作片

BA獨(dú)自等待

劇情片

CB機(jī)器貓

CB獅子王

動(dòng)畫片

利用“字母排序”和“按組排列查看”可以使文件查看和存放簡(jiǎn)潔明了，結(jié)合自己資料的特點(diǎn)和實(shí)際需求，給自己定一個(gè)分類原則并嚴(yán)格執(zhí)行。個(gè)人電腦資料的資源會(huì)得到高效而充分的利用。電腦文件管理八條小技巧

在電腦的內(nèi)部，在電腦的桌面上，在“資源管理器”中，充斥著無序與混亂,這種虛擬的混亂極大地影響了電腦的性能和我們辦公的效率，當(dāng)大家面臨這個(gè)問題時(shí)，通常認(rèn)為硬盤空間又不夠了，電腦性能又不跟不上了，需要再換一臺(tái)新的電腦了。事實(shí)上，我們真正需要的是坐下來，好好花時(shí)間將電腦里的文件真正管理起來，會(huì)為自己日后省下更多的時(shí)間。

文件管理的真諦在于方便保存和迅速提取，所有的文件將通過文件夾分類被很好地組織起來，放在你最能方便找到的地方。解決這個(gè)問題目前最理想的方法就是分類管理，從硬盤分區(qū)開始到每一個(gè)文件夾的建立，我們都要按照自己的工作和生活需要，分為大大小小、多個(gè)層級(jí)的文件夾，建立合理的文件保存架構(gòu)。此外所有的文件、文件夾，都要規(guī)范化地命名，并放入最合適的文件夾中。這樣，當(dāng)我們需要什么文件時(shí)，就知道到哪里去尋找。

這種方法，對(duì)于相當(dāng)數(shù)量的人來說，并不是一件輕松的事，因?yàn)樗麄兞?xí)慣了隨手存放文件和辛苦、茫無頭緒地查找文件。

下面，我們將幫你制訂一套分類管理的原則，并敦促您養(yǎng)成好的文件管理習(xí)慣。以下是我們總結(jié)出的一些基本技巧，這些技巧并不是教條，可能并不適合你，但無論如何你必須要有自己的規(guī)則，并堅(jiān)持下來，形成習(xí)慣。

一、發(fā)揮我的文檔的作用

有很多理由讓我們好好地利用“我的文檔”，它能方便地在桌面上、開始菜單、資源管理器、保存/打開窗口中找到，有利于我們方便而快捷地打開、保存文件。我們可以利用“我的文檔”中已有的目錄，也可以創(chuàng)建自己的目錄，將經(jīng)常需要訪問的文件存儲(chǔ)在這里。至于“我的文檔”存儲(chǔ)在C盤，在重裝系統(tǒng)時(shí)可能會(huì)誤刪除的問題，可以在非系統(tǒng)盤建立一個(gè)目錄，然后右擊桌面上的“我的文檔”，選擇“屬性”。在彈出的“我的文檔屬性”窗口中，單擊目標(biāo)文件夾下的“移動(dòng)”按鈕，然后在新的窗口中指定我們剛創(chuàng)建的文件夾。重裝系統(tǒng)后再次執(zhí)行以上操作，再重新指向此文件夾即可，即安全又便捷。

小提示：如果你使用Windows2000/XP，則移動(dòng)“我的文檔”文件夾時(shí)，其下的所有文件會(huì)自動(dòng)移過去，但如果你使用Windows9x，則需要手工將C:MyDocuments下的所有文件手工移到新指定的文件夾中，否則可能會(huì)丟失數(shù)據(jù)。

二、