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

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

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

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

Рис. 2.4. Карта для задачи о коммивояжере.

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

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

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

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

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

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

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

Рис. 2.5. (см. скан) Часть графа для задачи о Коммивояжере.

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

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

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