问题标签 [backtracking]

在找到第一个解决方案而不退出程序后，C/C++ 中有什么方法可以停止回溯算法。

我希望我的函数立即退出函数，而不是逐个退出每个级别的递归并声明返回。

关于深度优先搜索的维基百科：

深度优先搜索 (DFS) 是一种用于遍历或搜索树、树结构或图的算法。一个从根开始（在图中选择某个节点作为根），并在回溯之前沿着每个分支尽可能地探索 。

那么什么是广度优先搜索？

“一种算法，选择一个起始节点，检查所有节点回溯，选择最短路径，选择邻居节点回溯，选择最短路径，由于连续回溯遍历每条路径，最终找到最佳路径。

Regexfind的修剪——回溯？

回溯一词因其用途广泛而令人困惑。UNIXfind对 SO 用户的修剪通过回溯进行了解释。如果您不限制 Regex 的范围，Regex Buddy 使用术语“灾难性回溯”。这似乎是一个使用过于广泛的总称。所以：

1. 您如何专门为图论定义“回溯”？
2. 广度优先搜索和深度优先搜索中的“回溯”是什么？

[添加]

关于回溯和示例的良好定义

1. 蛮力法
2. Stallman（？）发明的术语“依赖导向回溯”
3. 回溯和正则表达式示例
4. 深度优先搜索定义。

SWI-Prolog 中是否有任何内置谓词总是会失败并防止机器回溯 - 它是停止程序立即执行（这不是什么fail/0）？我可以使用剪辑，但我不喜欢它们。

做类似的事情!, fail对我来说不是问题，但为了完成我想要的，我必须在更多位置使用剪辑，这是我不喜欢的。

所以我整天都在尝试解决这个任务，就是无法完成。

以下函数接受 2 个字符串，第二个（不是第一个）可能包含*'s（星号）。
an*是字符串的替换（空，1 个字符或更多），它可以出现（仅在 s2 中）一次、两次、更多或根本不出现，它不能与另一个相邻*（ab**c），无需检查。

如果字符串具有相同的模式，则返回 true。
它必须是递归的，不能使用任何循环、静态和全局变量。可以使用局部变量和方法重载。

只能使用以下方法：charAt(i), substring(i), substring(i, j), length().

例子：

1 TheExamIsEasy：；2: The*xamIs*y→ 真
1: TheExamIsEasy; 2: Th*mIsEasy*→ 真
1: TheExamIsEasy; 2: *→ 真
1: TheExamIsEasy; 2: TheExamIsEasy→ 真
1: TheExamIsEasy; 2：The*IsHard→假

我尝试使用逐个比较字符，charAt直到遇到星号，然后通过比较连续字符 ( i+1) 与s1at 位置的字符来检查星号是否为空i，如果为真 - 继续递归i+1作为s2&的计数器i作为计数器s1；
如果为假 - 继续递归i+1作为两者的计数器。
继续此操作，直到找到另一个星号或字符串结尾。

我不知道，我的大脑失去了对事物的追踪，无法集中注意力，任何指针/提示？我在正确的方向吗？

此外，据说要使用回溯技术来解决这个问题。

到目前为止我的代码（即使在理论上也不能完成这项工作）：

我的问题的抽象是在笛卡尔平面中有很多矩形。这些矩形具有已知的整数大小，并且必须具有整数坐标，它们的横坐标（水平坐标）是已知的且固定的，只有它们的纵坐标（垂直坐标）可能会有所不同。

问题是找到包含所有给定矩形的最小矩形最小的那些坐标。这意味着它应该具有最小高度，因为它的宽度是固定的，因为小矩形具有固定的横坐标。

我不知道我是否应该使用回溯或者有更快的方法，我可以想象在 50 个矩形上需要一些可测量的时间来计算正确的解决方案，而贪婪算法并不适合我。

编辑：对不起，我现在意识到我不够清楚。当我第一次问这个问题时，我正在构建一个日历应用程序。经理会为他的团队填写事件：

