Почему обратный анализ делает алгоритм недетерминированным?
Так что, по крайней мере, два профессора упомянули, что откат назад делает алгоритм недетерминированным, не давая слишком много объяснений, почему это так. Я думаю, что понимаю, как это происходит, но мне трудно выразить это словами. Может ли кто-нибудь дать мне краткое объяснение причины этого?
9 ответов
Дело не в том, что при обратном отслеживании алгоритм становится недетерминированным.
Скорее, вам обычно требуется откат назад для обработки недетерминированного алгоритма, поскольку (по определению недетерминированного) вы не знаете, какой путь выбрать в конкретный момент вашей обработки, но вместо этого вы должны попробовать несколько.
Я просто процитирую Википедию:
Недетерминированный язык программирования - это язык, который может определять в определенных точках программы (так называемые "точки выбора") различные альтернативы для выполнения программы. В отличие от оператора if-then, метод выбора между этими альтернативами не определяется программистом напрямую; программа должна выбирать во время выполнения между альтернативами с помощью некоторого общего метода, применяемого ко всем точкам выбора. Программист указывает ограниченное количество альтернатив, но программа должна позже выбирать между ними. ("Выбрать" - это, фактически, типичное имя для недетерминированного оператора.) Может быть сформирована иерархия точек выбора с выбором более высокого уровня, ведущим к ветвям, которые содержат выборы более низкого уровня внутри них.
Один из методов выбора реализован в системах обратного отслеживания, в которых некоторые альтернативы могут "потерпеть неудачу", в результате чего программа откатывается назад и пробует другие альтернативы. Если все альтернативы потерпят неудачу в определенной точке выбора, тогда произойдет сбой всей ветви, и программа вернется к более старой точке выбора. Одна сложность состоит в том, что, поскольку любой выбор является предварительным и может быть переделан, система должна быть в состоянии восстановить старые программные состояния путем устранения побочных эффектов, вызванных частичным выполнением ветки, которая в конечном итоге не удалась.
Из статьи о недетерминированном программировании.
Рассмотрим алгоритм раскраски карты мира. Никакой цвет нельзя использовать в соседних странах. Алгоритм произвольно начинается в стране и окрашивает ее в произвольный цвет. Таким образом, он движется, окрашивая страны, меняя цвет на каждом шаге, пока "ооо", две смежные страны не будут иметь одинаковый цвет. Что ж, теперь мы должны вернуться и сделать новый выбор цвета. Сейчас мы не делаем выбор, как недетерминированный алгоритм, это не возможно для наших детерминированных компьютеров. Вместо этого мы моделируем недетерминированный алгоритм с возвратом. Недетерминированный алгоритм сделал бы правильный выбор для каждой страны.
Время выполнения обратного отслеживания на детерминированном компьютере является факториальным, то есть оно находится в O(n!).
В тех случаях, когда недетерминированный компьютер может мгновенно правильно угадать на каждом этапе, детерминированный компьютер должен попробовать все возможные комбинации вариантов.
Поскольку невозможно построить недетерминированный компьютер, вероятно, имел в виду ваш профессор:
Доказательно трудная проблема в классе сложности NP (все проблемы, которые недетерминированный компьютер может эффективно решить, всегда правильно угадывая), не может быть решена более эффективно на реальных компьютерах, чем возврат.
Приведенное выше утверждение верно, если классы сложности P (все проблемы, которые детерминированный компьютер может эффективно решить) и NP не совпадают. Это знаменитая проблема P против NP. Институт глиняной математики предложил приз в 1 миллион долларов за свое решение, но проблема не поддается доказательству в течение многих лет. Однако большинство исследователей считают, что P не равно NP.
Простой способ подытожить это так: большинство интересных проблем, которые недетерминированный компьютер мог бы эффективно решить, всегда правильно угадывая, настолько сложны, что детерминированному компьютеру, вероятно, придется попробовать все возможные комбинации выбора, то есть использовать возвратный путь.
Мысленный эксперимент:
1) Скрыто от глаз некоторое распределение электрических зарядов, от которых вы чувствуете силу и измеряете потенциальное поле, которое они создают. Скажите мне точно позиции всех обвинений.
2) Возьмите некоторые обвинения и организуйте их. Скажите мне точно потенциальное поле, которое они создают.
Только на второй вопрос есть уникальный ответ. Это неединственность векторных полей. Эта ситуация может быть аналогична некоторым недетерминированным алгоритмам, которые вы рассматриваете. Далее рассмотрите в математических пределах, которые не существуют, потому что они имеют разные ответы в зависимости от того, в каком направлении вы подходите к разрыву.
Я написал бегущий в лабиринте, который использует backtracking (конечно), который я буду использовать в качестве примера.
Вы идете через лабиринт. Когда вы достигаете перекрестка, вы подбрасываете монету, чтобы решить, по какому маршруту идти. Если вы выбрали тупик, проследуйте обратно до перекрестка и выберите другой маршрут. Если вы попробовали их все, вернитесь к предыдущему перекрестку. Этот алгоритм недетерминирован, не из-за возврата, но из-за подбрасывания монеты.
Теперь измените алгоритм: когда вы достигнете перекрестка, всегда пробуйте самый левый маршрут, который вы еще не пробовали в первую очередь. Если это приводит к тупику, вернитесь к перекрестку и снова попробуйте крайний левый маршрут, который вы еще не пробовали. Этот алгоритм является детерминированным. Здесь нет никаких шансов, это предсказуемо: вы всегда будете следовать по одному и тому же маршруту в одном и том же лабиринте.
Недетерминированные машины Тьюринга (NDTM) могут принимать несколько ветвей за один шаг. DTM, с другой стороны, следуют процессу проб и ошибок.
Вы можете думать о DTM как о обычных компьютерах. В отличие от этого, квантовые компьютеры похожи на NDTM и могут гораздо проще решать недетерминированные проблемы (например, см. Их применение для взлома криптографии). Таким образом, возвращение назад будет для них линейным процессом.
Мне нравится аналогия лабиринта. Давайте для простоты будем рассматривать лабиринт как бинарное дерево, в котором есть только один выход.
Теперь вы хотите попробовать поиск в глубине, чтобы найти правильный выход из лабиринта.
Недетерминированный компьютер в каждой точке ветвления будет дублировать / клонировать себя и выполнять все последующие вычисления параллельно. Это похоже на то, как если бы человек в лабиринте дублировал / клонировал себя (как в фильме "Престиж") в каждой точке ветвления и отправлял одну копию себя в левую ветвь дерева, а другую копию себя - в правую ветвь дерева. дерево.
Компьютеры / люди, которые оказываются в тупике, они умирают (заканчивают без ответа).
Выживет только один компьютер (заканчивается с ответом), тот, кто выходит из лабиринта.
Разница между возвратом и недетерминизмом заключается в следующем.
В случае возврата назад в любой момент времени существует только один живой компьютер, он выполняет традиционный трюк по решению лабиринта, просто пометив свой путь мелом, а когда он попадает в тупик, он просто просто возвращается к точке ветвления, чьи подответы он еще не исследовал полностью, как в глубоком первом поиске.
ПО СРАВНЕНИЮ:
Недетерминированный компьютер может клонировать себя в каждой точке ветвления и проверять выход, выполняя поиск параллелизма во вспомогательных ветвях.
Таким образом, алгоритм обратного отслеживания имитирует / имитирует способность клонирования недетерминированного компьютера на последовательном / непараллельном / детерминированном компьютере.
Если вы разрешаете возврат, вы разрешаете бесконечный цикл в вашей программе, что делает его недетерминированным, поскольку реальный путь всегда может включать в себя еще один цикл.