4

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

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

4

8 回答 8

5

一种快速而肮脏的方法是抛出一个异常并在基本级别捕获它(我认为,现在很多人会尖叫只使用异常处理错误,找到一个解决方案是一个例外事件,因为找不到一个是规范)

于 2010-04-25T14:30:16.360 回答
3

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

void foo(..)
{
   if (g_done) return;
...
}
于 2010-04-25T14:34:50.643 回答
3

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

于 2010-04-25T14:48:59.190 回答
1

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

于 2010-04-25T14:26:21.187 回答
1

为什么要让函数立即退出?不回溯堆栈是危险的,因为上面可能有需要销毁的对象。抛出异常可能是由于你的技巧,它会清理堆栈。提供有关您正在尝试做的事情的更多信息,我们可能会提供其他方法。

于 2010-04-25T14:54:12.483 回答
0

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

于 2010-04-25T14:42:22.643 回答
0

如果您的回溯算法实际上递归的深度足以让这一点变得重要,那么您不应该使用递归,因为您将面临破坏堆栈的危险。与其犯一些涉及 longjmp 的暴行,不如考虑将算法重写为迭代方法,使用自己的堆分配堆栈存储代表状态的 POD 对象。当您找到解决方案时,可以通过一个有效的步骤销毁状态容器并返回答案。

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

于 2010-04-25T15:48:33.797 回答
0

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

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;
        }
}
于 2010-04-25T18:16:13.387 回答