Лекция: Эвристический поиск.

В [Polya, 1945] эвристика определяется как «изучение методов и правил открытий и изобретений». Это слово имеет греческий корень, глагол euriscoозначает «исследовать». Когда Архимед выскочил из ванны, держа золотой венец, он закричал «Эврика!», что значит «Я нашел!». В пространстве состояний поиска эвристика определяется как набор правил для выбора тех ветвей из пространства состояний, которые с наибольшей вероят­ностью приведут к приемлемому решению проблемы.

Специалисты по искусственному интеллекту используют эвристику в двух ситуациях.

1. Проблема может не иметь точного решения из-за неопределенности в поста­новке задачи и/или в исходных данных. Медицинская диагностика – пример такой проблемы. Определенный набор признаков может иметь несколько при­чин; поэтому врачи используют эвристику, чтобы поставить наиболее точный диагноз и подобрать соответствующие методы лечения. Система технического зрения — другой пример задачи с неопределенностью. Визуальные сцены час­то неоднозначны, вызывают различные (часто не связанные друг с другом) предположения относительно протяженности и ориентации объектов. Оптический обман — хорошая иллюстрация таких двусмысленностей. Системы тех­нического зрения часто используют эвристику для выбора наиболее вероятной интерпретации из нескольких возможных.

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

К сожалению, подобно всем правилам открытия и изобретения, эвристика может ошибаться. Эвристика — это только предложение следующего шага, который будет сде­лан на пути решения проблемы. Такие предположения часто основываются на опыте или интуиции. Поскольку эвристика использует такую ограниченную информацию, как опи­сание текущих состояний в списке open, то она редко способна предсказать дальнейшее поведение пространства состояний. Эвристика может привести алгоритм поиска к субоп­тимальному решению или не найти решение вообще. Это ограничение присуще эвристи­ческому поиску и не может быть устранено «лучшей» эвристикой или более эффектив­ным алгоритмом поиска [Garey и Johnson, 1979].

Эвристика и разработка алгоритмов для эвристического поиска в течение доста­точно долгого времени остаются основным объектом исследования в проблемах ис­кусственного интеллекта. Игра и доказательство теорем — два самых старых при­ложения в области искусственного интеллекта; оба они нуждаются в эвристике для сокращения числа состояний в пространстве поиска. Невозможно рассмотреть каж­дый вывод, который может быть сделан в той или иной области математики, или каждый возможный ход на шахматной доске. Эвристический поиск — часто единст­венный практический метод решения таких проблем.

Исследование в области экспертных систем подтвердило важность эвристики как основного компонента при решении задач. Эксперт-человек, решая проблему, анализирует доступную информацию и делает вывод. Интуитивные правила («rules of thumb»), кото­рые использует эксперт, чтобы эффективно решить ту или иную проблему, в значитель­ной степени эвристичны по природе. Такие эвристики были созданы и формализованы разработчиками экспертных систем.

Эвристические алгоритмы состоят из двух частей: эвристической меры и алгорит­ма, который использует ее для поиска в пространстве состояний

10.3.1. «Жадный» алгоритм поиска

Наиболее простой путь эвристического поиска — это применение процедуры поиска экстремума (hill climbing). Стратегии, основанные на поиске экстремума, оценивают не только текущее состояние поиска, но и его потомков. Для дальнейшего поиска выбирается наилучший потомок; при этом о его братьях и родителях просто забывают. Поиск прекра­щается, когда достигается состояние, которое лучше чем любой из его наследников. Поиск экстремума — название стратегии, которая может быть использована энергичным, но сле­пым альпинистом, поднимающимся вдоль наиболее крутого склона до тех пор, пока он не сможет идти дальше. Так как в этой стратегии данные о предыдущих состояниях не сохра­няются, то алгоритм не может быть восстановлен из точки, которая привела к «неудаче».

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

сдвинуть фишку, находящуюся в наилучшей позиции. Без этого невозможно решить головоломку, но в то же время на данном этапе это ухудшает состояние системы. Дело в том, что «лучший» не означает «идеальный». Методы поиска без механизмов возврата или других приемов восстановления не могут отличить локальный максимум от глобаль­ного. Существуют методы приближенного решения этой проблемы, например, случайное возмущение оценки. Однако гарантированно решать задачи с использованием техники поиска экстремума нельзя.

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

Подобно алгоритмам поиска в глубину и алгоритмам поиска в ширину, описанными ранее, «жадный» алгоритм поиска использует списки сохраненных состояний: список open

отслеживает текущее состояние поиска, а в closed записываются уже проверенные

