国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

采用矩陣+深度優先算法解決迷宮問題

yankeys / 2987人閱讀

摘要:所謂深度優先算法,百科的解答是這樣的深度優先搜索算法,簡稱是搜索算法的一種。是沿著樹的深度遍歷樹的節點,盡可能深的搜索樹的分支。這一過程一直進行到已發現從源節點可達的所有節點為止。

所謂深度優先算法,百科的解答是這樣的

深度優先搜索算法(Depth-First-Search),簡稱DFS,是搜索算法的一種。是沿著樹的深度遍歷樹的節點,盡可能深的搜索樹的分支。當節點v的所有邊都己被探尋過,搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點,則選擇其中一個作為源節點并重復以上過程,整個進程反復進行直到所有節點都被訪問為止。屬于盲目搜索。

通俗的說,就是足夠“深”的遍歷樹的所有節點分支并且遍歷過的節點不會再去訪問,很適合做網絡爬蟲,你懂得^ ^

而迷宮問題也是數據結構里面一道經典的問題了,首先我們先用矩陣創建一個迷宮;

const arr = [
        [0,0,0,1,0],
        [0,1,1,1,0],
        [0,1,0,0,0],
        [0,0,0,1,0],
        [0,1,1,1,0]
    ];

其中數字1代表墻壁,數字0代表路,最左上角代表入口,最右下角代表出口,這里我們不考慮“死路”的情況

const arr = [
    [0,0,0,1,0],
    [0,1,1,1,0],
    [0,1,0,0,0],
    [0,0,0,1,0],
    [0,1,1,1,0]
];//創建迷宮

const pathX = [1,-1,0,0];//創建一個數組代表上下左右,在advance這個函數會用到
const pathY = [0,0,-1,1];//同上,區別在于矩陣的行和列
let _arrLength = arr.length-1;
let _arrElementLength = arr[0].length-1;
let i=0,j=0;
(function(){
    console.time("time")//用于測試運算時間

    arr[0][0] = 3;//數字3代表已經走過的路,一開始默認從入口進入

    function matrix(i,j){

        let k,newi,newj;

        for(k = 0;k<4;k++){ //上下左右總共四個方向

            if (advance(i,j,k)) {   
                /*
                通過advance函數的判斷返回一個可走的路的點
                */
                newi = i + pathX[k];
                newj = j + pathY[k];   
                
                arr[newi][newj] = 3;//將這個點定義為已走過的點
                
                /*
                判斷此時是否已經到了終點如果沒有則遞歸
                */
                if (newi == _arrLength && newj == _arrElementLength) {
                    end()
                } else {   
                    matrix(newi,newj);   
                }   
            }
        }
        arr[i][j] = 2

    }
    matrix(0,0)

    function advance(i,j,k){
        var bool = true;
         /*
        每走一步路就判斷其上下左右是否還有路可走
        */
        i += pathX[k];
        j += pathY[k];
        /*
        判斷臨界范圍,保證在迷宮范圍內
        */
        if(i<0||i>_arrLength||j<0||j>_arrElementLength){
            bool = false;
        }else if(arr[i][j]!=0){
            bool = false;
        }
        return bool;
    }


    /*
    負責輸出結果
    */
    function end(){
        let i,j,newArr=[];
        for (i = 0; i < _arrLength+1; i++) {   
            for (j = 0; j < _arrLength+1; j++) {   
                if (arr[i][j] == 3) { 
                    newArr.push("V");  
                } else {   
                    newArr.push("*");   
                }
            }   
        }
        /*
        下面這段代碼只是為了能夠在控制臺看得更直觀,可無,因為寫得有點笨拙
        */
        newArr.splice(0,0,"")
        newArr.splice(6,0,"
");
        newArr.splice(12,0,"
");
        newArr.splice(18,0,"
");
        newArr.splice(24,0,"
");
        console.log(newArr.join(" "));
    }
    console.timeEnd("time")
})()

最終的路線圖如下

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/81299.html

相關文章

  • 采用矩陣+深度優先算法解決迷宮問題

    摘要:所謂深度優先算法,百科的解答是這樣的深度優先搜索算法,簡稱是搜索算法的一種。是沿著樹的深度遍歷樹的節點,盡可能深的搜索樹的分支。這一過程一直進行到已發現從源節點可達的所有節點為止。 所謂深度優先算法,百科的解答是這樣的 深度優先搜索算法(Depth-First-Search),簡稱DFS,是搜索算法的一種。是沿著樹的深度遍歷樹的節點,盡可能深的搜索樹的分支。當節點v的所有邊都己被探尋過...

    bang590 評論0 收藏0
  • 算法(第4版) Chapter 4.1 無向圖

    摘要:邊僅由兩個頂點連接,并且沒有方向的圖稱為無向圖。用分隔符當前為空格,也可以是分號等分隔。深度優先算法最簡搜索起點構造函數找到與起點連通的其他頂點。路徑構造函數接收一個頂點,計算到與連通的每個頂點之間的路徑。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter...

    kamushin233 評論0 收藏0
  • 回溯算法

    摘要:回溯算法主要思想回溯算法的基本思想是從一條路往前走,能進則進,不能進則退回來,換一條路再試。回溯算法說白了就是窮舉法。回溯算法也叫試探法,它是一種系統地搜索問題的解的方法。用回溯算法解決問題的一般步驟為定義一個解空間,它包含問題的解。 回溯算法 主要思想 回溯算法的基本思想是:從一條路往前走,能進則進,不能進則退回來,換一條路再試。八皇后問題就是回溯算法的典型,第一步按照順序放一個皇...

    ctriptech 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<