в качестве результата выдает любое
fct f == ( nat n ) nat:
if n == 0 then 0
else f(n—l)
fi
является недетерминированным и при его вызове
f(m) для m Î N в качестве результата выдает любое число i Î N, такое, что 0£ i £ m.
Обратим внимание, что от недетерминированного выбора может также зависеть и завершаемость вычислений.
Пример (недетерминированный алгоритм с неопределенным завершением).
Предписание
fct f =( nat n ) nat:
n?f(n+1)
При вызове f(m) либо вычисляет такое число i Î N, что m £ i, либо вычисление выражения не завершается.
В дальнейшем мы хотим - в свете полиномиально-ограниченных Т-машин - сконцентрироваться на недетерминированных алгоритмах, при которых завершение вычислений всегда обеспечено. В таком случае завершаемость не зависит от недетерминированного выбора.
Пример (недетерминированное порождение перестановки). Алгоритм f, заданный описанием
fct f = ( nat n ) seq nat:
if n = 0 then
else nperm(f(n—l), n)
fi
fct nperm == ( seq nat s, nat n ) seqnat:
if s == e then append(n, s)
else
append(n, s) ?
append(first(s), nperm(rest(s), n))
fi
При вызове f(n) для заданного числа n порождает недетерминированным образом некоторую перестановку чисел {1, 2, ..., n} и всегда завершается. Докажем это по индукции.
(0) Для n > 0 утверждение тривиально.
(1) Предположение индукции: утверждение справедливо для заданного n Î N. Вызов f(n) дает перестановку s из {1, 2, ..., n}. Функция nperm(s, n+l) вставляет (n+l) в какую-нибудь позицию в s. Так можно породить любую перестановку.
Рассмотрение недетерминированных выражений приводит к ряду трудностей, поскольку классические правила преобразований логики не обязательно имеют место. Так, высказывание f(x)==f(x) для недетерминированного алгоритма f можно интерпретировать двояко:
· вычисления правой и левой частей приводят к одинаковому значению (если значений не больше одного);
· множества недетерминированно-возможных значений левой и правой частей совпадают.
Эти тонкие различия затрудняют обращение с недетерминированными выражениями.
Для организации завершения вычислений при недетерминированном выборе введем специальное выражение failure («неуспешная попытка»), которое в некотором (недетерминированном) вычислении обозначает выражение, не доставляющее никакого «желаемого» значения (неуспех). Благодаря этому может быть промоделирована концепция вычислений, встречающаяся в недетерминированных Т-машинах.
Введением failure
определяется так называемый «бэктрекинг-недетерминизм» (недетерминированный поиск с возвратом). Недетерминированные ветви вычисления, которые ведут к failure, отсекаются, т. e. не принимаются в качестве результата. Неуспех фиксируется только в том случае, когда все ветви приводят к failure.
Использование failure (выбор по-прежнему является недетерминированным) позволяет организовать поиск в недетерминированно-выбранном дереве вычислений.
Пример (алгоритмы с недетерминированным поиском).
Сортировка недетерминированным выбором. Рассмотрим систему вычислительных предписаний
fct ndsort == ( seq nat s, seq nat r ) scq nat:
if s = e then r
else nat x == any(s);
if x > first® then failure
else ndsort(drop(s, x), <x> * r)
fi
fi
fct any = (seq nat
s) nat:
if s=e then failure
else first(s) any(rest(s))
fi
fct drop = (seq nat s, nat x) seq nat:
if s == є then failure
elif first(s) = x then rest(s)
else append(first(s), drop(rest(s), x))
fi
fct sort = ( seq nat s)
seq nat:
if s = є then s
else nat x = any(s);
ndsort(drop(s,x),<x>?є
При вызове sort(s) порождается отсортированная по неубыванию версия s.
Обратим внимание: если затраты времени простого (т.e. недетерминированного) выбора составляют z, то затраты бэктрекинг-недетерминизма в самом неблагоприятном случае имеют порядок 2^z.
Эти затраты определяются как глубиной «почти сразу» успешного поиска, так и происходящей широтой поиска.
Можно представить себе два возможных способа действий (т. 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.
Гамильтонов обход через подмножество S узлов - это замкнутый путь без повторений, все узлы которого содержатся в S.
Предписание
fct hk == (set node s,
seq node q) seq node:
if s = Æ
then if g(last(q), first(q)) then q
else failure
fi
else node x == some node z: z e s;
if g(last(q), x) then hk(s\{x}, q 0 <x>)
else failure
fi
fi
порождает недетерминированно-направленный Гамильтонов обход (если он существует) через узлы из конечного множества S в качестве результата вызова hk(s\{x}, <x> о є ), при любом х Î S.
Недетерминированный выбор и концепцию бэктрекинг-недетерминизма можно ввести аналогичным образом в императивные программы. Тогда справедливо: S1 ? S2 для оператора, выполнение которого происходит путем недетерминированного выбора для исполнения одного из операторов S1
и S2
.Снова может быть использовано ключевое слово
failure для обозначения неуспешной ветви (тупика).
