遍历所有可能的移动

我有一个Puzzle对象，它有一个{1,2,3}的数组和一个表示目标{3,3,0}的数组，以及一个移动函数，它带有两个整数i & j并将其应用于阵列。

现在我正在尝试为此编写一个求解器。因此，我们的想法是，我们将所有可能的值应用于i & j，并继续应用它直到获得所需的目标。

我正在尝试使用递归方法来处理这个问题，但我无法理解的是如何阻止我的递归进入不同的方式，并找到让我到达目标的最佳“移动集”。

所以可能的移动列表：

（0，1），（0，2），（1，0），（1，2），（2，1），（2,0）

在每一次这些举动后，我们得到一个新的“金额数组”，我们需要将这些举动应用到那个，并检查它们中是否有任何结果在“目标数组”。

所以我的伪代码：

solve(puzzle): 
    if puzzle.isSolved: return true; 
    else: 
     solve(puzzle.move(0, 1)); 
     solve(puzzle.move(0, 2)); 
     solve(puzzle.move(1, 0)); 
     solve(puzzle.move(1, 2)); 
     solve(puzzle.move(2, 0)); 
     solve(puzzle.move(2, 1));

我们假设puzzle.move函数返回新状态的谜题。

现在我确信我在这里做了一些可怕的错误..但我似乎无法把它放在手指上。所以任何想法/提示/指针将不胜感激。

谢谢。

编辑

好了，所以几件事情让这个大家更加清晰：

由于puzzle.move应用在移动后返回的困扰，我想创建一个新的难题，这样的递归经历了这一点。基本上，需要发生的是在每次移动之后，我们将有一个新的数组数组状态。（a，b，a，c）的初始量为（a，b，c）的谜题有一个量（a = a，b + a，c）。我们比采取这个新的数组数组并应用下一步（i = 0，j = 2）等等。

但这只是“树”的一部分，还有另外一条需要检查的路径，即当我们对最初的数量应用移动（i = 0，j = 2），然后从那里继续。

希望这有助于:)

顺便说一句，这是问题被称为水壶问题（http://www.cut-the-knot.org/ctk/Water。SHTML）

来源

2011-11-04 Obaid

我不真正了解你正在试图解决这一难题，但我不认为重要

有一些可怕的错误 - 你只当你得到一个正解停止，但你也需要阻止它永远递归到非解决方案。

想想这段代码会做的一系列步骤：

// Solve puzzle 
Is puzzle solved? No. 
Move puzzle 0,1 
// Solve puzzle 
Is puzzle solved? No. 
Move puzzle 0,1 
// Solve puzzle 
Is puzzle solved? No. 
Move puzzle 0,1

除非0,1 .. 0,1 .. 0,1 ..确保最终能够解决这一难题的招式，那么这个算法将永远不会结束。

您可能需要

找到一个方法来制定出一个举动是否具有“改良”的困扰，
有一些截止的当某个解决方案显然是行不通的。

来源

2011-11-04 04:35:49 Tim

感谢您的评论。我将尝试解释更多（在我的原始线程中，希望这也能帮助你）:) – Obaid

您试图将solve（puzzle.move）作为递归函数，因此解决方案必须负责确定要解决的新参数是什么。问题是，如果你通过拼图来解决问题，就没有办法解决从先前的调用中推断出i和j的值（除非拼图存储它们）。我建议传递i和j的值，然后在调用递归解决之前调用puzzle.move。

solve(puzzle, i, j): 
    if solve(puzzle.move(i, j)): return true; 
    else: 
     j++; 
     if (j == i) 
     j++; 
     if (j > MAX) 
     j = 0 
     i++; 
     if (i > MAX) 
     return false; 
     solve(puzzle, i, j);

不过，我认为这是值得一提的是，可以用递归来解决任何问题都没有递归调用，所以让我们看看本想什么模样了：

i = 0; 
j = 1; 
solved = false; 
while (!solved && i <= MAX) 
    while (!solved && j <= MAX) 
     solved = puzzle.move(i, j); 
     j++; 
     if (j == i) 
      j++; 
     if (j > MAX) 
      j = 0 
      i++;

这里，该代码稍微简单一些，它可以避免所有额外的调用（这会消耗有限的堆栈空间） - 建议。

来源

2011-11-07 13:43:10

遍历所有可能的移动

回答

相关问题