问题标签 [recursive-backtracking]

我在 Python 中有一个基本问题，我必须验证我的回溯代码是否找到了一些解决方案（我必须找到 1 到n具有属性的数字的所有子列表|x[i] - x[i-1]| == m）。如何检查是否有解决方案？我的意思是我找到的潜在解决方案，我只是打印它们而不是将它们保存到内存中。如果没有解决方案，我必须打印正确的消息。

我知道关于这个话题有很多问题。事实上，我正在寻找其他问题，并尝试使用一些解决方案，但这还不够。

我必须做一个模拟puffball的程序，使用回溯，现在我正在开发动作，当我移动时，我需要保存表格，因为这是一个可能的解决方案，所以问题是下一个：当我尝试保留表第一个保存正确，但添加下一个并覆盖较早的。我向您展示了代码，它不是全部，只有我认为对大家有用的方法和其他信息。

在 main() 中你可以看到我是如何获取所有信息的，然后当我开始玩时，我调用了 soplarBola()，在这里你可以看到问题所在。

对不起，因为都是西班牙语。我希望你能理解我的缺陷。

非常感谢！

我创建这个新线程而不是仅仅阅读之前给出的这个特定问题的答案的原因是我觉得我只是不完全理解它背后的整个想法。我似乎无法理解整个回溯的概念。所以我需要充分理解回溯，然后解决特定的数独问题。

到目前为止，我所理解的是，回溯是一种返回的技术，在（例如）递归流程中，如果人们发现在当前状态之前做出的决定导致了死胡同。所以你回去试试别的，然后再继续。

因此，在我的数独示例中，我选择了第一个空单元格并尝试从 {1...9} 中填充一个自然数，该自然数与众所周知的数独规则不冲突。现在我对下一个空单元格做同样的事情，直到我没有插入有效数字而不会发生冲突。据我了解，这应该是回溯发挥作用的地方。但是怎么做？如果我使用递归返回最后写入的单元格，算法将再次填写数字，继续并最终陷入无限循环。

因此，我在 Internet 上搜索了提示，发现这是一个有据可查且经常解决的问题。然而，许多解决方案声称使用回溯，即使我面前有源代码，我也看不出他们是如何或在哪里做的。

例如：Java 中的数独求解器，使用回溯和递归或http://www.heimetli.ch/ffh/simplifiedsudoku.html

这是我的（不工作）源代码：

现在我不知道如何继续。如何实施回溯或者我已经实施了吗？这似乎是一个愚蠢的问题，但我真的没有看到上面链接中提到的源代码中有更多的回溯。

编辑：最终（工作）版本：

我正在尝试解决代码出现的第 9 天的问题javascript

我正在使用回溯来获取所有可能的路线，然后计算每条路线的成本。

我习惯于使用 PHP 和 C++ 等语言进行回溯，但从未在 JS 中这样做过，所以感谢 google，我发现您无法在 PHP 和 C++ 中传递像&参数这样的可变参数。

我的意图是将bestRoute变量分配给最佳路线，因为这是问题的解决方案。

但是当我这样做时，在某些站点中使用 return 时，我得到一个未定义的变量错误，如下所示：

这是我当前的代码，它不起作用并像第一个定义的那样打印 bestRoute。

我被这个问题陈述所困扰，我的代码确实有效，但我使用itertools.permutations了它，这使得它非常慢。此外，我不知道如何使它适用于所有或任何输入。我想我必须使用回溯，但我没有在这里使用如何使用它。

欢迎任何有价值的建议或建议或代码。是的，这是一项任务，我不是要完整的代码。谢谢！

这是问题陈述：

用不同的数字（0, 1, 2, .., 9）代替下面的不同字母，这样对应的加法正确，得到的MONEY值尽量大。价值是什么？

SHOW + ME + THE = 钱

有 3 个解满足方程：10376、10267、10265。因此，正确的一个是（最大的）10376。如果有多个映射评估为相同的最大值，则将它们全部输出。

那作业：

用 Python 写一个程序，总能找到这类问题的正确解决方案。

I have a little problem with this.I want to generate every possible combination.The numbers located in 1D array and it is read from a file. Now I don't know the problem: I know that every combination which will be printed to monitor is in ascending order. The probelm is that if it finishes with smallest number it doesn't ascends to the next number.

