Назад | Содержание | Вперёд

13. 4. 1.    Эвристические оценки и алгоритм поиска

Базовые процедуры поиска предыдущего раздела производят систематический и полный просмотр И / ИЛИ-дерева, не руководствуясь при этом какими-либо эвристиками. Для сложных задач подобные процедуры весьма не эффективны из-за большой комбинаторной сложности пространства поиска. В связи с этим возникает необходимость в эвристическом управлении поиском, направленном на уменьшение комбинаторной сложности за счет исключения бесполезных альтернатив. Управление эвристиками, излагаемое в настоящем разделе, будет основано на численных эвристических оценках "трудности" задач, входящих в состав И / ИЛИ-графа. Программу, которую мы составим, можно рассматривать как обобщение программы поиска с предпочтением в пространстве состояний гл. 12.

Начнем с того, что сформулируем критерий оптимальности, основанный на стоимостях дуг И / ИЛИ-графа. Во-первых, мы расширим наше представление И / ИЛИ-графов, дополнив его стоимостями дуг. Например, И / ИЛИ-граф рис. 13.4 можно представить следующими предложениями:

        а ---> или : [b/1, с/3].
        b ---> и : [d/1, е/1].
        с ---> и : [f/2, g/1].
        e ---> или : [h/6].
        f ---> или : [h/2, i/3].

        цель( d).  цель( g).   цель( h).

Стоимость решающего дерева мы определим как сумму стоимостей его дуг. Цель оптимизации - найти решающее дерево минимальной стоимости. Как и раньше, иллюстрацией служит рис. 13.4.

Будет полезным определить стоимость вершины И / ИЛИ-графа как стоимость оптимального решающего дерева для этой вершины. Стоимость вершины, определенная таким образом, соответствует "трудности" соответствующей задачи.

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

Для продолжения поиска будет всегда выбираться "наиболее перспективное" решающее дерево-кандидат. Каким же образом используется функция   h   для оценки степени перспективности решающего дерева-кандидата или, точнее, вершины-кандидата - корня этого дерева?

Рис. 13. 9.  Получение оценки  Н  трудности задач  И / ИЛИ-графа.

Обозначим через Н( В) оценку трудности вершины  В.  Для самой верхней вершины текущего дерева поиска  H( В)  просто совпадает с  h( В).  С другой стороны, для оценки внутренней вершины дерева поиска нам не обязательно использовать непосредственно значение  h,  поскольку у нас есть некоторая дополнительная информация об этой вершине: мы знаем ее преемников. Следовательно, как показано на рис. 13.9, мы можем приближенно оценить трудность внутренней ИЛИ-вершины как

        H( B) = min ( c( B, B_i) + H( B_i) )
                                ⁱ

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

Будем называть H-оценку внутренней вершины "возвращенной" (backed-up) оценкой.

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

        F( B) = с( В1, В) + H( В)

Пусть  В1  -  родительская вершина вершины  В,  а  В₁,  В₂,   ... - ее дочерние вершины, тогда, в соответствии с определениями  F  и  H, имеем

        F( B) = c( B1, B) + minF( B_i),             если  В   -  ИЛИ-вершина
                                          ⁱ

                       если  В    -  И-вершина

Хотя стартовая вершина  А  и не имеет предшественника, будем считать, что стоимость ведущей в нее (виртуальной) дуги равна 0. Если положить  h  равным 0 для всех вершин И / ИЛИ-дерева, то для любого найденного оптимального решающего дерева окажется, что его стоимость, т.е. сумма стоимостей его дуг, в точности равна  F( A).

На любой стадии поиска каждый преемник ИЛИ-вершины соответствует некоторому альтернативному решающему дереву-кандидату. Процесс поиска всегда принимает решение продолжать просмотр того дерева-кандидата, для которого  F-оценка минимальна. Вернемся еще раз к рис. 13.4 и посмотрим, как будет вести себя процесс, поиска на примере И / ИЛИ-графа, изображенного на этом рисунке. В начале дерево поиска состоит всего из одной вершины - стартовой вершины  а, далее дерево постепенно "растет" до тех пор, пока не будет найдено решающее дерево. На рис. 13.10, показан ряд "мгновенных снимков", сделанных в процессе роста дерева поиска. Для простоты мы предположим, что h = 0 для всех вершин. Числа, приписанные вершинам на рис. 13.10 - это их  F-оценки (разумеется, по мере накопления информации в процессе поиска они изменяются). Ниже даются некоторые пояснительные замечания к рис. 13.10.

