Почему обратный поиск делает алгоритм недетерминированным?

Ответ 1

Это не так, что обратный поиск делает алгоритм недетерминированным.

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

Ответ 2

Я просто напишу википедию:

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

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

Из Недетерминированное программирование.

Ответ 3

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

Ответ 4

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

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

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

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

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

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

Ответ 5

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

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

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

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

Ответ 6

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

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

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

Ответ 7

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

Ответ 8

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

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

Ответ 9

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

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

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

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

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

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

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

В КОНТРАСТЕ:

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

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