• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            KISS(Keep It Simple, Standard)

              C++博客 :: 首頁 :: 聯(lián)系 :: 聚合  :: 管理
              10 Posts :: 0 Stories :: 24 Comments :: 0 Trackbacks

            常用鏈接

            留言簿(10)

            我參與的團(tuán)隊

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            最近做了路徑搜索,看了網(wǎng)上的描述真是晦澀,所以自己就整理下!
            圖畫的不太好, :)
            綠色的是節(jié)點(diǎn),紅色的為權(quán)值,箭頭為可通行的標(biāo)志.

            現(xiàn)在我們要從 0 節(jié)點(diǎn) 到 12 節(jié)點(diǎn) 找一條最優(yōu)路徑:
            首先咱們要解決NODE點(diǎn)存貯的信息(結(jié)構(gòu)):
            struct NodeBaseInfo
            {
               unsigned short nNodeID;   //番號
               unsigned long  nMeasure;            //權(quán)值
               NodeBaseInfo *pParent;            //父節(jié)點(diǎn)
            };

            我寫了簡單的結(jié)構(gòu)大家可以根據(jù)自己需要定義(定義這個結(jié)構(gòu)是為了更好理解)
            下面講的是最主要的了:
            DIJKSTAR算法中要定義兩個表:OPEN 和 CLOSE  (其實(shí)可以看作鏈表)
            他的原理就是把沒有遍歷的點(diǎn)放在 OPEN 表中,把從 OPEN表中遍歷到的最短權(quán)值的點(diǎn)放入
            CLOSE 表中,當(dāng)插入 CLOSE表中的節(jié)點(diǎn)的番號于我們要的重點(diǎn)時算法結(jié)束;然后按照父節(jié)點(diǎn)(pParent)
            向上遞歸就可以得到我們要的最優(yōu)路徑了。

            第一步:應(yīng)為 OPEN 和CLOSE表都是空的,把起點(diǎn)(0節(jié)點(diǎn))插入CLOSE標(biāo)中,它的權(quán)值為0。把起點(diǎn)(0節(jié)點(diǎn))附近的節(jié)點(diǎn)(因該為可通行的)插入OPEN 表中(最好按權(quán)值從大道小的順序插入,這樣取得最優(yōu)值時,這樣速度就會很快)。(如示例圖)

            第2步:從OPEN表中找到權(quán)值最小的節(jié)點(diǎn),把它插入CLOSE 表中, 把這個節(jié)點(diǎn)的可連通的節(jié)點(diǎn)查入OPEN
            表,(如果OPEN表中存在要查入的點(diǎn),如果要插入的節(jié)點(diǎn)的權(quán)值比已經(jīng)存在的小,就把已經(jīng)查入的權(quán)值該為最小的,如果要插入的節(jié)點(diǎn)的權(quán)值比已經(jīng)存在的大,就忽落它.)
            (為了更好的理解我把父節(jié)點(diǎn)也加入了,如示例圖)

            posted on 2008-02-01 16:13 QUIRE-0216 閱讀(3900) 評論(12)  編輯 收藏 引用 所屬分類: Arithmetic(算法)

            Feedback

            # re: 關(guān)于Dijkstra算法我的理解(上) 2008-07-28 19:54 duzhihua
            看看在說,別處寫的的確晦澀難懂,而且?guī)缀跛械胤降拿枋龆家粯?nbsp; 回復(fù)  更多評論
              

            # re: 關(guān)于Dijkstra算法我的理解(上) 2008-10-07 12:56 Vincent
            不錯,支持原創(chuàng)
            自己的研究成果,Dijkstra的進(jìn)化。。。

            鄙視網(wǎng)上的大抄特抄  回復(fù)  更多評論
              

            # re: 關(guān)于Dijkstra算法我的理解(上) 2008-10-07 15:36 Vincent
            的確是Dijkstra

            畢竟是有限狀態(tài)空間的窮舉搜索,面對大規(guī)模數(shù)據(jù)時,不可以預(yù)測的情況增多,效率低下,任務(wù)甚至不能完成。

            優(yōu)點(diǎn):準(zhǔn)確性高

              回復(fù)  更多評論
              

            # re: 關(guān)于Dijkstra算法我的理解(上) 2008-10-07 16:00 Vincent
            使用權(quán)值 也就是A*里面的估價值重排Open表,有啟發(fā)式搜索的味道

            沒有點(diǎn)名使用估值函數(shù),因?yàn)樗呀?jīng)吧估值函數(shù)的結(jié)果表示為權(quán)值了 呵呵



            就是A*了  回復(fù)  更多評論
              

            # re: 關(guān)于Dijkstra算法我的理解(上) 2009-04-28 22:17 vision
            簡單明了... 至少我看懂了... 其他頁面上的實(shí)在看不懂...  回復(fù)  更多評論
              

            # re: 關(guān)于Dijkstra算法我的理解(上) 2009-07-29 18:05 kfue
            dd  回復(fù)  更多評論
              

            # re: 關(guān)于Dijkstra算法我的理解(上) 2009-07-29 18:05 kfue
            非常好
              回復(fù)  更多評論
              

            # re: 關(guān)于Dijkstra算法我的理解(上) 2009-08-14 20:37 D.K.
            頂你  回復(fù)  更多評論
              

            # re: 關(guān)于Dijkstra算法我的理解(上) 2009-08-31 20:27 Johnnx
            好象錯別字有些多  回復(fù)  更多評論
              

            # re: 關(guān)于Dijkstra算法我的理解(上) 2009-09-18 16:57 popo
            終于通過你這篇文章弄懂了Dijkstra算法...網(wǎng)上不少帖子,看得我不停走神
            你的文章雖然錯別字不少,但的的確確一目了然。贊一個!  回復(fù)  更多評論
              

            # re: 關(guān)于Dijkstra算法我的理解(上)[未登錄] 2009-09-20 16:58 quire
            謝謝,Johnnx,popo兩位老兄提醒,下次一定注意,但是兩位仁兄也沒指出那兒錯了!很長時間沒上CPPBLOG了,看了Johnnx的主頁,好像都是算法,看來Johnnx數(shù)據(jù)結(jié)構(gòu)研究的蠻多,還望賜教!  回復(fù)  更多評論
              

            # re: 關(guān)于Dijkstra算法我的理解(上) 2010-08-20 22:29 ri
            完全就不通順  回復(fù)  更多評論
              

            久久这里只有精品首页| 久久中文字幕人妻熟av女| 久久亚洲精品国产精品婷婷| 欧美伊人久久大香线蕉综合69 | 99久久精品国产免看国产一区| 欧美噜噜久久久XXX| 久久福利青草精品资源站免费| 久久精品二区| 久久水蜜桃亚洲av无码精品麻豆| 久久91精品国产91久久户| 久久综合久久性久99毛片| 99久久综合国产精品二区| 国产精品久久久久久久人人看 | 97久久久久人妻精品专区| 天堂无码久久综合东京热| 奇米综合四色77777久久| 久久久青草青青国产亚洲免观| 久久这里只有精品18| 97精品伊人久久久大香线蕉| 国内精品久久久久影院免费| 亚洲国产成人久久笫一页| 成人精品一区二区久久久| 浪潮AV色综合久久天堂| 综合久久一区二区三区 | 久久久久国产成人精品亚洲午夜| 国内精品伊人久久久久AV影院| 18岁日韩内射颜射午夜久久成人 | 婷婷国产天堂久久综合五月| 国产成人久久久精品二区三区| 久久精品国产清高在天天线| 久久久噜噜噜久久中文福利| 久久久一本精品99久久精品88| 色青青草原桃花久久综合| 精品国产婷婷久久久| 狠狠色丁香久久婷婷综合蜜芽五月 | 欧美麻豆久久久久久中文| 国内精品久久久久国产盗摄| 亚洲国产精品热久久| 99国产欧美久久久精品蜜芽| 国内精品久久久久影院优| www性久久久com|