После распространения поиска из первоначального дерева (снимок  А)   получается дерево  В.  Вершина  а   - это ИЛИ-вершина, поэтому мы имеем два решающих дерева-кандидата:  b  и  с.   Поскольку  F( b) = 1 < 3 = F( c), для продолжения поиска выбирается альтернатива  b.   Насколько далеко может зайти процесс роста поддерева  b? Этот процесс может продолжаться до тех пор, пока не произойдет одно из двух событий:

    (1)        F-оценка вершины  b  станет больше, чем  F-оценка ее конкурента  с,  или
    (2)        обнаружится, что найдено решающее дерево.

В связи с этим, начиная просмотр поддерева-кандидата  b,  мы устанавливаем верхнюю границу для  F( b):   F( b) <= 3 = F( c). Сначала порождаются преемники  d  и  е  вершины  b    (снимок  С), после чего  F-оценка   b  возрастает до 3. Так как это значение не превосходит верхнюю границу, рост дерева-кандидата с корнем в  b   продолжается. Вершина  d   оказывается целевой вершиной, а после распространения поиска из вершины  е   на один шаг получаем дерево, показанное на снимке  D.  В этот момент выясняется, что  F( b)  =  9   >  3,  и рост дерева  b

Рис. 13. 10.  Трассировка процесса поиска с предпочтением в
И / ИЛИ-графе ( h = 0) при решении задачи рис. 13.4.

прекращается. В результате процесс поиска не успевает "осознать", что  h  -   это тоже целевая вершина и что порождено решающее дерево. Вместо этого происходит переключение активности на конкурирующую альтернативу  с.  Поскольку в этот момент F( b) = 9, устанавливается верхняя граница для  F( c),  равная 9. Дерево-кандидат с корнем  с   наращивается (с учетом установленного ограничения) до тех пор, пока не возникает ситуация, показанная на снимке  Е.  Теперь процесс поиска обнаруживает, что найдено решающее дерево (включающее в себя целевые вершины  h  и  g),  на чем поиск заканчивается. Заметьте, что в качестве результата процесс поиска выдает наиболее дешевое из двух возможных решающих деревьев, а именно решающее дерево рис. 13.4(с).

13. 4. 2.    Программа поиска

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

Существует несколько случаев, как показано на рис. 13.11. Различные формы представления поискового дерева возникают как комбинации следующих возможных вариантов, относящихся к размеру дерева и к его "решающему статусу".

• Размер:
  
  (1)    дерево состоит из одной вершины (листа)
          или
  (2)    оно имеет корень и (непустые) поддеревья.
  
• Решающий статус:
  
  (1)    обнаружено, что дерево соответствует
          решению задачи( т. е. является решающим
          деревом) или
  (2)    оно все еще решающее дерево-кандидат.

Основной функтор, используемый для представления дерева, указывает, какая из комбинаций этих воз-

Рис. 13. 11.  Представление дерева поиска.

можностей имеется в виду. Это может быть одна из следующих комбинаций:

        лист     решлист    дер    решдер

Далее, в представление дерева входят все или некоторые из следующих объектов:

• корневая вершина дерева,
• F-оценка дерева,
• стоимость  С  дуги И / ИЛИ-графа, ведущей в корень дерева,
• список поддеревьев,
• отношение (И или ИЛИ) между поддеревьями.

Список поддеревьев всегда упорядочен по возрастанию  F-оценок. Поддеревья, являющиеся решающими деревьями, помещаются в конец списка.

Обратимся теперь к программе рис. 13.12. Отношение самого высокого уровня - это

        и_или( Верш, РешДер)

где Верш - стартовая вершина. Программа строит решающее дерево (если таковое существует), рассчитывая на то, что оно окажется оптимальным решением. Будет ли это решение в действительности самым дешевым, зависит от той функции  h,  которую использует алгоритм. Существует теорема, в которой говорится о том, как оптимальность решения зависит от  h.  Эта теорема аналогична теореме о допустимости алгоритма поиска с предпочтением в пространстве состояний (гл. 12). Обозначим через  С( В)  стоимость оптимального решающего дерева для вершины  В.   Если для каждой вершины  В  И / ИЛИ-графа эвристическая оценка  h( B) <= C( B),   то гарантируется, что процедура  и_или   найдет оптимальное решение. Если же  h   не удовлетворяет этому условию, то найденное решение может оказаться субоптимальным. Существует тривиальная эвристическая функция, удовлетворяющая условию оптимальности, а именно   h = 0  для всех вершин. Ее недостатком является отсутствие эвристической силы.

Основную роль в программе рис. 13.12 играет отношение

        расширить( Дер, Предел, Дер1, ЕстьРеш)

