Назад | Содержание| Вперёд Глава 11. ОСНОВНЫЕ СТРАТ...

Глава 11.

ОСНОВНЫЕ СТРАТЕГИИ РЕШЕНИЯ ЗАДАЧ

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

11. 1.    Предварительные понятия ипримеры

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

Эту задачу можно представлять себе как задачувыбора среди множества возможных альтернатив. Висходной ситуации альтернатива всего одна:поставить кубик С на стол. После того как кубик Споставлен на стол, мы имеем три альтернативы:

поставить А на стол или

поставить А на С, или

поставить С на А.

Рис. 11. 3.  "Игра ввосемь" и ее представление в форме графа.

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

Давайте подытожим те понятия, которые мы ввели,рассматривая примеры. Пространство состоянийнекоторой задачи определяет "правила игры":вершины пространства состояния соответствуютситуациям, а дуги - разрешенным ходам илидействиям, или шагам решения задачи. Конкретнаязадача определяется

пространством состояний

стартовой вершиной

целевым условием (т.е. условием, к достижению которого следует стремиться); "целевые вершины" - это вершины, удовлетворяющие этим условиям.

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

В тех случаях, когда каждый ход имеет стоимость,мы заинтересованы в отыскании решенияминимальной стоимости. Стоимость решения - этосумма стоимостей дуг, из которых состоит"решающий путь" - путь из стартовой вершины вцелевую. Даже если стоимости не заданы, все равноможет возникнуть оптимизационная задача: насможет интересовать кратчайшее решение.

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

Мы будем представлять пространство состоянийпри помощи отношения

        после( X, Y)

которое истинно тогда, когда в пространствесостояний существует разрешенный ход из вершины  Х  в вершину  Y.  Будем говорить, что  Y  - это преемник вершины  X.  Еслис ходами связаны их стоимости, мы добавим третийаргумент, стоимость хода:

        после( X, Y, Ст)

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

Рассмотрим в качестве примера задачуманипулирования кубиками, проиллюстрированнуюна рис. 11.1. Мы будем рассматривать более общийслучай, когда имеется произвольное числокубиков, из которых составлены столбики, - одинили несколько. Число столбиков мы ограничимнекоторым максимальным числом, чтобы задача былаинтереснее. Такое ограничение, кроме того,является вполне реальным, поскольку рабочеепространство, которым располагает робот,манипулирующий - кубиками, ограничено.

Проблемную ситуацию можно представить каксписок столбиков. Каждый столбик в свою очередьпредставляется списком кубиков, из которых онсоставлен. Кубики упорядочены в списке такимобразом, что самый верхний кубик находится вголове списка. "Пустые" столбикиизображаются как пустые списки. Таким образом,исходную ситуацию рис. 11.1 можно записать как терм

        [ [с, а, b], [ ], [ ] ]

Целевая ситуация - это любая конфигурациякубиков, содержащая, столбик, составленный извсех имеющихся кубиков в указанном порядке.Таких ситуаций три:

        [ [a, b, c], [ ], [ ] ]

        [ [ ], [а, b, с], [ ] ]

        [ [ ], [ ], [a, b, c] ]

Отношение следования можно запрограммировать,исходя из следующего правила: ситуация Сит2есть преемник ситуации Сит1, если в Сит1имеется два столбика Столб1 и Столб2,такие, что верхний кубик из Столб1 можнопоставить сверху на Столб2 и получитьтем самым Сит2. Поскольку все ситуации -это списки столбиков, правило транслируется наПролог так:

        после( Столбы,[Столб1, [Верх1 | Столб2], Остальные]) :-