洗涤并重复
这只是引导探索,如果你运气不好,整体复杂度仍然很高。
直觉上,现在最好去出口较少的区域,因为以后回到这些区域会更加困难。有一个只有1个出口的2个单元格规则,这只是一种优化,但它可以修剪大的子树,这是好的。根据测试放置的位置,如果检测到未访问的0个出口的单元格,则还可以进行回溯。
即使在比经典的8x8更大的棋盘上,我也能轻松地用这个启发式方法找到很多解决方案。
我已经实现了类似于这里的东西来解决一个名为“骑士之旅”的难题。我相信这个问题应该涉及相同的逻辑,只需要进行一些小的修改。
与其谈论遍历,不如让我们更普遍地考虑——从任何给定点开始,回答“下一步最好的移动是什么?”这个问题,你需要再思考一步,并问:“最具限制性的因素是什么?”在这种情况下,根据你的下一个可用移动,最具限制性的因素是每个移动可用的移动次数。每个你的下一个可用移动都将有自己的下一个可用移动集合。拥有最少数量的自己的下一个可用移动的下一个可用移动是你最具限制性的因素。
例如,假设我有可用的移动x、y和z。x和z都有2个下一个可用移动,而y有3个下一个可用移动——你想要移动到x或z(你可以像我在代码中所做的那样随机选择其中一个,这并不重要)。
为什么这是有意义的?换个角度思考——我们示例中的下一个可用移动(x、y和z)都是你必须在某个时刻到达的位置!对于x、y和z的下一个可用移动也可以被认为是你回到x、y或z的方式。由于回到x和z的方法较少,因此最好现在就去其中一个。例如,如果x只有1个下一个可用移动(其他条件不变),那么x将是您唯一有效的选择(并且作为优化,您可以立即转到x的下一个可用移动,因为您知道只有1个)。getPossibleMoves
、getAvailableMoves
和getBestNextMove
(以及这些函数调用的任何函数)。在getPossibleMoves
函数中的插值点内容与D3相关,不是你需要担心的事情。该函数仅根据马走棋的规则计算出从一个点(具有x和y属性)开始所有可能的移动,然后简单地评估每个点以查看它们是否在边界内。修改此函数以适应你的机器人允许的移动应该不会太难,你还需要更新检查点是否在边界内的函数,以禁止存在墙壁的点。void explore(Node position)
{
position.visited = true
while(position.hasUnvisitedDirection())
{
//random unvisited direction
int direction = position.getDirection();
if(direction == WEST && !west(node).visited && !position.westWall)
explore(west(node));
if(direction == EAST && !east(node).visited && !position.eastWall)
explore(east(node));
if(direction == SOUTH && !south(node).visited && !position.southWall)
explore(south(node));
if(direction == NORTH && !north(node).visited && !position.northWall)
explore(north(node));
}
}
在这里,我们对DFS进行修改,每次访问一个位置时选择一个随机未访问的位置。 east(Node)
,north(Node)
等调用将返回传递的节点东、北方向的位置,请注意网格中的边缘情况(如果您将图形建模为2D数组,则相当直观)。
接下来,我们想要检查图是否只有一个强连通分量,如果在DFS中只有一个跳跃,则是这种情况,即深度优先搜索森林中只有一棵树,并且可以从起始位置到达每个位置,这正是您想要的结果。否则,在运行DFS后未被访问的节点将是无法访问的,您可以在之后检查这些位置以查看算法是否返回false。因此,以下内容应该能够实现此目的:
boolean isConnected(Graph g, Node startPosition)
{
int jumps = 0;
for (Node node : g.nodes())
{
if(!node.visited)
{
jumps++;
if(jumps > 1) return false;
else explore(position);
}
}
return true;
}