• 活动 A 从下午 2 点开始。并在下午 4 点结束。
• 活动 B 从下午 5 点开始。并在下午 6 点结束。
• 活动 C 从下午 4 点开始。并在下午 6 点结束。
• 活动 D 从下午 2 点开始。并在下午 3 点结束。
• 活动 E 从下午 3 点开始。下午 5 点结束。

我想在时间轴上显示这些事件，并且我希望它们占用尽可能少的屏幕空间，而不会重叠（因为经理希望在其矩形中查看每个事件，并在该矩形中查看描述）。

上述示例的最佳安排如下：

A和C在一条线上，D、E、B在另一条线上。贪婪的方法是将 A 和 B 放在同一条线上，C 和 D 放在另一条线上，E 放在第三条线上。

好的，真正的问题稍微复杂一些，因为它使用了我编写的一些类而不是字符串，但可以这样想象：如果你有一个包含 700 个 3 字母单词的列表，我怎样才能找到每个组合可以通过将其中的 5 个单词的首字母和尾字母连接在一起形成，即 CAT TOW WAR RAD DOG 会成功，但 CAT TOW WAR RAG GOD 也会成功，等等。

到目前为止，我有这样的事情：

但这只会不断增加生产垃圾。我不擅长递归回溯，我认为如果我能让这个例子工作，我最终会理解这个概念。请聪明人帮帮我！

作为针对此问题的一般酿造示例，我的意图是匹配一些a's，然后匹配相同数量的b's，再加上一个 's b。

检查此片段中展示的两种模式（也在 ideone.com 上）：

请注意，两种模式的匹配存在差异。r1，它在平衡组构造上使用贪婪重复，匹配 3a和 3 b，这不是预期的。r2，它使用了不情愿的重复，给了我 2a和 3 b，这是预期的。

我可以解释这一点的唯一方法是，当(?<B-A> b)+回溯匹配一个 lessb时，它会从B堆栈中弹出，但不会推回相应地从A堆栈中弹出的内容。因此，即使b现在由于回溯而匹配到少一个，A堆栈仍然是空的。这是我可以解释如何r1匹配的唯一方法aaabbb。

请注意，使用不情愿+?inr2不会导致此问题。在我看来，这是因为与贪婪的重复不同，不情愿的重复不必“消除”对A堆栈的损害，可以这么说。相比之下，贪婪的重复会造成尽可能多的“损害”，但回溯无法“让事情保持原样”到A堆栈中。

这是对发生的事情的正确分析吗？如果是这样，这种行为是设计使然吗？因为在我看来基本上是在贪婪的重复中回溯平衡组可能会导致不平衡，因此这可能被归类为错误（或者至少是没有充分记录的有点令人惊讶的行为）。

我有一个似乎可以通过列举所有可能的解决方案然后找到最佳解决方案来解决的问题。为了做到这一点，我设计了一种回溯算法，它会枚举并存储找到的最佳解决方案。到目前为止它工作正常。

现在，我想将此算法移植到 CUDA。因此，我创建了一个程序来生成一些不同的基本案例。这些基本情况应该在 GPU 上并行处理。如果其中一个 CUDA 线程找到了最佳解决方案，那么所有其他线程当然可以停止它们的工作。

所以，我想要以下内容：找到最佳解决方案的线程应该停止我程序的所有正在运行的 CUDA 线程，从而完成计算。

经过一番快速搜索，我发现线程只有在同一个块中才能进行通信。（所以我想阻止其他人阻塞线程是不可能的。）

我能想到的唯一方法是我有一个专用标志optimum_found，在每个内核开始时都会检查它。如果找到最佳解决方案，则将此标志设置为1，因此所有未来的线程都知道它们不必工作。但是，当然，如果已经运行的线程没有在每次迭代时检查这个标志，它们就不会注意到这个标志。

那么，是否有可能停止所有剩余的 CUDA 线程？

假设我有以下代码：

现在当我做

我可以将邻居列表打印到控制台。但是我怎样才能得到它作为结果列表呢？就像是

（由于member处理方式，上面的部分并没有真正起作用。请问有什么建议吗？

我想建立一种排序方法将数组“4,2,7,5,1”排序为“1,2,4,5,7”我当前的代码是

怎么了