Конспект установочных лекций по комплексному курсу Информатика, Теория информации



Пример (недетерминированное вычислительное предписание) Предписание - часть 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.




Содержание  Назад  Вперед