问题标签 [backtracking]

我有一个字符串向量，大小都一样。
我必须构建一个满足某些条件的字符串列表作为解决方案。

伪代码算法将是这样的：

我迷失了如何实际编写代码。

我不明白如何保存当前的解决方案，将什么样的参数传递给函数......

这是我所拥有的东西，尽管我认为这是完全错误的：

}

问题是解决方案在不受控制的情况下不断增长。你能告诉我如何处理它吗？并进行适当的回溯？

我有这个问题，我需要解决递归回溯问题。它看起来很像 n-queen 问题，但不同之处在于它使用具有非对称板的不同候选人。总共有四个不同的候选人，每个候选人都相互依赖。我有 2 个 A、2 个 K、2 个 Q 和 2 个 J。每个王牌必须靠近（水平或垂直）国王，每个国王必须靠近皇后，每个皇后必须靠近杰克，并且任何棋子旁边都不能有重复。具有正确解决方案的电路板如下所示：

现在我的问题是我想使用一棵树来跟踪作为树的父母和孩子的候选人。我还没有实现树，但我想知道这个例子中显示的方法是否是创建树的好方法。如果这是创建树的好方法，我该如何开始，树如何知道它应该在孩子身上找到哪个父母，并在解决方案不适合时返回？

我希望我已经添加了有关这种情况的足够信息，在此先感谢。

我正在写一个数独求解器。自从我接触 prolog 已经很长时间了，因此我不记得关于统一、回溯等的所有内容。我认为我导致系统永远回溯（但我没有得到任何堆栈异常 - 至少没有立即地）。这是我到目前为止所拥有的（这个谜题可以在http://en.wikipedia.org/wiki/File:Sudoku-by-L2G-20050714.svg找到）：

该行allunique(C1)导致问题。系统似乎将 7 放在第一列的第一个空框中，并且永远不会更改它（或者至少在不久的将来不会更改）。一个示例 C1 列表是[5, 6, 7, 8, 4, 7, 9, 8, 6]. 我很想知道为什么会这样。

我得到了一组称为“字典”的字符串，它存储为一个字段，代表一个单词字典。

我要编写一个方法，它接受一个字符串参数（“短语”）并返回一个集合，其中包含字典集中的所有单词，这些单词可以通过重新排列给定短语中的字符来实现。基本上我正在字典中搜索字谜。

这是我的代码：

所以我的方法是： 1. 检查字典中在这个线程中传递的可能性，由变量“chosen”表示。

1. 如果字典确实包含这种可能性，请将其添加到调用结束时返回的名为“anagrams”的集合中。然后再次传递可能性以尝试从中做出其他组合。

3.. 如果字典中不包含该可能性，则修改字符串尝试其他可能性，然后递归测试。

上面的代码会产生一个“堆栈溢出错误”，我的研究表明这意味着我正在执行无限递归，或者无限地一遍又一遍地传递相同的字符串。不过，我看不到我在哪里做这个。你能？

我的回溯函数有问题，它会循环某些数据，我不能在这里写整个程序代码，但可以把我的函数放在这里。

现在解释一下：

quantity - values
中 的 元素
数指数组值

该函数获取长度为 values 数组的元素的数量，values 一个包含数字的数组，从最高到最低排序，索引控制递归，默认为 0，因此它从第一个元素开始，moneyA 存储数字的变量值数组，它应该达到一半，这是从值数组求和的数字的一半，并且 ifChosen 存储选择的数字。

整个函数执行此操作，它对 values 数组中的元素求和并检查它是否达到一半，如果它低于一半，则将其添加到 moneyA 并在 ifChosen 中标记，然后它转到下一个，如果总和高于它的一半取回并在 ifChosen 数组中取消标记它并从 moneyA 中减去。它应该总是得到最高的元素。

这是一个简单的例子：

这个结果应该是：

当然，对于这个简单的示例，它做得很好，但是对于具有更多数字并且一个数字不止一次出现的更复杂的示例，它循环并且递归永远不会停止。我实际上已经为此工作了 1.5 周，并询问了我所有的朋友，但没有人知道它有什么问题。我知道这与背包问题有点关系，但我还没有那个问题，仍然需要学习。

我期待任何可以提供帮助的答案。

我很抱歉我的标点符号，但我是第一次来这里，不习惯格式化。

这里有一个例子：

现在我认为它会永远循环：43 个元素：

@Karl Bielefeldt 是的，我知道有很多组合，这就是我试图加快速度的原因。现在这就是我所得到的，但它给我某些输入的错误结果。任何人都可以纠正它，它比以前工作得更快吗？

我正在尝试制作一个程序，它可以通过一个名为“Knight's Tour”的骑士（大小并不重要，但现在它是 6x6）的所有方格，请在 wiki 上查看。

游览应该是关闭的，这意味着最后访问过的广场上的骑士可以“攻击”他开始的广场。该代码适用于某些方块，例如，在 main 中输入“traverse(1,1,1)”会生成输出，该输出不仅显示他正在遍历，而且还回溯并返回成功地遍历目标。但是，如果我输入 'traverse(1,0,0)' ，我会得到一个StackOverflowError。由于它有时是成功的，回溯和遍历，我知道代码有效，我只是不知道如何摆脱错误。我假设我打了太多电话，但我不知道如何解决这个问题，有很多方块可以访问:) 编辑了代码，主要是因为老师会发现它说我作弊。

