Почему отслеживание делает алгоритм недетерминированным?

Question

Итак, по крайней мере, два профессора упомянули, что откат назад делает алгоритм недетерминированным, не давая слишком большого объяснения, почему это так. Я думаю Я понимаю, как это происходит, но мне сложно выразить это словами. Может ли кто-нибудь дать мне краткое объяснение причины этого?

Answer 1

Дело не в том, что при обратном отслеживании алгоритм становится недетерминированным.

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

Answer 2

Я просто процитирую Википедию:

Недетерминированный язык программирования - это язык, который может определять в определенных точках программы (так называемые «точки выбора») различные альтернативы для выполнения программы. В отличие от оператора if-then, метод выбора между этими альтернативами не определяется программистом напрямую; программа должна выбирать во время выполнения между альтернативами, используя некоторый общий метод, применяемый ко всем точкам выбора. Программист указывает ограниченное количество альтернатив, но программа должна позже выбирать между ними. («Выбрать» - это, фактически, типичное имя для недетерминированного оператора.) Может быть сформирована иерархия точек выбора, с выбором более высокого уровня, ведущим к ветвям, которые содержат выборы более низкого уровня.

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

Из недетерминированного программирования статья.

Answer 3

Рассмотрим алгоритм раскраски карты мира. Никакой цвет нельзя использовать в соседних странах. Алгоритм произвольно начинается в стране и окрашивает ее в произвольный цвет. Таким образом, он движется, окрашивая страны, меняя цвет на каждом шаге, пока «ооо», две смежные страны не будут иметь одинаковый цвет. Что ж, теперь мы должны вернуться и сделать новый выбор цвета. Сейчас мы не делаем выбор, как недетерминированный алгоритм, это невозможно для наших детерминированных компьютеров. Вместо этого мы моделируем недетерминированный алгоритм с возвратом. Недетерминированный алгоритм сделал бы правильный выбор для каждой страны.

Answer 4

Время выполнения обратного отслеживания на детерминированном компьютере является факториальным, то есть в O (n!).

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

Поскольку невозможно построить недетерминированный компьютер, то, что ваш профессор, вероятно, имел в виду следующее:

A заведомо сложная проблема в классе сложности NP (все проблемы, которые недетерминированный компьютер может решить эффективно, всегда правильно угадывая), не могут быть решены более эффективно на реальных компьютерах, чем при возврате.

Приведенное выше утверждение верно, если классы сложности P (все проблемы, которые детерминированный компьютер может эффективно решить) и NP не совпадают. Это знаменитая проблема P против NP. Институт глиняной математики предложил приз в 1 миллион долларов за свое решение, но проблема не поддалась доказательству в течение многих лет. Однако большинство исследователей считают, что P не равно NP.

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

Answer 5

Я написал бегущий в лабиринте, который использует backtracking (конечно), который я буду использовать в качестве примера.

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

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

Answer 6

Мысленный эксперимент:

1) Скрыто от глаз некоторое распределение электрических зарядов, от которых вы чувствуете силу и измеряете потенциальное поле, которое они создают. Скажите мне точно позиции всех обвинений.

2) Возьмите некоторые сборы и организуйте их. Скажите мне точно потенциальное поле, которое они создают.

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

Answer 7

Мне нравится аналогия лабиринта. Давайте для простоты будем рассматривать лабиринт как бинарное дерево, в котором есть только один выход.

Теперь вы хотите попробовать поиск в глубине, чтобы найти правильный выход из лабиринта.

Недетерминированный компьютер в каждой точке ветвления будет дублировать / клонировать себя и выполнять все последующие вычисления параллельно. Это похоже на то, как если бы человек в лабиринте дублировал / клонировал себя (как в фильме «Престиж») в каждой точке ветвления и отправлял одну копию себя в левую ветвь дерева, а другую копию себя - в правую ветвь дерева. дерево.

Компьютеры / люди, которые оказываются в тупике, они умирают (заканчивают без ответа).

Только один компьютер выживет (завершится с ответом), тот, кто выходит из лабиринта.

Разница между возвратом и недетерминизмом заключается в следующем.

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

В КОНТРАСТЕ:

Недетерминистский компьютер может клонировать себя в каждой точке ветвления и проверять выход, выполняя поиск параллелизма в подветвях.

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

Answer 8

Недетерминированные машины Тьюринга (NDTM) могут принимать несколько ветвей за один шаг. DTM, с другой стороны, следуют процессу проб и ошибок.

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

Answer 9

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