• <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>
            隨筆 - 89  文章 - 118  trackbacks - 0
            <2012年11月>
            28293031123
            45678910
            11121314151617
            18192021222324
            2526272829301
            2345678

            留言簿(16)

            隨筆分類(56)

            隨筆檔案(89)

            文章分類

            推薦博客

            搜索

            •  

            最新隨筆

            最新評論

            閱讀排行榜

            有一個二維數(shù)組,0表示路,-1表示墻,求其中任意兩點(diǎn)的最短路徑。

            我們先看,怎么求一條路徑:求兩點(diǎn)路徑是一個數(shù)據(jù)結(jié)構(gòu)上的典型的迷宮問題,很多數(shù)據(jù)結(jié)構(gòu)的書上都有介紹,解決辦法如下:

            從一點(diǎn)開始出發(fā),向四個方向查找,每走一步,把走過的點(diǎn)的值+1(即本節(jié)點(diǎn)值+1),防止重復(fù)行走,并把走過的點(diǎn)壓入堆棧(表示路徑),如果遇到墻、或者已走過的點(diǎn)則不能前進(jìn),如果前方已經(jīng)無路可走,則返回,路徑退棧,這樣遞歸調(diào)用,直到找到終點(diǎn)為止。

            迷宮如下圖所示:


            從(2, 1)到(6, 8),程序如下所示:

             

            struct Postion
            {
                
            int _X, _Y;

                Postion()
            {}
                Postion(
            int X, int Y)
                    : _X(X), _Y(Y)
            {}
            }
            ;

            bool isCanGo(const 
            int prePosValue,
                         const 
            int posX,
                         const 
            int posY)
            {
                
            if (   posX < 0 || posX > 9        // 越界
                    || posY < 0 || posY > 9        
                    
            || maze[posX][posY] == -1    // 墻
                    || maze[posX][posY] >= 1)    // 走過
                {
                    
            return false;
                }


                
            return true;
            }



            stack
            <Postion> path__;            //路徑
                    
            Postion offset[
            4];                //路徑

            bool shortestPath(stack
            <Postion> &path,
                              const Postion 
            &start,
                              const Postion 
            &end)
            {
                
            if (   start._X == end._X 
                    
            && start._Y == end._Y)
                
            {
                    path__ 
            = path;
                    
            return true;
                }

                
                
            for (int i = 0; i < 4; i++)
                
            {
                    
            int nNextPos_X = start._X + offset[i]._X;
                    
            int nNextPos_Y = start._Y + offset[i]._Y;

                    
            if (isCanGo(maze[start._X][start._Y], nNextPos_X, nNextPos_Y))
                    
            {
                        maze[nNextPos_X][nNextPos_Y] 
            = maze[start._X][start._Y] + 1;

                        path.push(Postion(nNextPos_X, nNextPos_Y));

                        
            if (shortestPath(path, Postion(nNextPos_X, nNextPos_Y), end))
                            
            return true;

                        path.pop();
                    }

                }


                
            return false;
            }


            int main(int argc, char* argv[])
            {
                offset[
            0]._X = -1;    offset[0]._Y = 0;    // 上
                offset[1]._X = 1;    offset[1]._Y = 0;    // 下
                offset[2]._X = 0;    offset[2]._Y = -1;    // 左
                offset[3]._X = 0;    offset[3]._Y = 1;    // 右

                printMat(maze);


                Postion start(
            21), end(68);
                maze[start._X][start._Y] 
            = 1;            // 置起點(diǎn)值1, 防止走回起點(diǎn)
                shortestPath(stack<Postion>(), start, end);

                printPath(path__);
                printMat(maze);

                
            return 0;
            }

            這時,我們經(jīng)過運(yùn)算,到達(dá)終點(diǎn),有44步之多。如果我們調(diào)整調(diào)用offset的順序,即先左右,后上下,可能會得到更短的路徑,但無法確保在任何情況下都能得到最短路徑。

            得到最短路徑的方法,解決方法如下:

            每走一步,就對前方的節(jié)點(diǎn)賦值為此節(jié)點(diǎn)+1,走過的路徑也可以重復(fù)行走。但有一個條件,就是本節(jié)點(diǎn)+1必須小于已走過的節(jié)點(diǎn)的權(quán)值(墻不能走),這樣走遍所有的節(jié)點(diǎn),記錄最短的路徑。

            主要修改了以下兩個函數(shù):

            bool isCanGo(const int prePosValue,
                         const 
            int posX,
                         const 
            int posY)
            {
                
            if (   posX < 0 || posX > 9        // 越界
                    || posY < 0 || posY > 9        
                    
            || maze[posX][posY] == -1)    // 墻
                {
                    
            return false;
                }


                
            if (maze[posX][posY] == 0)    // 未走過
                    return true;
                
            else                        // 更近的路徑
                    return (prePosValue + 1< maze[posX][posY];
            }


            void shortestPath(stack<Postion> &path,
                              const Postion 
            &start,
                              const Postion 
            &end)
            {
                
            if (   start._X == end._X 
                    
            && start._Y == end._Y)
                
            {
                    
            if (path.size() < path__.size() || path__.empty())    // 更短的路徑
                        path__ = path;
                    
            return;
                }

                
                
            for (int i = 0; i < 4; i++)
                
            {
                    
            int nNextPos_X = start._X + offset[i]._X;
                    
            int nNextPos_Y = start._Y + offset[i]._Y;

                    
            if (isCanGo(maze[start._X][start._Y], nNextPos_X, nNextPos_Y))
                    
            {
                        maze[nNextPos_X][nNextPos_Y] 
            = maze[start._X][start._Y] + 1;

                        path.push(Postion(nNextPos_X, nNextPos_Y));

                        shortestPath(path, Postion(nNextPos_X, nNextPos_Y), end);

                        path.pop();
                    }

                }

            }

             

             

            我上傳了兩個工程,求一條路徑的程序點(diǎn)此下載,求最短路徑的程序點(diǎn)此下載

            文章結(jié)束!愿它對您有所幫助。

            posted on 2008-03-18 17:47 胡滿超 閱讀(8906) 評論(4)  編輯 收藏 引用

            FeedBack:
            # re: 迷宮最短路徑問題解析 2009-02-24 11:33 胡滿超
            回復(fù):
            我想請問,如果將初始位置設(shè)為(9,9),末端位置設(shè)為(0,2),結(jié)果和設(shè)計預(yù)期有出入。這是怎么回事,怎么解決呢?
            ------------
            (9,9)點(diǎn)為墻!算法忘記判斷。  回復(fù)  更多評論
              
            # re: 迷宮最短路徑問題解析 2014-12-22 15:19 11
            。。。。。。。。  回復(fù)  更多評論
              
            # re: 迷宮最短路徑問題解析 2016-04-16 20:09 rover
            stack<Postion> path__;
            這個里面 ”<> “符號是什么意思?我在C++語言里面沒見過呢? 初學(xué)者,大神勿噴。  回復(fù)  更多評論
              
            # re: 迷宮最短路徑問題解析 2016-05-03 13:05 胡滿超
            @rover
            這個是C++模板  回復(fù)  更多評論
              

            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            久久久久亚洲AV无码网站| 国产99精品久久| 久久久久久久综合日本| 伊人久久成人成综合网222| 亚洲国产综合久久天堂| 亚洲va久久久噜噜噜久久男同| 久久亚洲精品无码AV红樱桃| 久久精品成人国产午夜| 天天影视色香欲综合久久| 国产三级久久久精品麻豆三级 | 国产精品99久久免费观看| 人妻少妇久久中文字幕| 99热成人精品免费久久| 亚洲国产成人久久综合区| 99久久中文字幕| 久久无码中文字幕东京热| 国产精品久久久福利| 久久中文字幕人妻丝袜| 久久香蕉国产线看观看99| 久久大香萑太香蕉av| 91精品日韩人妻无码久久不卡| 女人高潮久久久叫人喷水| 久久综合久久综合久久| 色狠狠久久AV五月综合| 香蕉久久影院| 三级韩国一区久久二区综合 | 久久精品亚洲AV久久久无码| 久久青青草原国产精品免费 | 88久久精品无码一区二区毛片| 久久久亚洲欧洲日产国码是AV| 一本伊大人香蕉久久网手机| 久久免费的精品国产V∧| 伊人久久精品无码av一区| 99久久这里只精品国产免费| 久久久久久久综合日本| 狠狠人妻久久久久久综合| 免费观看成人久久网免费观看| 久久电影网一区| 国产巨作麻豆欧美亚洲综合久久| 亚洲国产精品久久| 激情久久久久久久久久|