2.5. ПРЕДСТАВЛЕНИЕ ПРОСТРАНСТВ СОСТОЯНИЙ ПОСРЕДСТВОМ НЕДЕТЕРМИНИРОВАННЫХ ПРОГРАММ

Процесс порождения пространства состояний может быть представлен блок-схемой, изображенной на рис. 2.2. Здесь символы х и у используются для обозначения произвольных совокупностей данных. Заметим, что оператор присваивания «положить у равным некоторому члену множества элементов, непосредственно следующих за у», является недетерминированным в том смысле, что при его выполнении может быть выбран любой член множества

Рис. 2.2. Представление пространства состояний с помощью недетерминированной программы. Исходное положение: программная переменная у (пробегающая описания состояний) полагается равной входной структуре данных описывающей начальное состояние. Присваивание: новое значение программной переменной у полагается равным одному из элементов множества дочерних значений для прежней величины у.

Множество (возможно, бесконечное) всех возможных способов выполнения программы, представленной этой блок-схемой, охватывает тогда полное

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

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

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

В общем недетерминированные программы связаны с расширением определений оператора обычного присваивания и оператора ветвления детерминированных программ. Мы уже видели, как можно пользоваться, недетерминированными операторами присваивания. Этот тип операторов присваивания, называемый операторами типа ВЫБОР, на блок-схемах обозначается так:

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

Рис. 2.3. (см. скан) Представление игры в пятнадцать в виде недетерминированной программы.

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

обозначается следующим образом:

Отметим, что обычные детерминированные присваивания и ветвления — это простые частные случаи недетерминированных операторов.

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

В качестве того как некоторой задаче можно придать форму недетерминированной программы, на рис. 2.3 дается одна возможная программа для игры в пятнадцать. Здесь состояние описывается значением программной переменной у, принадлежащем пространству массивов . Элементами этих массивов являются числа от 1 до 15 и символ (представляющий пустую клетку). Функции ВЛЕВО, ВВЕРХ, ВПРАВО, ВНИЗ соответствуют операторам. Они изменяют массивы посредством перемещения символа соответственно влево, вверх, вправо, вниз.

Оказывается, что можно определить также и другие элементы недетерминированных программ. Эти элементы полезны при обсуждении формулировок, основанных на сведении задачи к подзадачам. Они будут рассмотрены в гл. 4.