Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Пример (недетерминированное вычислительное предписание) Предписание - часть 3
Эти затраты определяются как глубиной «почти сразу» успешного поиска, так и происходящей широтой поиска.
Можно представить себе два возможных способа действий (т. e. возможные способы реализации) при вычислении недетерминированного выражения с failure-подвыражениями.
· Параллельное вычисление, которое соответствует одновременному развитию событий, как при Т-недетерминизме. Вычисление завершается успешно, если найдется одна из ветвей успешного вычисления.
· Поиск с возвратом (бэктрекинг-недетерминизм). Если текущая ветвь вычислений приводит к failure , то она обрезается и для вычисления выбирается другая ветвь. Лишь в том случае, когда все ветви вычислений приводят к
failure, вычисление в целом считается неуспешным. Таким образом, бэктрекинг-недетерминизм требует поиска в недетерминированно-выбранном дереве вычисления.
Обратим внимание: каждая задача в NP с помощью подходящих функций gi, которые соответствуют недетерминированным альтернативам Т-машины, а также предикатов vollstandig и korrekt, которые проверяют, является ли потенциальное решение полным и корректным, может быть представлена следующей схемой программы с бэктрекинг-недетерминизмом:
fct f = (m x) m:
if vollstandig(x) then if korrekt(x) then x
else failure
fi
else f(gi(x))a...a f(gk(x)(x))
fi
При этом глубина рекурсии предписания f должна быть полиномиально-ограниченна.
Бэктрекинг-недетерминизм может быть обобщенна выбор из конечных множеств. Выбор элемента х типа m с определенным свойством q(x) назовем также недетерминированным выбором.
Для этого мы пишем
some m х: q(x).
С помощью этого оператора выбора для некоторых задач можно достаточно просто формулировать алгоритмы.
Пример (недетерминированное порождение обхода Гамильтона). Пусть тип node
является множеством {0, 1, ..., п-1} вершин ориентированного графа, ребра которого заданы через fct g = (node, node) bool.
