4.6. ПРЕДСТАВЛЕНИЕ «И/ИЛИ» ГРАФОВ С ПОМОЩЬЮ НЕДЕТЕРМИНИРОВАННЫХ ПРОГРАММ

Мы можем ввести некоторые дополнительные элементы недетерминированных программ, с тем чтобы эти программы можно было использовать для представления процесса построения «И/ИЛИ» графа. По аналогии с оператором присваивания ВЫБОР (в котором программная переменная принимается равной любому элементу некоторого множества) мы можем определить оператор присваивания ВСЕ. В последнем программная переменная принимается равной всем элементам некоторого

множества. (Представьте себе, что вычисление после оператора ВСЕ разветвляется на множество фиктивных параллельных про? цессов, в каждом из которых в качестве значения программной переменной берется своя величина.)

Рис. 4.7. Недетерминированная программа, определяющая «И/ИЛИ» граф. ИСХОДНОЕ ПОЛОЖЕНИЕ: Программная переменная у (принимающая значения из области описаний задач) полагается равной входной структуре данных х, описывающей; задачу.

ВЫБОР: Значение программной переменной (принимающей значения области множеств описаний задач) полагается равным некоторому элементу множества множеств дочерних вершии для прежнего значения Новое значение у принимается равным всем элементам множества

На рис. 4.7 изображена блок-схема недетерминированной программы, определяющей «И/ИЛИ» граф. Для простоты здесь опущены условия окончания, но они состояли бы в совершенна очевидных проверках, разрешимы вершины или неразрешимы.

В общем случае оператор ВСЕ обозначается на блок-схемах следующим образом:

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

новые значения программной переменной у равными всем членам множества

Мы также вводим обозначение Д-ветвления. Это ветвление на направлений, в котором используется предикатов Эти предикаты имеют значение Т (истина) или (ложь) на той области, которая является прямым произведением областей изменения х и у. (Снова х — входная структура данных, а у — программная переменная.) Значение хотя бы одного из этих предикатов должно быть Т. Каждый предикат соответствует некоторой ветви, и выбираются все те ветви, соответствующие предикаты которых имеют значения Т. (Представьте себе опять фиктивные параллельные процессоры, начинающие работать на каждой из выбранных ветвей.) На блок-схемах Д-ветвления изображаются так:

И опять, обычные детерминированные ветвления являются частными случаями Д-ветвлений. Точно так же, когда значением функции является один элемент, операторы ВЫБОР, ВСЕ и обычные детерминированные операторы совпадают.

При конкретном осуществлении недетерминированной программы делается один определенный выбор в -ветвлениях и операторах ВЫБОР и производятся все возможные выборы в Д-ветвлениях и операторах ВСЕ. Множество всех возможных конкретных реализаций определяет некоторое «И/ИЛИ» дерево. В данной реализации содержится много путей (ветвления на Д-ветвлениях и операторах ВСЕ). Ее выполнение завершается, если завершается каждый из ее путей. Если для любого входа существует по крайней мере одна завершающая реализация, то говорят, что эта программа правильно определена.

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

координаты ферзя по горизонтали и по вертикали соответственно.

Рис. 4.8. (см. скан) Недетерминированная программа для задачи в восьми ферзях.

Предикат «побить имеет значение Т лишь тогда, когда ферзь с координатами с может по бить ферзя с координатами