问题标签 [recursive-backtracking]

我目前正在编写一个递归算法来解决 Peg Solitaire 游戏。

该算法需要使用“回溯”的方法来解决棋盘。我想我已经设法得到了一个非常接近正确的解决方案。看来我的代码正确地解决了所有可解板的问题。它似乎也正确地确定了板何时不可解，但仅当钉子的数量不太高时。

我的递归方法如下所示：

该板是标准的 Peg Solitaire 板。我确信我的 isSolved() 方法正确地确定了板子是否已解决。我的 makeMove 函数接受行、列和方向（i、j 和 k）。它在这些坐标处找到钉子并检查它是否可以将其移动到请求的方向。如果可以，它会移动，将移动添加到移动数组中，然后返回 true。如果不是，则返回 false。

我的 undo 方法从数组中弹出最后一个动作，并将棋盘恢复到以前的布局（在弹出动作之前）。

似乎对于大约 25 个或更多钉子的随机板，程序根本不会终止。它无限期地继续处理。可解板和具有较少钉子的各种不可解板似乎始终会在 10 秒内以正确的结果终止。

有任何想法吗？

我正在尝试实现状态空间图的深度优先迭代深化搜索。我有一个包含三个顶点的图，它们是两个激活边和两个抑制边。每个节点都有一个二进制值，这就是图的状态。该图可以通过查看其中一个节点是高于阈值还是低于阈值（通过对所有传入节点求和来计算）转换到新状态。每次转换最多会改变一个节点。由于它们是三个节点，因此它们是三个状态转换边，将每个状态留在状态转换图中。

我认为我的 state_change/3 工作正常，例如我可以查询：

它给了我三个正确的答案：

我正在尝试使用 Bratkos Prolog for AI book 中给出的谓词 id_path，这是问题 11.3 的解决方案，但我在使用/调整它时遇到问题。 我想创建从起始节点到其他节点的路径，而不会进入循环 - 我不希望它有重复元素或在路径不存在时卡住。我想让路径说起始状态，然后您可以从起始状态访问一系列状态。如果有一个自我循环，我希望每一种到达那里的方式都包含一次。即我想跟踪我到达状态空间的方式，并使其独一无二，而不仅仅是状态空间在路径中是唯一的。

例如，从 011 开始，我希望用弧线找到长度为 1 的所有三个路径。

然后在下一级所有具有三个节点的路径，显示它需要到达节点的两条弧，然后在下一级，所有具有四个节点的路径显示它需要的三个弧等

如果这有帮助，我也将我的代码放入 SWISH 中？（第一次尝试这个？！）

http://pengines.swi-prolog.org/apps/swish/p/HxBzEwLb.pl#&togetherjs=xydMBkFjQR

我的任务是找到一种方法来显示所有可能的方式来回馈预定值的更改，这些值是从txt文件中扫描的。这必须通过递归回溯来完成，否则我的解决方案将不会得到认可。老实说，我完全不知道如何使用适当的算法进行编码。我所知道的是该算法的工作原理是这样的：

问题是我对如何或从哪里开始没有丝毫线索，只有必须完成的事情，或者是否有任何其他解决方案是显而易见的。

到目前为止，这是我的代码：

更新

这是我扫描的输入文件

java homework5 hwk5sample1.txt

输出

因此，使用 my 中的数字coinTypes ArrayList，我需要一个通用代码算法来显示所有可能的接收方式，例如，使用文件中的硬币返回 143（1.43 美元）零钱，所有便士都是最后一种显示方式。

请不要以为我想让你给我写算法，我只是想帮助写一个，否则我什么也学不会。谢谢大家的任何回答或帮助，您可以给予这对我来说意义重大！如果我遗漏了什么或者您需要更多信息，请告诉我

我非常接近完成我的任务，但我不知道如何findChange()正确调用。我的猜测是它需要在 main 方法中。但是当 findChange(); 打电话给它，它要求int, List<Integer>, List<Integer>我如何“正确”地做到这一点。

代码

这个程序计算了所有不同的方式来显示一定金额的变化，即：143（1.43 美元）。我所要做的就是调用findChange()main 并且它应该可以工作，我错过了什么？

编辑我刚刚意识到我没有指定我需要帮助的方法调用我为任何不清楚的地方道歉

输入文件

电流输出

想

我的程序的目标是输出给定金额的所有可能的变更解决方案，例如

期望的输出

（9 = $0.09）但是我的输出有点不同，我的输出看起来像这样

我的输出

如您所见，它从字面上为我提供了所有可能的解决方案。我只关心前两个答案。很明显，当要求更大的数量时，这将是一个大问题。所以这是我的问题：根据我的代码，如何将其修复到每个仅显示一个组合的位置？

代码

感谢您的任何和所有答案，请尽量忽略任何其他错误，我想先解决这个问题。谢谢！！

我目前正在处理用户输入单词的编程任务

即“那个”

并且程序应该返回可以从给定字符串中生成的所有有效单词

即[那个，帽子，在]

我遇到的问题是应该使用检查前缀是否有效的递归方法来创建生成的单词。

即如果给定的单词是“kevin”，一旦程序尝试组合“kv”，它应该知道没有单词以kv开头并尝试下一个组合以节省时间。

目前，我的代码只创建所有排列，当输入大于 8 个字母时，这需要相对大量的时间。

如果有人可以帮助我解决这个问题，我将不胜感激。我还使用 AVL 树来存储字典单词以进行必要的验证。

我需要这个练习的帮助：
给出在输入中接收整数 n 并打印所有可能的矩阵 nxn 的伪代码，其中 a 的数量大于或等于 b 的数量，例如 n=2：（顺序不重要）输出：
aa aa aa ab ab ba ba
ab ba aa aa ba aa ab
算法的复杂度为 O($n^2*S(n)$)。其中 S(n) 是应打印的矩阵数。

现在我对回溯的技术算法不是很了解，因为我正在研究它......所以请如果有人可以帮助我进行练习和回溯......否则我永远不会通过这次考试。感谢你们 ;）

我最近用 C++ 制作了一个数独求解器。我使用回溯算法来解决它，但有一个问题：在某些情况下，它只能解决到第 5 行。

工作案例：[6][6] = 2, [4][5] = 1

第 5 行后的案例失败：[1][1] = 1

我不知道它在某些情况下部分解决 sudoko 的原因可能是什么，并且对于这些情况存在解决方案

作为家庭作业的一部分，我需要编写一个函数，如果给定的数组中存在“好”子组，则返回 true。“好子组”是每个组成员中特定字段（整数）的总和大于给定目标（特别是数组原始长度的一半）的子组，并且每个组成员小组与小组的所有其他成员“相处”。如果 2 个成员“相处融洽” (abs(m1->f1 - m2->f1) + abs(m1->f2 - m2-f2)) <= given_hatred。这是我到目前为止尝试过的，但似乎不起作用：

我还要提到 Member 是一种抽象数据类型，它实现了所有以开头的函数，member....并且工作正常（经过测试）。

编辑： 我找到了一个解决方法，我很快就会发布，但我对其他解决方案非常感兴趣，所以请随意:)

我试图在简单的六边形晶格的有限区域中生成所有闭合曲线。这并不太重要，它只是一组彼此相距 1 的有限点。但是，我的代码会生成一段时间的闭合曲线，然后我的程序将停止工作并陷入无限循环？我曾尝试通过命令强制 java 进行垃圾收集，但相同的代码在不同的点停止。据我所知，它停在哪里是随机的。Sphere 是一个数组，用于存储所考虑区域中的所有点