2.6. НЕКОТОРЫЕ ПРИМЕРЫ ПРЕДСТАВЛЕНИЙ ЗАДАЧ

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

Задача о коммивояжере

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

Коммивояжёр должен посетить каждый из пяти городов, изображенных на карте на рис. 2.4. Между каждой парой горо­дов имеется путь, длина которого указана на этой карте. Нужно, отправляясь из города А, найти са,мый короткий путь, по которому коммивояжер по одному разу проходит через каж­дый из городов и затем возвращается в город А.

Чтобы дать представление в пространстве состояний, мы должны определить следующее:

Описания состояний. Будем задавать состояния списком го­родов, пройденных к настоящему моменту. Так, начальным состоянием будет список (Л). Мы не будем допускать, чтобы в этом списке какой-то город упоминался более одного раза, с тем лишь исключением, что после того, как в нем будут упо­мянуты все остальные .города, может быть снова упомянут А.

Операторы. Операторы суть вычисления, соответствующие лоступкам: (1) направиться теперь в город А, (2) направиться

теперь в город В, , (5) направиться теперь в город Е. Опе­ратор неприменим к некоторому описанию состояния, если он не преобразует его в некоторое допустимое описание. Так, опе­ратор номер (1) (соответствующий «направиться теперь в го­род Л») неприменим ни к какому описанию, не содержащему названия всех городов.

Критерий достижения цели. Любое описание, начинающееся и оканчивающееся городом Л и перечисляющее все другие го­рода, есть описание состояния, удовлетворяющего поставленной цели.

На рис. 2.5 показано представление этого пространства со­стояний в виде графа. (Явно указаны лишь некоторые из его

вершин.) Числа, написанные около дуг графа, указывают стои­мости этих дуг'. Мы полагаем эти стоимости равными расстоя­ниям между соответствующими городами (см. рис. 2.4). В вер­шинах графа стоят описания тех состояний, которые они представляют. Достоинства представления в виде графа состоят

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

Задача о коммивояжере представляет собой пример задачи, в которой информация, содержащаяся в ее формулировке, пред­ставима в графической форме (карте расстояний). Следует быть внимательным и не смешивать какие-либо графы, исполь­зуемые при формулировке задачи, с графом пространства со­стояний, который строится при решении задачи.

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

Грамматика. Предположим, что мы определяем предложение как строку одного из следующих видов: за символом а следует символ b за символом а следует некоторое предложение за некоторым предложением следует символ b за некоторым предложением следует другое предложение. Примеры предложений: aab, abaabab, aaaaab. Некоторые строки, не являющиеся предложениями: ааа, aba, abaa.

Предположим, что мы захотели определить, является ли строка abaabab предложением. Тогда формулировка этой задачи в пространстве состояний выглядит taK:

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

Операторы. Мы определяем операторы через следующие лравила переписывания:

$іай$2->-$iS$2 (подстрока ab может быть заменена сим­волом S, обозначающим предложение)

Мы видим, что эти правила просто выражают грамматику, определяющую понятие предложения.

Критерий цели. Целевое состояние описывается строкой, ко­торая состоит из одиночного символа S.

Последовательность состояний, представляющая собой реше­ние этой задачи, имеет следующий вид:

Граф, изображающий пространство состояний для этой задачи, показан на рис. 2.6. В этой задаче оказалось так, что

в силу заданной грамматики любая строка, начинающаяся с а и оканчивающаяся на Ь, является предложением. Знание такого факта, очевидно, сильно бы упростило решение вопроса о том, будет ли некоторая произвольная строка предложением. Иногда оказывается, что заданная грамматика может быть представ-

лена в эквивалентном, но более простом виде. Обнаружение таких упрощений позволяет строить меньшие пространства для перебора.

Следующая простая задача типична для класса задач, на­зываемых иногда задачами распределения. Имеются два источ­ника жидкости: А дает 100 галлонов в минуту, а В — 50. Источ­ники должны снабжать два бассейна С и D, потребность каждого из которых 75 галлонов в минуту. Жидкость может

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

Представление этой задачи в пространстве состояний выгля­дит следующим образом:

Описания состояний. Состояния описываются списком вели­чин избыточного расхода жидкости, который имеется в точках А, В, С и D. Так, начальное состояние описывается списком (А = 100, В = 50, С = 0, D = 0).

Операторы. Операторы соответствуют передаче избытка «жидкости в минуту» из одной точки в другую. В задачах, по-

добных этой, в качестве подходящего избытка выступает наи­больший общий делитель пропускных способностей и потребно­стей в жидкости в различных точках. Таким образом, у нас есть операторы:

1. Передать 25 галлон/мин из Л в В.

2. Передать 25 галлон/мин из Л в С.

12. Передать 25 галлон/мин из В в Л.

Разумеется, операторы применимы лишь тогда, когда имеется достаточный избыток жидкости в той точке, от которой жид­кость отбирается для передачи в другую точку. И, конечно, для осуществления каждой такой передачи нужно иметь соответ­ствующую трубу.

Критерий цели. Целевое состояние описывается списком (Л = О, В = О, С = .75, D = 75).

Часть графа, получающегося таким образом пространства состояния, показана на рис. 2.8. Обозначение типа A—*D около Дуг графа показывает, что соответствующий оператор передает избыток в 25 галлон/мин от Л к D. Стоимости, написанные ря­дом с каждой дугой, показывают, сколько миль труб нужно до­бавить для подачи этого избытка. Число нуль при этом озна-

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

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

Интересным примером служит задача о перевернутом маят­нике на тележке (рис. 2.9). В этой задаче масса М прикреп­лена к концу стержня длины /, дру­гой конец которого шарнирно за­креплен на тележке, так что стер­жень может свободно вращаться в вертикальной плоскости, совпадаю­щей с направлением движения те­лежки, снабженной колесами. Уста­навливаемые переменные — угол на­клона стержня Ѳ, координата х те­лежки и производная по времени Ѳ.

Требуется, чтобы значения каждой из этих переменных поддержива­лись в определенных, заранее ука­занных границах. Управляющей пе­ременной служит скорость тележки х, которая может принимать одно из двух значений -\-ѵ и —ѵ. (Мы предполагаем для простоты, что эти значения могут сменять друг друга мгновенно.) Главная за­дача здесь состоит в принятии в данный момент решения о том, следует ли перемещать тележку со скоростью ѵ вправо или со скоростью ѵ влево.

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

Операторы. Имеются ровно два оператора:

1. Применить управление + ѵ.

2. Применить управление —ѵ.

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

Критерий достижения цели. Предположим, что целевое состояние описывается вектором (Ѳ = О, Ѳ = 0, лг=»0). Тогда нам нужно найти последовательность операторов, которая будет преобразовывать любое данное состояние в целое. Конечно, такая последовательность не должна приводить ни к какому состоянию, описываемому переменными Ѳ, Ѳ и х, для которого неизбежно в конце концов полное нарушение работы системы- (Оно происходит при Ѳ = ±90°.)

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