Остановка возврата

Question

Есть ли какой-либо способ в C / C ++ остановить алгоритм обратного отслеживания после нахождения первого решения без выхода из программы.

Я хочу, чтобы моя функция немедленно выходила из функции, а не выходила из всех уровней рекуррентного уровня.одним заявлением возврата.

Answer 1

Не зная точно, что вам нужно, я бы посмотрел на реализацию вашего собственного стека и полностью избежал рекурсии. Таким образом, становится тривиально выйти из дерева обратного отслеживания (одно «возвращение»), и также можно возобновить поиск, чтобы найти следующее решение, снова вызвав функцию, предполагая, что состояние пользовательского стека сохраняется в статических переменных). Конечно, для преобразования простой рекурсивной программы в цикл требуется немного времени, но это довольно просто сделать.

Answer 2

если у вас есть флаг, который установлен, когда вы закончите, а затем который проверен в ваших функциях, вы можете решить это например,

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

Answer 3

Быстрый и грязный способ - создать исключение и поймать его на базовом уровне (сейчас многие утверждают, что используют исключения только для ошибок, я утверждаю, что найти решение - исключительное событие, поскольку одна норма)

Answer 4

Почему вы хотите, чтобы функция немедленно выходила? Не возвращаться через стек опасно, так как на нем могут быть объекты, которые необходимо уничтожить. Если вы сгенерируете исключение, это может помочь вам, и это очистит стек. Предоставьте больше информации о том, что вы пытаетесь сделать, и мы могли бы предложить другие подходы.

Answer 5

На самом деле это зависит от вашей реализации, но вы могли бы установить какой-то особый параметр и использовать его в качестве флага типа «Получили ли мы решение? Если да, то прервите текущую процедуру и получите только это решение для вывода».

Answer 6

Во-первых, обратите внимание, что вы не можете сделать это для любой рекурсивной функции. Рассмотрим следующий код:

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

Answer 7

Если ваш алгоритм обратного отслеживания на самом деле достаточно рекурсивный, чтобы это имело значение, вам не следует использовать рекурсию, потому что вы рискуете перевернуть стек. Вместо того, чтобы совершать какое-либо злодеяние, связанное с longjmp, вы должны рассмотреть возможность переписать ваш алгоритм итеративным подходом с вашим собственным стеком, выделенным для кучи, в котором хранится объект POD, представляющий состояние. Когда вы найдете свое решение, контейнер состояния может быть уничтожен за один эффективный шаг, и ответ может быть возвращен.

См. Путь от рекурсии к итерации

Answer 8

Вы можете использовать setjmp () / longjmp () как в C, так и в C ++ для грубого, но эффективного способа избежать необходимости передавать флаг обратно.