4

我正在制作一个解决益智游戏的程序，它会在棋盘上找到所有可能的动作，并将所有可能的棋盘放在一个对象中。然后它会为结果板找到所有可能的移动，依此类推。该对象将如下所示：

{
  "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":[{}]
    }]
}

我可以弄清楚如何从顶层板上添加可能的移动，但我无法弄清楚如何循环遍历第二层中的所有结果板并找出它们可能的移动，然后遍历所有第三层板等等。如何使用广度优先搜索添加可能的移动并遍历对象？

4

3 回答 3

21

递归。

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-23T20:41:52.257 回答
2

未完全测试：

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-23T20:45:41.317 回答
1

我没有 JavaScript 描述，但我通常会通过保留未探索节点的队列来做到这一点。

  1. 仅从队列中的根节点开始。
  2. 从队列的前面弹出一个项目
  3. 探索它将探索期间找到的所有节点添加到队列的后面
  4. 检查队列中是否有任何节点，如果有返回步骤2
  5. 你完成了

维基百科页面上还有一些伪足以及更多解释 这里

快速的谷歌搜索也发现了一个类似的算法，可以满足你的目的 这里

于 2011-04-02T07:48:40.547 回答