问题标签 [backtracking]

我真的不知道应该如何使用 List 转换ListT器。例如应该如何完成这个简单的任务：

函数的类型应该是什么？

这不是我想要完成的任务（我知道如何使用许多其他方法来解决这个问题），我只是想知道如何使用ListT来完成这些任务。

我正在写一个数独回溯求解器，它卡住了，我不明白为什么。我认为我的递归调用没问题。我错过了什么？

输入从 input.txt 文件中读取，网格初始布局在一行中：

输入.txt：

编辑：我的意思是“卡住”，因为没有完成对网格的求解

这是一个示例输出：

程序：

我正在尝试用 JavaScript 编写一个算法来解决使用回溯的骑士​​之旅问题，但它不起作用。基本上，该函数应该输出一个名为visited的数组，其中包含每个移动的位置。但是，没有将位置附加到数组，它仍然是 [[0,0]]。这是我的代码。有什么线索吗？

谢谢你。

由于堆栈（带有推送和弹出），我在树中使用回溯算法。它有效，但我有一个问题。堆栈给出的路径是“错误的”。

例如，我有一棵树：

例如，当我想要 C 的路径时，此函数返回 RAB（适用于 R 和 A，而不是 B）。

我不知道它是来自这个函数还是 push() 函数。如果您在函数中没有看到任何错误，我将粘贴 push() 但它很长。

编辑：我现在更好地理解了，我已经添加到函数中：
如果节点是叶子，pop()。如果我搜索 F，它会返回我 RABF 而不是 RB F。我不知道如何避免将 A 保留在堆栈中。

编辑2：

这是代码：（返回 RABF 而不是 RBF）

我不明白如何弹出遍历子节点以获得良好的结果，也许在 if (Prefix(root->left, tas, search)) 中添加 else ？有人有想法吗？

谢谢 ！

这个递归回溯问题遇到了一些麻烦：

“编写一个可分区的方法，该方法接受整数列表作为参数并使用递归回溯来发现列表是否可以划分为两个相等和的子列表。如果给定的列表可以平均分区，则您的方法应该返回 true，并且如果不是，则为假。”

例如，列表 [1, 2, 3] 可以划分为子列表 [1, 2] 和 [3]，因此它会产生“真”的结果。

我的解决方案似乎是正确的，但无论如何都会返回 false。我不明白为什么。

编辑：我解决了从 list1 中删除元素两次的问题。

我在我的PEG解析器中添加了零个或多个和一个或多个修饰符，这很简单，因为 PEG 中的回溯很少。早期的迭代永远不会重新考虑，所以一个简单的while循环就足够了。

然而，在其他情况下，零个或多个和一个或多个修饰符确实需要回溯。例如，采用以下正则表达式：

这个表达式应该能够贪婪地匹配一个由 7 组成的字符串a：有几种方法可以将 2 和 3 相加得到 7。但要做到这一点，重新考虑早期的迭代是必要的。例如，如果表达式a第一次匹配 3 a，第二次匹配 3，则只剩下一个a，无法匹配。但是，回溯最后三个a并匹配两个a，然后匹配五个a。然后最后两个a也可以匹配（即3 + 2 + 2 = 7）。

幸运的是，正则表达式在匹配字符串后退出搜索。但是EBNF解析器呢？如果语法不明确，解析器将使用回溯查找所有可能的语法树！如果我们有生产

和一个由 7 组成的字符串a，一个完全回溯的解析器将返回用 2 和 3 来表达 7 的所有可能方式。这只是针对 7a的：匹配一个稍长的字符串，并且N叉树的可能性会增长另一个层次。考虑N  = 6：

恐怖的组合爆炸！

然而，真的会是这样吗？EBNF中对零个或多个修饰符和一个或多个修饰符没有限制吗？按照描述实现它们比while()PEG 解析器的普通循环要多得多，所以我不得不怀疑......

我有一个矩阵，需要通过命中和试验方法进行更改、评估，如果不符合要求则需要重新分配值。我在用于链式假设的递归函数中执行此操作。这可以在不创建多个副本的情况下完成吗？

我可以在回溯时恢复矩阵吗？

这个问题是在面试中提出的，涉及递归/回溯。假设我们有两个布尔数组：bool* source并且bool* target，它们中的每一个都具有相同的长度n（源/目标/n 作为参数给出）。问题的目标是转换source为target使用操作 开关。

• 如果有多个转换：呈现其中任何一个
• 如果没有解决方案：断言没有解决方案

定义：运算switch(int i, bool* arr)反转 arr[i] 和 arr[i-1] 和 arr[i+1] 的值（如果这些索引在 0...n-1 范围内）。

换句话说，switch操作通常会翻转三位（i和它的邻居），但只有两位。

例如：

• switch(0,arr) 将只切换 arr[0] 和 arr[1] 的值
• switch(n-1,arr) 将只切换 arr[n-1] 和 arr[n-2] 的值

提前感谢您对算法的建议。

我目前正在学习回溯并陷入 8-queen 问题，我使用的是 8x8 矩阵，我认为我在将矩阵传递给函数方面遇到了一些问题，任何帮助都会非常感激。我不介意如果任何人都会对代码进行任何优化，谢谢。

这是我的代码。

有人能解释一下为什么 Java 的正则表达式引擎会在这个正则表达式上进入灾难性的回溯模式吗？据我所知，每个交替都与其他交替互斥。

文本：'pão de açúcar itaucard mastercard platinum SUSTENTABILIDADE])

向某些交替添加所有格匹配可以解决问题，但我不知道为什么 - Java 的正则表达式库必须非常错误才能在互斥分支上回溯。