Дер и Предел - его "входные" аргументы, а Дер1 и ЕстьРеш - "выходные". Аргументы имеют следующий смысл:

Дер - дерево поиска, подлежащее расширению.

Предел - предельное значени  F-оценки, при котором еще разрешено наращивать дерево Дер.

ЕстьРеш - индикатор, значения которого указывают на то, какой из следующих трех случаев имеет место:

    (1)        ЕстьРеш = да: Дер можно "нарастить" (с учетом ограничения Предел) таким образом, чтобы образовалось решающее дерево Дер1.

    (2)        ЕстьРеш = нет: дерево Дер можно расширить до состояния Дер1, для которого F-оценка превосходит Предел, но прежде чем F-оценка превзошла Предел, решающее дерево не было обнаружено.

    (3)        ЕстьРеш = никогда: Дер не содержит решения.

В зависимости от случая Дер1 - это либо решающее дерево, либо Дер, расширенное до момента перехода через Предел; если ЕстьРеш = никогда, то переменная Дер1 неинициализирована.

Процедура

        расширспис( Деревья, Предел, Деревья1, ЕстьРеш)

аналогична процедуре расширить. Так же, как и в процедуре расширить, Предел задает ограничение на рост дерева, а ЕстьРеш - это индикатор, указывающий, каков результат расширения ("да", "нет" или "никогда"). Первый аргумент - это, на этот раз, список деревьев (И-список или ИЛИ-список):

        Деревья = или:[Д1, Д2, ...] или
        Деревья = и : [Д1, Д2, ...]

Процедура расширспис выбирает из списка Деревья наиболее перспективное дерево (исходя из F-оценок). Так как деревья в списке упорядочены, таким деревом является первый элемент списка. Наиболее перспективное дерево подвергается расширению с новым ограничением Предел1. Значение Предел1 зависит от Предел, а также от других деревьев списка. Если Деревья - это ИЛИ-список, то Предел1 устанавливается как наименьшая из двух величин: Предел и F-оценка следующего по "качеству" дерева из списка Деревья. Если Деревья - это И-дерево, то Предел1 устанавливается равным Предел минус сумма F-оценок всех остальных деревьев из списка. Значение переменной Деревья1 зависит от случая, задаваемого индикатором ЕстьРеш. Если ЕстьРеш = нет, то Деревья1 - это то же самое, что и список Деревья, причем наиболее перспективное дерево расширено с учетом ограничения Предел1. Если ЕстьРеш = да, то Деревья1 - это решение для всего списка Деревья (найденное без выхода за границы значения Предел). Если ЕстьРеш = никогда, то переменная Деревья1 неинициализирована.

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

Для отображения решающего дерева можно определить процедуру, аналогичную процедуре отобр (рис. 13.8). Оставляем это читателю в качестве упражнения.

13. 4. 3.    Пример отношений, определяющих конкретную задачу: поиск маршрута

Давайте теперь сформулируем задачу нахождения маршрута как задачу поиска в И / ИЛИ-графе, причем сделаем это таким образом, чтобы наша формулировка могла бы быть непосредственно использована процедурой и_или рис. 13.12. Мы условимся, что карта дорог будет представлена при помощи отношения

        связь( Гор1, Гор2, Р)

означающего, что между городами Гор1 и Гор2 существует непосредственная связь, а соответствующее расстояние равно Р.   Далее, мы допустим, что существует отношение

        клпункт( Гор1-Гор2, Гор3)

имеющее следующий смысл: для того, чтобы найти маршрут из Гор1 в Гор2, следует рассмотреть пути, проходящие через Гор3 ( Гор3 - это "ключевой пункт" между Гор1 и Гор2). Например, на карте рис. 13.1  f   и  g  - это ключевые пункты между  а   и  z:

        клпункт( a-z, f).                 клпункт( a-z, g).

Мы реализуем следующий принцип построения маршрута:

Для того, чтобы найти маршрут между городами   X  и  Z,  необходимо:

    (1)        если между   X  и  Z  имеются ключевые пункты  Y1,   Y2,  ...,  то найти один из путей:

• путь из  X  в  Z  через  Y1,  или
• путь из  X  в  Z  через  Y2,  или
  ...

    (2)        если между   X  и  Z  нет ключевых пунктов, то найти такой соседний с  X   город  Y,  что существует маршрут из  Y  в  Z.

Таким образом, мы имеем два вида задач, которые мы будем представлять как

    (1)        X-Z                             найти маршрут из  X  в  Z

    (2)        X-Z через Y               найти маршрут из  X  в  Z,  проходящий через   Y

