Intel_Nils, страница 7

Часто бывает удобным приписывать дугам графа стоимости, отражающие стоимость применения соответствующего оператора. Мы будем использовать запись с(пь и,) для обозначения стоимости дуги, направленной из вершины и; в пр Стоимость пути между двумя верр1инами определяется тогда как сумма стоимостей всех дуг, соединяющих вершины этого пути. В задачах оптимизации возникнет необходимость найти путь между двумя вершйнами, имеющий минимальную стоимость. В задачах простейшего типа нам необходимо найти путь (возможно, имеющий минимальную стоимость) между заданной вершиной е (представляющей начальное состояние) и другой заданной вершиной с (представляющей целевое состбяние). Два очевидных усложнения этой простейшей задачи следующие: Найти путь между вершиной е и любым элементом множества вершин (гс).

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

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

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

При этом процесс поиска в пространстве состояний той последовательности операторов, которая решает задачу, соответствует преобразованию в явную форму достаточно большой части неявно заданного графа, такой, чтобы в нее входила вершина, отвечающая цели. Таким образом, центральным пунктом решения задачи с использованием пространства состояний является поиск на графе указанного типа. Рассмотрение приемов поиска на графе мы отложим до следующей главы. 2,б. ПРЕДСТАВЛЕНИЕ ПРОСТРАНСТВ СОСТОЯНИИ ПОСРЕДСТВОМ НЕДЕТЕРМИН ИРОВАННЫХ ПРОГРАММ ') Процесс порождения пространства состояний может быть представлен блок-схемой, изображенной на рис. 2.2.

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

Множество (возможно, бесконечное) всех возможных способов выполнения программы, представленной этой блок-схемой, охватывает тогда полное про- ') Этот раздел может быть опущен при первом чтении. 2 Заа. азз 34 Гл. 2. Представление задач е иространстее состояний странство состояний. (При такой формулировке состояния описываются возможными величинами программной переменной у, которая может быть произвольно сложной совокупностью данных.) Программы, в которых используются операторы присваивания (и другие), допускающие во время выполнения недетерминированные выборы, получили название недетерминированнын'). Часто бывает удобно представлять пространство состояний некоторой задачи неявно, с помощью некоторой недетерминированной блок-схемы.

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

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

Для представления этого подмножества мы пользуемся обозначением Я, а ВЫБОР (Р) означает выбор одного члена (любого члена) этого подмножества. Этот член затем присваивается как новое значение величине у, (Мы допускаем, что присваивание может зависеть как от значения входной переменной х, так и от имеющегося в данное время значения программной переменной у.) ') Слово «недетерминированный» в том смысле, в котором оно использовано здесь, вовсе не равносильно слову «стохастический»ч иедетерминирован.

вость не означает наличие каких-либо случайных механизмов. 2.5. Представление посредством пвдетврминироваииых программ Зо Рис. 2.3. Представление игры в пятнадцать в виде иедетермииировннной программы. Кроме того, мы расширяем понятие оператора ветвления. В операторе Ч -ветвления на п направлений используется и пРедикатов Р~(х, У), ..., Рн(хдУ), пРинимающих либо значение Т (истина), либо Р (ложь) в совместной области изменения х и у, причем по крайней мере один из предикатов должен иметь значение Т. Каждый предикат соответствует некоторой ветви.

Выбирается одна ветвь (любая), для которой соответствующий ей предикат имеет значение Т. Этот тип недетерминированного ветвления называется тг'-ветвлением и на блок-схемах обозна- 36 Ге. 2. Представление водок в аространстве состояний чается следующим образом: Лт Отметим, что обычные детерминированные присваивания и ветвления — это простые частные случаи недетерминнрованных операторов. При конкретном восполнении недетерминированной программы в операторах~/-ветвление и ВЫБОР делаются конкретные выборы. Тогда множество всех возможных способов выполнения определяет пространство состояний. Если для любого входного массива существует по крайней мере одно конкретное выполнение программы, имеющее окончание, то говорят, что эта программа правильно определена.

В качестве того как некоторой задаче можно придать форму недетерминированной программы, на рис. 2.3 дается одна возможная программа для игры в пятнадцать. Здесь состояние описывается значением программной переменной у, принадлежащем пространству массивов 4 рс',4. Элементами этих массивов являются числа от ! до 15 и символ ° (представляющий пустую клетку).

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

НЕКОТОРЫЕ ПРИМЕРЫ ПРЕДСТАВЛЕНИЙ ЗАДАЧ Для большого числа задач можно дать представления, связанные с пространством состояний. Для некоторых задач такое представление удается выбрать совершенно естественно, тогда как для других любое представление, связанное с введением пространства состояний, кажется весьма искусственным. Читателю не следует предполагать, что каждая из формулировок, приведенных в настоящем разделе, — наилучшая из всех возможных.

Точно так же он не должен удивляться, увидев, что может решить задачу, опираясь на иное представление. Сейчас мы хотим лишь показать, что для некоторых различных типов задач действительно возможно представление в пространстве состояний. 2.6. Оекоторме примера представлений задач 37 Задача о коммивояжере Задача о коммивояжере — классичесКая комбинаторная проблема. Коммивояжер должен построить свой маршрут так, чтобы побывать в каждом из и городов в точности по разу и возвратиться в исходный город.

Желательно, чтобы этот маршрут имел минимально возможную протяженность. Было разработано несколько эффективных методов решения задачи, которые реализуемы лишь в том случае, когда число городов не превышает примерно 50. Приближенные методы дают хорошие решения (хотя не обязательно минимизирующие протяженность маршрута) уже для 200 городов.

Задача о коммивояжере полезна для иллюстрации представлений, основанных на введении пространства состояний, как это видно из следующего простого частного примера. В и Р и с, 2.4. Карта для задачи о коммивояжере. Коммивояжер должен посетить каждый из пяти городов, изображенных на карте на рис. 2.4.