состояния. На каждом шаге алгоритм записывает в список open состояние с учетом некоторой эвристической оценки его «близости к цели». Таким образом, на каждой итерации рассматриваются наиболее перспективные состояния из списка open.

На каждой итерации функция best_first_search, реализующая «жадный» алгоритм удаляет первый элемент из списка open. Достигнув цели, алгоритм возвращает путь, который ведет к решению. За­метим, что каждое состояние сохраняет информацию о предшествующем состоянии, чтобы впоследствии восстановить его и позволить алгоритму найти кратчайший путь к решению.

Если первый элемент в списке open не является решением, то алгоритм использует процедуры, чтобы сгенерировать все возможные потомки данного элемента. Если потомок уже находится в списке open или closed, то ал­горитм выбирает кратчайший из двух возможных путей достижения этого состояния. Затем функция best_first_search вычисляет эвристическую оценку состояний в списке open и сортирует список в соответствии с этими эвристическим значениям. При этом «лучшие» состояния ставятся в начало списка. Заметим, что из-за эвристической природы оценивания следующее состояние должно проверяться на любом уровне про­странства состояний. Отсортированный список open часто называют прuорuтетной очередью(priority queue).

Рис. 10.12. Эвристический поиск в гипотетическом пространстве состояний.

На рис. 10.12 показано гипотетическое пространство с эвристическими оценками некото­рых из его состояний. Состояния, рядом с которыми стоит их эвристическая оценка, были сгенерированы функцией best_first_search. Состояния, по которым велся эвристи­ческий поиск, отмечены полужирном шрифтом; заметьте, что поиск не ведется по всему пространству. Другими словами, цель «жадного» алгоритма поиска состоит в том, чтобы прийти к целевому состоянию кратчайшим путем. Чем более обоснованной является эври­стика, тем меньше состояний нужно проверить при поиске цели.

Путь, по которому функция best_first_search находит целевое состояние, по­казан на рисунке жирными стрелками. Предположим, что Р- целевос состояние (см. рис. 10.12). Поскольку Р — цель, состояния на пути к Римеют низкие эвристические зна­чения. Эвристика подвержена ошибкам: состояние О имеет более низкое эвристическое значение, чем целевое, и поэтому было исследовано раньше. В отличие от поиска экстре­мума, который не сохраняет приоритетную очередь для отбора «следующих» состояний, данный алгоритм восстанавливается после ошибки и находит целевое состояние.

Ниже показан процесс реализации алгоритма best_first_search для графа из рис. 10.12., при этом Р — это желаемое целевое состояние.

Таблица 10.4. Состояние списков после каждой итерации «жадного» алгоритма поиска для графа на рис. 10.12.

0 итерация — Инициализируем списки. Список open =[A-5]; Списокclosed =[ ];

1 итерация – Выбираем первую вершину из списка openи определяем её как текущее состояние Х=А-5. Применяем процедуру определения потомков к Х=А-5, потомки есть, ими являются вершины В-4, С-4, D-6. Записываем слева направо эти вершины в список openв порядке возрастания эвристических оценок этих вершин,удаляя слева из этого списка вершину А-5 и записывая эту вершину в списокclosed слева направо. Далее алгоритм переходит к следующей итерации.

2 итерация – Выбираем первую вершину из списка openи определяем её как текущее состояние Х=В-4. Применяем процедуру определения потомков к Х= В-4, потомки есть, ими являются вершины Е-5, F-5. Записываем слева направо эти вершины в список openв порядке возрастания эвристических оценок этих вершин, удаляя слева из этого списка вершину В-4 и записывая эту вершину в списокclosed слева направо.

Далее алгоритм переходит к следующей итерации. Эти итерации продолжаются до тех пор пока текущее состояние Х не будет равно целевому состоянию P-3.

«Жадный» алгоритм поиска всегда выбирает наиболее перспективное и лучшее состояние в open для продолжения, кстати поэтому его назвали «жадным». Однако, поскольку при выборе состояния используется эври­стика, которая может оказаться ошибочной, алгоритм не отказывается от остальных состояний, и сохраняет их в списке open. В данном случае эвристика обеспечивает поиск вниз; этот путь оказывается ошибочным, но алгоритм в итоге возвращается к некоторому ранее сгенерированному «лучшему» состоянию в open и затем продолжа­ет поиск в другой части пространства. В примере на рис. 10.12 после нахождения потом­ков состояния В оказалось, что они имеют плохие эвристические оценки, и поэтому по­иск сместился к состоянию С. При этом потомки состояния В были сохранены в open на случай, если алгоритму необходимо будет вернуться к ним позже. В функции best_first_search, как и в описаных ранее алгоритмах, список open позволяет воз­вращаться назад по ошибочному пути.