问题标签 [recursive-backtracking]

不久前，作为概念证明（并且因为我和自闭症儿子一起使用 Logo），我在 Logo 中编写了一个程序，使用回溯方法在图中（如果存在）找到哈密顿回路。我使用的基本回溯模式是：

你可以在这里看到一个讨论。OUTPUT我可以在 Logo 中轻松地做到这一点，因为它允许使用命令从函数中获得多个退出点。

但是，Racket 不允许多个退出点（至少，不容易）。所以我希望指出一些材料的方向，这些材料可以解释（a）如何管理一个函数的多个退出点（我有一个模糊的概念，我可以用延续来做到这一点，如let/ec）或（b）如何以更适合该语言的方式管理 Racket 中的递归回溯。

作为 Racket 的新手，我相信这可以由专家在眨眼间完成，甚至可以由比我更初级的任何人完成。但现在我为自己感到困惑。谢谢！

因此，可以说迷宫已经由算法生成。你怎么知道迷宫的起点和终点在哪里？因为一开始，你选择了一个随机的单元格，而算法完成后你不知道迷宫在哪里结束

我正在尝试为和谐的图形着色编写回溯算法（相邻颜色不能相同，并且每对颜色只能出现一次）。这是回溯功能：

}

检查是否正常工作以及所有其他事情。问题是输出是错误的 - 最后它显示如下：

1 4 2 6

2 5 7 8

3 6 4 8 <--- 这是错误的

1 7 3 0 <--- 这也是错误的

因此，当它在当前树中找不到解决方案时，它只会结束一切而不是向上。为什么会这样？

我有几组任务，每组都是一个任务链，组是相互独立的。组内的任务只能按照该组的链确定的顺序进行处理。

每个任务都有一个 ID 和一个成本。任务是原子的，它们只能通过投入与其成本相等的时间单位一次完成（不可能解决一半的任务）。在每个步骤的开始都有m可用的时间单位。

我想检查是否可以在给定的步骤数内完成所有任务d。

这里有一些图片来说明情况，每个任务都是一个2元组（ID，Cost），链中的任务只能从左到右解决。

这是 6 个任务分为 3 组的图形示例：

假设m = 5（每个步骤中有 5 个可用的时间单位）和那个d = 4（我们想检查是否所有任务都可以在 4 个步骤内完成）。一个可能的解决方案是：

另一种可能的解决方案是：

一个无效的解决方案是（它在 5 个步骤中完成所有任务，我们说限制是 4）：

我的问题：

对于给定：

• 分组的任务
• m每一步都有多个可用的时间单位
• 以及一些d允许的步骤

确定是否可以解决d步骤中的所有任务，如果可以，则输出一个可能的序列（任务 ID），其中可以解决任务以<= d完成步骤。

我目前的做法：

我试图通过回溯找到解决方案。我创建了一个双端队列列表来对组进行建模，然后查看集合 A（在当前步骤中可以解决的所有任务，每个组的最左侧元素）并找到所有子集 B（A 的子集，其总和为成本是<= d并且不能添加其他任务以使成本总和保持不变<= d）。集合 B 的子集代表我在当前步骤中考虑解决的任务，现在每个子集代表一个选择，我对它们中的每一个进行递归调用（以探索每个选择），其中我传递了 B 中没有元素的双端队列列表（我将它们从双端队列中删除，因为从现在开始我认为它们在这个递归分支中解决了）。一旦递归深度达到，递归调用就会停止> d（超出了允许的步骤数）或找到了解决方案（双端队列列表为空，所有任务均已在<= d步骤内解决）。

伪Javaish代码：

我在尝试正确实施时迷失了方向，您如何看待我的方法，您将如何解决这个问题？

笔记：

这个问题非常普遍，因为许多调度问题（m机器和n优先级受限的作业）可以简化为这样的问题。

给定初始网格和单词（单词可以多次使用或根本不使用），我需要解决填字游戏。

初始网格如下所示：

这是一个示例单词列表：

任务是填充占位符（长度> 1的水平或垂直），如下所示：

任何正确的解决方案都是可以接受的，并且保证有解决方案。

为了开始解决问题，我将网格存储在 2-dim 中。char 数组，我将单词按它们的长度存储在集合列表中：List<Set<String>> words，以便例如长度为 4 的单词可以通过words.get(4)

然后我从网格中提取所有占位符的位置并将它们添加到占位符列表（堆栈）中：