嘿，我正在构建一个生成迷宫的程序，以便稍后将路径转换为我的图形部分。我的大部分工作都在工作，但是，每次你只要走东线和南线，你就会到达终点。即使我将宽度设置为 64，因此迷宫是 64*64，我也可以选择这 2 个选项并每次都到达终点。我真的不明白它为什么这样做。代码如下，很容易理解。

正如你所看到的，我认为问题出在我生成迷宫的地方，但是，当我让它直到当前点结束时，它并没有填满每个迷宫，通常只是一条笔直的路径. 感谢您的帮助。

更新：我已将生成迷宫的 for 循环更改为简单的 while 循环，它似乎工作得更好。似乎当 for 循环运行时，它并没有递归地运行，但是，在 while 循环中它完全没问题。但是，现在所有的方块都没有填写。

我寻求是否有人可以帮助我解决我的房间搜索算法
我正在尝试实现一个回溯算法来解决迷宫问题。我被困在我应该记住我已经访问过的房间的地方。
迷宫由房间组成，每个房间有 4 个面——北、东、南和西。每个房间都通过在所需一侧制作一扇门连接到下一个房间，即room1.createNorth(roomName) 在北边创建一个新房间，一个新房间有南门连接回第一个房间，正如您在我的 Room 课程中看到的那样。

这是我切碎的房间类，它代表迷宫中的每个房间。我删除了与我处理北侧的方法相同的南、西和东方向。

迷宫看起来像这样：http: //i.stack.imgur.com/2KePs.jpg其中 S 是起点

我的迷宫课

这是我的主要课程 public class Main {

问题出在我的findPathTo(roomName)方法中，它找到了通往房间的路线。如果我进入房间 D4，那么我的算法只会从“A4”向东移动一次到“B4”房间，然后它会无限循环，堆栈只会随着房间“B4”而增长。为什么它不前进到下一个房间“B3”或“C4”？

编辑：这是工作代码

基本上，我有这个：首先，一堆代码生成一个不可穿越的迷宫。它根据一些参数在二维数组的某些空间中随机设置墙壁。然后我有一个回溯算法通过它来敲掉墙壁，直到整个东西都可以遍历。问题是，程序似乎并没有回到堆栈中。

这是非常标准的回溯代码。该算法从一个随机位置开始，然后以伪代码进行：

move(x, y){
如果你可以往上走但还没到过：
move (x, y - 1)
如果你可以往右走但还没到过：
move (x + 1, y)
。 ..
}

其他方向依此类推。每次移动时，都会在坐标处设置两个单独的 2D 布尔数组（一个是临时的，一个是永久的），以表明您已经在某个元素中。一旦它不能继续前进，它就会检查永久二维数组，看看它是否无处不在。如果不是，它会随机选择一个在已访问空间和未访问空间之间的墙（根据临时数组）并将其移除。这整个过程是在一个while循环中调用的，所以一旦它遍历了迷宫的一大块，临时二维数组就会被重置，而另一个则保留，它会在另一个随机位置再次遍历，直到永久二维数组显示整个迷宫已经被遍历。move 方法中的检查与临时二维数组进行比较，而不是永久数组。

这几乎可行，但我一直在最终生成的迷宫中找到一些无法到达的区域。否则，它会按照我想要的方式生成迷宫。问题是，我发现这样做的原因是它不会一直回到堆栈中。

如果我将其更改为检查临时二维数组是否完成而不是永久数组（从而使其在一次运行中进行一次完整遍历以将其标记为完成，而不是在多次迭代中进行完整运行），它将继续下去等等。我必须设置一个计数器来打破它。结果是一个“迷宫”，移除了太多太多的墙壁。检查算法采用的路线，我发现它没有正确回溯，并且没有回到堆栈中足够远的距离，并且经常只是在一个元素上卡住了几十次递归，然后无缘无故地宣布自己完成根本没有拆除零的墙需要拆除。

我尝试过两次运行前面的那个，但它一直在敲掉不需要敲掉的墙壁并使迷宫变得太稀疏。我不知道为什么会发生这种情况。

编辑：为什么我是个傻瓜，请参阅下面的答案。不过，这里面还有一个谜，我很想回答。

我已经被困在这太久了。我正在尝试在漂亮的网格中打印出数独解决方案。

我想我遇到了问题，因为我不了解模式匹配在 Prolog 中如何工作的一些关键部分。

事不宜迟，我的代码：

这是电话：

这是输出：

问题是它不只是返回 true，我必须按;，然后它返回 false。这反过来又意味着我的prettier_print/1规则不能正常工作。

我想我知道的足够多，这意味着：

Prolog 正在回溯并尝试对我的规则进行另一种解释（如果我正确理解我的条款，看看是否还有其他可以统一的东西）。这找到了另一件事与之统一，但这立即失败了。是对的吗？

我希望只有一种可能的解释。我怎样才能修复我的功能意味着这个？

谢谢你的帮助，这让我觉得自己像个傻瓜！