С точки зрения программирования, что такое решение для поиска с возвратом?

У меня есть пара вопросов о том, что на самом деле означает решение с возвратом.

  1. Скажем, у вас есть n вариантов из текущего состояния, значит ли решение с возвратом в основном означает, что вы пробуете все эти состояния и делаете то же самое для подзадач (где у вас может быть n-1 состояний для решения), и и так далее, и вы возвращаете лучшее решение от (n-1)-го кадра до n-го кадра.

См. задачу ниже, где: Данная веревка длины n, как разрезать веревку на m частей длиной n[0], n[1], ..., n[m-1], чтобы получить максимальное произведение n[0]n[1] ... *n[m-1] Итак, веревку длины нужно разрезать на 2*3*3, чтобы получить произведение из 18. ,

public class RopeCuttingMaxProduct
{
    public static void main(String[] args)
    {
        System.out.println(fun(8));
    }

    static int fun(int n)
    {
        if(n == 1)
            return 1;

        int totalret = 0;
        for(int i = 1;i<n;i++)
        {
            /*At every frame, two options 1.to cut 2.to not cut
             *  1.If cutting, multiple ways to cut : Remember i+(n-i) == n
             *  2.If not cutting, just return n
             */
            /* Explore all possible solutions, from all possible paths 
             * and the subpaths that these lead to,
             * and their subpaths*/
            int reti = max(fun(n-i)*i,n);

            if(reti > totalret)
                totalret = reti;
        }
        return totalret;
    }

    static int max(int a, int b)
    {
        return a>b?a:b;
    }
}
  1. Итак, все ли решения с возвратом экспоненциальны по временной сложности?
  2. Это так похоже на рекурсию, что я не могу себе представить что-то подобное, достигнутое с помощью какой-либо другой рекурсии. Можете ли вы привести пример решения с возвратом, достигнутого без рекурсии?
  3. Чем он отличается от грубой силы. Является ли решение этой проблемы грубой силой, чтобы попробовать все возможные комбинации способов сложения до n. Я считаю, что приведенное выше решение для обратного отслеживания делает почти то же самое.

recursion algorithm dynamic-programming backtracking recursive-backtracking
person tubby    schedule 24.10.2015    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Если вы считаете, что путь, по которому идет ваш алгоритм, является обходом дерева решений, то решение, если оно существует, является неким конечным узлом дерева, или, если существует несколько решений, то существует несколько конечных узлов, которые их представляют.

Возврат просто означает, что алгоритм обнаруживает в какой-то момент, что решение не может быть найдено в ветви дерева, в которой он находится в данный момент, и затем перемещается назад на один или несколько узлов, чтобы продолжить работу с другими ветвями.

Это не означает, что нужно посетить все узлы. Например, если алгоритм обнаружит, что текущая ветвь не имеет смысла, до того, как она действительно достигнет листа, то он будет избегать посещения всех оставшихся узлов в этой ветви.

Следовательно, не все алгоритмы поиска с возвратом являются грубыми.

Сколько ненужной работы может избежать такой алгоритм, очень специфично для задачи, на него нельзя ответить в общем виде. Общий ответ заключается в том, что поиск с возвратом не обязательно основан на исчерпывающем поиске/испытании.

person trijezdci    schedule 24.10.2015