Have Geek Brain

Reverse stop

Is there a way in C / C ++ to stop the backtracking algorithm after finding the first solution without exiting the program.

I want my function to exit the function immediately, rather than leaving each level of recursion one by one by specifying return.

+2


a source to share


8 answers


You can use setjmp () / longjmp () in both C and C ++ for a crude but effective workaround for having to pass a flag on the way back.



0


a source


Without knowing exactly what you need, I would look at implementing my own stack and avoid recursion entirely. Thus, it becomes trivial to exit the backtrace tree (one "backtrace"), and you can also resume searching to find the next solution by calling the function again, assuming that the state of the user stack is preserved (in static variables). Of course, there is a bit of programming overhead to convert a simple recursive program to a loop, but it's pretty straightforward to do.



+3


a source


The quick and dirty way is to throw an exception and catch it at a basic level (around now a lot of people will shout to use Exceptions for errors, I argue that creating a solution is an exceptional event since not finding one is the norm)

+2


a source


if you have a flag set that is set when you are done and then checked in your functions you can fix this problem. eg.

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


a source


It really depends on your implementation, but you can set some special parameter and use it as a flag like "Have we got a solution? If yes, then abort your current procedure and get only this output solution".

+1


a source


Why do you want the function to exit immediately? It is dangerous not to backtrack through the stack, as you may have objects that need to be destroyed. Throwing an exception might be triggered by a trick for you and it will clear the stack. Please provide more information on what you are trying to do and we could provide other approaches.

+1


a source


If your backtracking algorithm actually recurses deep enough for it to matter, then you shouldn't use recursion because you would be in danger of blowing the stack. Rather than committing some atrocity involving longjmp, you should consider rewriting your algorithm to be an iterative approach with your own heap stack that stores a POD object representing the state. When you find your solution, the state container can be destroyed in one efficient step and a response can be returned.

See Way to go from recursion to iteration

0


a source


First, please note that you cannot do this for any recursive function. Consider the following code:

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

The actual value is calculated during backtracking.

However, you can rewrite your code like this:

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

Now you can do the following trick:

    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;
        }
}
0


a source






More articles:


All Articles