Здесь 'через' - это инфиксный оператор более высокого приоритета, чем '-', и более низкого, чем '--->'. Теперь можно определить соответствующий И / ИЛИ-граф явным образом при помощи следующего фрагмента программы:

        :- ор( 560, xfx, через)

        % Правила задачи X-Z, когда между  X  и  Z
        % имеются ключевые пункты,
        % стоимости всех дуг равны 0

        X-Z ---> или : СписокЗадач

        :- bagof( ( X-Z через Y)/0, клпункт( X-Z, Y),
                        СписокЗадач),   !.

        % Правила для задачи X-Z без ключевых пунктов

        X-Z ---> или : СписокЗадач

        :- bagof( ( Y-Z)/P, связь( X, Y, Р), СписокЗадач).

        % Сведение задачи типа ''через" к подзадачам,
           % связанным отношением И

        X-Z через Y---> и : [( X-Y)/0, ( Y-Z)/0].

        цель( Х-Х)         % Тривиальная задача: попасть из X в X

Функцию  h  можно определить, например, как расстояние, которое нужно преодолеть при воздушном сообщении между городами.

Упражнение

13. 4.    Напишите процедуру

        отобр2( РешДер)

для отображения решающего дерева, найденного программой и_или рис. 13.12. Формат отображения пусть будет аналогичен тому, что применялся в процедуре отобр (рис. 13.8), так что процедуру отобр2 можно получить, внеся в отобр изменения, связанные с другим представлением деревьев. Другая полезная модификация - заменить в отобр цель write( Верш) на процедуру, определяемую пользователем

        печверш( Верш, H)

которая выведет Верш в удобной для пользователя форме, а также конкретизирует  Н   в соответствии с количеством символов, необходимом для представления Верш в этой форме. В дальнейшем  Н  будет использоваться как величина отступа для поддеревьев.

Резюме

• И / ИЛИ-граф - это формальный аппарат для представления задач. Такое представление является наиболее естественным и удобным для задач, которые разбиваются на независимые подзадачи. Примером могут служить игры.
• Вершины И / ИЛИ-графа бывают двух типов: И- вершины и ИЛИ-вершины.
• Конкретная задача определяется стартовой вершиной и целевым условием. Решение задачи представляется решающим деревом.
• Для моделирования оптимизационных задач в И / ИЛИ-граф можно ввести стоимости дуг и вершин.
• Процесс решения задачи, представленной И / ИЛИ-графом, включает в себя поиск в графе. Стратегия поиска в глубину предусматривает систематический просмотр графа и легко программируется. Однако эта стратегия может привести к неэффективности из-за комбинаторного взрыва.
• Для оценки трудности задач можно применить эвристики, а для управления поиском - принцип эвристического поиска с предпочтением. Эта стратегия более трудна в реализации.
• В данной главе были разработаны прологовские программы для поиска в глубину и поиска с предпочтением в И / ИЛИ-графах.
• Были введены следующие понятия:
  
          И / ИЛИ-графы
          И-дуги, ИЛИ-дуги
          И-вершины, ИЛИ-вершины
          решающий путь, решающее дерево
          стоимость дуг и вершин
          эвристические оценки в И / ИЛИ-графах
          "возвращенные" оценки
          поиск в глубину в И / ИЛИ-графах
          поиск с предпочтением в И / ИЛИ-графах

Литература

И / ИЛИ-графы и связанные с ними алгоритмы поиска являются частью классических механизмов искусственного интеллекта для решения задач и реализации машинных игр. Ранним примером прикладной задачи, использующей эти методы, может служить программа символического интегрирования (Slagle 1963). И / ИЛИ-поиск используется в самой пролог-системе. Общее описание И / ИЛИ-графов и алгоритма можно найти в учебниках по искусственному интеллекту (Nilsson 1971; Nilsson 1980). Наша программа поиска с предпочтением - это один из вариантов алгоритма, известного под названием АО* . Формальные свойства АО* -алгоритма (включая его допустимость) изучались несколькими авторами. Подробный обзор полученных результатов можно найти в книге Pearl (1984).

Nilsson N.J. (1971). Problem-Solving Methods in Artificial Intelligence. McGraw-Hill.

Nilsson N.J. (1980). Principles of Artificial Intelligence. Tioga; also Springer-Verlag.

Pearl J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley.

Slagle J.R. (1963). A heuristic program that solves symbolic integration problems in freshman calculus. In: Computers and Thought (E. Feigenbaum, J. Feldman, eds.). McGraw-Hill.

Назад | Содержание | Вперёд