停止回溯

Question

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

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

Answer 1

一种快速而肮脏的方法是抛出异常并在基础级别捕获它（现在很多人会尖叫只使用异常来处理错误，我认为，找到一个解决方案是一个特殊的事件，因为找不到一个解决方案就是规范）

Answer 2

如果您在完成后设置了一个标志，然后在您的函数中检查该标志，您可以解决这个问题。例如

void foo(..)
{
   if (g_done) return;
...
}

Answer 3

在不确切知道您需要什么的情况下，我会考虑实现您自己的堆栈，并完全避免递归。这样，退出回溯树（单个“返回”）就变得微不足道，并且还可以通过再次调用该函数来恢复搜索以找到下一个解决方案，假设保留了用户定义堆栈的状态（在静态变量中）。当然，将简单的递归程序转换为循环需要一些编程开销，但做起来非常简单。

Answer 4

它实际上取决于您的实现，但您可以设置一些特殊参数并将其用作标志，例如“我们得到解决方案了吗？如果是，则中止当前例程并仅获取输出的解决方案”。

Answer 5

为什么要让函数立即退出呢？不回溯堆栈是危险的，因为堆栈上可能有需要销毁的对象。抛出异常可能会给你带来麻烦，它会清理堆栈。提供有关您正在尝试执行的操作的更多信息，我们也许可以提供其他方法。

Answer 6

您可以在 C 和 C++ 中使用 setjmp()/longjmp() 作为一种粗略但有效的方法来绕过一路传递标志的需要。

Answer 7

如果你的回溯算法实际上递归得足够深，以至于这很重要，那么你不应该使用递归，因为你将面临堆栈崩溃的危险。您应该考虑使用自己的堆分配堆栈（存储表示状态的 POD 对象）将算法重写为迭代方法，而不是犯下涉及 longjmp 的暴行。当您找到解决方案时，可以通过一个有效的步骤销毁状态容器并返回答案。

请参阅从递归到迭代的方式

Answer 8

首先，请注意，您不能对任何递归函数执行此操作。
考虑以下代码：

int SumNum(int nMax)
{
    if (0 == nMax)
        return 0;
    else
        return nMax + SumNum(nMax-1);
}

实际值是在回溯期间计算的。

但是，您可以按以下方式重写代码：

int SumNum(int nMax, int nSum)
{
    if (0 == nMax)
        return nSum;
    else
        return SumNum(nMax-1, nSum+nMax);
}

现在，您可以执行以下技巧：

    int SumNum(int nMax, int nSum)
    {
        if (0 == nMax)
            throw nSum;
        else
            return SumNum(nMax-1, nSum+nMax);
    }


f()
{
        int nSum;

        try
        {
            SumNum(100, 0);
        }
        catch (int _nSum)
        {
            nSum= _nSum;
        }
}