•  01-10-2019
  •  | 
  •  

题

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

我希望我的功能立即退出该功能，而不是一一陈述返回。

有帮助吗？

解决方案

您可以在C和C ++中使用setJmp（）/longjmp（），以绕过绕过一路传递标志的粗略但有效的方法。

其他提示

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

我认为，一种快速而肮脏的方法是抛出一个异常并在基本级别上捕捉它（现在，许多人会尖叫以仅使用异常来使用错误，我认为，建立解决方案是一个非凡的事件，因为没有找到一个事件规范）

如果您有完成后设置的标志，则可以在功能中检查一下，您可以解决此问题。例如

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

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

您为什么要该功能立即退出？没有通过堆栈进行回溯是危险的，因为您可能会有需要销毁的物体。抛出例外可能会给您带来窍门，它将清理堆栈。提供有关您要做的事情的更多信息，我们也许可以提供其他方法。

如果您的回溯算法实际上已经足够深，那么您就不应使用递归，因为您可能有吹烟囱的危险。您不应考虑使用自己的堆分配的堆栈将算法重写为迭代方法，而不是涉及LongJMP的某些暴行，该算法存储代表状态的POD对象。当您发现解决方案时，状态容器可以在一个有效的步骤中被破坏，并且可以返回答案。

看 从递归到迭代的方式

首先，请注意，您无法为任何递归功能做到这一点。考虑以下代码：

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;
        }
}
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top