该算法的主要部分是solve()方法：

函数fill(c, word, pl)只返回一个新的填字游戏，当前单词写在当前占位符pl上。如果word与pl不兼容，则函数返回 null。

这是Rextester的完整代码。

问题是我的回溯算法效果不佳。假设这是我的初始网格：

这是单词列表：

我的算法会将单词pain垂直放置，但是当意识到这是一个错误的选择时，它会回溯，但是到那时初始网格已经改变并且占位符的数量将会减少。您认为该算法如何修复？

我最近被分配了一个问题，归结为在给定矩阵中找到最长的路径，如果相邻值小于当前单元格，则两个单元格相邻。我一直在扯我的头发试图弄清楚，所以我将非常感谢任何帮助。但是，正如我所说，这是一项家庭作业，因此非常欢迎提出建议和提示（但尽量不要让我觉得太容易）。

这是我的代码的最新版本：

基本上，它首先收集一个输入矩阵，然后从第一个单元格开始（一旦我让整个工作正常，它将遍历每个单元格），调用搜索函数，检查相邻单元格是否有效，然后调用再次搜索。如果已检查所有四个方向，则回溯。当前路径正在列表中跟踪path。我的问题似乎主要在回溯部分。但是，我不确定如何前进。这段代码目前几乎无法编译，因为我一直在尝试很多不同的东西。在这一点上，我想喘口气，真正明白我在做什么。

早些时候，我尝试生成一个邻接列表，并从中构建路径，但回溯选项似乎更有希望。典型的输入如下所示：

表示一个 5x5 矩阵。预期输出为 25 (25->24-> ... 2->1)。请让我知道是否有任何其他信息会有所帮助。任何建议/提示将不胜感激！谢谢。

编辑：原来的问题被颠倒了（即两个单元格是 adj iff 邻居有一个严格较低的值。这两个问题是等价的，对吗？）

编辑 2：我对代码进行了一些更改，我认为我更接近了。它现在给出这个输出：

我替换了上面的代码以反映这些变化。它似乎非常接近，但不是完全正确的答案，即似乎找到了路径，但长度不正确。

你需要爬一个有 n 个台阶的楼梯，你决定通过跳上台阶来做一些额外的锻炼。一次跳跃最多可以走 k 步。返回你爬楼梯的所有可能的跳跃序列，排序。

我的实现显然给了我错误的答案。

对于 n = 4 和 k = 2，输出应为

实际输出：

有人可以指出我缺少哪一部分吗？

我试图理解回溯，但我陷入了这个问题，提示如下：

给定一组不同的整数，返回所有可能的子集。

示例输入：[1,2,3]

示例输出：[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

这是我的代码：

当我返回时，res我得到一个 size 的空列表列表2^(len(nums))，这是正确的大小，但数字不存在。temp但是，在我之前打印res.append(temp)表明 temp 输出正确。

例如

res = [[], [], [], [], [], [], [], []]

打印语句：

[] [1] [1, 2] [1, 2, 3] [1, 3] [2] [2, 3] [3]

为什么更改没有延续到res列表中？

编辑1：

这个解决方案有效，有什么区别？

我在构建一个随机矩阵时遇到了一个问题，其中我部分已经有了值（需要保持固定 - 所以那里没有进一步的随机化）。

让我们来看看：

矩阵最终应该是 10 x 10

我确实希望我的第一行是我输入的数据。例如：

为了对具有 10 行（和 10 列）的矩阵进行 bild，我将这些行与样本组合在一起（不替换，因为我希望每个数字在每一行中都是唯一的）。

输出：

到目前为止一切顺利.. 但是现在我遇到的问题是无法控制列中的唯一数字。这是我需要的。我之所以会出现这种情况是因为我使用了 rbind （因此只有不重复的功能仅适用于行）。但我不知道如何解决这个问题。第 1-3 行应该保持原样。

有任何想法吗？

语法 S -> a S a | aa 生成所有偶数长度的 a 字符串。我们可以为这个语法设计一个带有回溯的递归下降解析器。如果我们选择先通过产生式 S -> aa 展开，那么我们将只识别字符串 aa。因此，任何合理的递归下降解析器都会首先尝试 S -> aSa。

证明这个递归下降解析器可以识别输入 aa、aaaa 和 aaaaaaaa，但不能识别 aaaaaa。