广度物体的第一次遍历

我正在制作一个解决益智游戏的程序，它可以找到棋盘上所有可能的棋步，并将所有可能的棋盘放在一个物体中。然后找到所有可能的棋盘棋步，等等。对象将是这个样子：广度物体的第一次遍历

{ 
    "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

广度物体的第一次遍历

回答

相关问题