廣度物體的第一次遍歷

我正在製作一個解決益智遊戲的程序，它可以找到棋盤上所有可能的棋步，並將所有可能的棋盤放在一個物體中。然後找到所有可能的棋盤棋步，等等。對象將是這個樣子：廣度物體的第一次遍歷

{ 
    "board": { 
     "starts": [[0,0],[0,3]], 
     "blocks": [[3,0],[3,3]], 
     "ends": [[2,4]] 
    }, 
    "possibleMoves": [ 
    { 
     "board": { 
     "starts": [[0,0],[2,3]], 
     "blocks": [[3,0],[3,3]], 
     "ends": [[2,4]] 
     }, 
     "possibleMoves":[ 
     { 
      "board": {}, 
      "possibleMoves": [{}] 
     } 
     ] 
    }, 
    { 
     "board": { 
     "starts": [[0,3]], 
     "blocks": [[3,0],[3,3]], 
     "ends": [[2,4]] 
     }, 
     "possibleMoves":[{}] 
    }] 
}

我可以計算出如何從頂層板添加可能的行動，但在第二個層面我無法通過的所有結果板弄清楚如何循環和找出他們可能的動作，然後循環遍歷所有的三層板等等。如何使用廣度優先搜索添加可能的移動和遍歷對象？

來源

2011-03-23 Peter Olson

你可能想在這裏做一個「遞歸」和「遞歸函數」的搜索，一般來說網絡應該是豐富的信息。 – prodigitalson 2011-03-23 20:40:59

你是否熟悉遞歸？ – climbage 2011-03-23 20:41:22

遞歸。

function traverse(state) { 
    handle(state.board); 
    if (state.possibleMoves) { 
     $.each(state.possibleMoves, function(i, possibleMove) { 
      traverse(possibleMove); 
     }); 
    } 
}

編輯：對於廣度優先搜索，嘗試這樣的事情。它不使用遞歸，而是遍歷不斷增長的隊列。

function traverse(state) { 
    var queue = [], 
     next = state; 
    while (next) { 
     if (next.possibleMoves) { 
      $.each(next.possibleMoves, function(i, possibleMove) { 
       queue.push(possibleMove); 
      }); 
     } 
     next = queue.shift(); 
    } 
}

來源

2011-03-23 20:41:52

第二個想法是，這不是處理第一個層次，然後遍歷第二個層次的第一個板子，處理它，然後遍歷第三個層次的第一個板子，依此類推？我希望它能夠處理第一塊板，然後遍歷第二層中的所有板，然後開始處理第三層中的任何東西。 – 2011-03-29 13:42:22

沒錯。在這種情況下，你需要實現一個隊列。我向你展示的是深度優先遍歷。你想要廣度優先遍歷。查看http://en.wikipedia.org/wiki/Breadth-first_search獲得體面的算法。 – 2011-03-31 23:13:52

好的。我想我並不清楚我想要什麼。我修改了這個問題。 – 2011-04-01 03:16:43

不完全測試：

var oo = { 
    board: { 
     starts: [[0,0],[0,3]], 
     blocks: [[3,0],[3,3]], 
     ends: [[2,4]] 
    }, 
    possibleMoves: [{ 
     board: { 
      starts: [[0,0],[2,3]], 
      blocks: [[3,0],[3,3]], 
      ends: [[2,4]] 
     }, 
    }], 
}; 


function traverseObject (o) { 
    for (var prop in o) { 
     if (typeof o[prop] == "array" || typeof o[prop] == "object") { 
      traverseObject(o[prop]); 
      console.log(prop); 
     } else { 
      console.log(prop, "=", o[prop]); 
     } 
    } 
} 

traverseObject(oo);

來源

2011-03-23 20:45:41

我沒有JavaScript的描述，但我一般會通過保持未知節點的隊列中做到這一點。

從只有隊列中的根節點開始。
從隊列的前面彈出一個項目
探索其添加的勘探過程中發現的隊列
支票背面節點是否有如果有回到步驟的隊列中的任何節點2
你做

還有就是維基百科頁面上的一些僞足，以及一些更多的解釋 HERE

而且快速谷歌搜索出現了一個類似的算法，可以彎曲你的目的 HERE

來源

2011-04-02 07:48:40 Hugoagogo

廣度物體的第一次遍歷

回答

相關問題