Example: The 1D array file with 1,2,3,4,5 and n = 5 and p = 3; Possible combinations:

1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5, 1 4 5, 2 3 4, 2 3 5, etc...

Here is what I done so far:

我有一个学校项目，我必须用 C# 编写一个程序。我认为我在正确的轨道上，但我坚持这个问题。

在程序的这一部分，我必须编写一个回溯算法。我有课程（英语、物理、数学等），所有课程都持续特定时间。（例如 1h、2h、3h、5h 等）。另外，我有 maxClassHours ，它显示了一个人今天可以在学校度过多少时间。该算法应尽可能收集填充此 maxClassHours 的类的所有可能组合。

重要的是我只能坐一次给定的课程！所以我只能上一节数学课。

例如，maxClassHours 是 5，所以我可以花 5 个小时坐在不同的班级。

假设我有这些课程：

• 数学 - 2小时
• 物理 - 1小时
• 音乐 - 2 小时
• 舞蹈 - 5小时
• 体育 - 3小时
• 地理 - 5小时
• 英语 - 3 小时
• 法语 - 1 小时
• 科学 - 7小时
• 艺术 - 1小时

目标是找到填补这 5 个小时的所有可能组合（使用回溯算法）。

我希望它有意义...谢谢您的帮助。

编辑：我想了解如何将回溯算法应用于此问题。

EDIT2：我尝试了几个小时的工作，但我无法取得重大进展，这就是我寻求帮助的原因......

问题

我知道在我的功能的某个地方，我没有返回我应该返回的东西。

我正在返回递归调用，但似乎我没有返回“一路”

语境

我正在对列表中的每个组合进行深度优先搜索。一旦我达到达到某个条件的组合，我就想返回。

我正在保持我的组合的“状态”，并且正在回溯我应该在哪里（我认为）。

我究竟做错了什么？

Combo 有一个名为“staples”的属性，由一系列主食类组成。我想遍历决策树中的钉书钉列表以找到最佳数量。

在这种情况下，最佳数量是对列表中每个钉书钉实例的数量求和，并作为 Combo 实例的属性存储/重新计算。

我有这个家庭作业要做一个递归方法来破解给定长度的密码，n（无限和未知！）由小英文字母组成，仅限 az。

这是创建随机密码的“密码”类：

这是详细的问题：“您必须编写一个静态递归方法， public static String findPassword(Password p, int length)它会“破解”代码。这是一个主要方法的示例：

重要笔记：

1. 该方法必须是递归的，不使用任何循环。
2. 您不能使用 getPassword 方法。
3. 如果您想使用 String 类的方法，您只能使用以下内容：charAt、substring、equals、length。
4. 你可以使用重载，但你不能使用其他方法。（您不能使用 String.replace/String.replaceall）
5. 您不得使用静态（全局）变量。
6. 您不得使用任何数组。"

这是我到目前为止所拥有的，这显然行不通；:\

非常感谢！非常感激！- 三重奏

我正在尝试使用递归和 DP 找到两个字符串的最长公共子字符串。请注意，我指的不是最长连续子序列。所以，如果两个字符串是

我正在尝试使用递归和回溯来做到这一点。但是，问题是，如果我使用如下递归，+1会在帧中预先添加，即在调用堆栈中更高，并且不知道要出现的字符是否确实是连续元素。因此，按照上面的例子，“bcdf”就是答案。

至于现在，下面的代码是我想出的。请注意，每次发现不匹配时，我都会将计数重置为 0。并使用名为int count的变量跟踪匹配字符的数量，并使用名为int maxcount的变量记录程序中任何点的最高值。我的代码如下。

这工作正常。但是，我不喜欢我的代码的几件事

1. 使用全局变量（静态 int maxcount）跨帧进行比较
2. 我不认为这是真正的动态编程或回溯，因为较低的帧没有将其输出返回到较高的帧，然后决定如何处理它。

请给我您的意见，说明如何在不使用全局变量和使用回溯的情况下实现这一目标。

PS：我知道解决该问题的其他方法，例如保留矩阵并执行类似的操作

M[i][j] = M[i-1][j-1]+1 如果（str[i] == str[j]）

目标不是解决问题，而是找到一个优雅的递归/回溯解决方案。