Лабораторная работа №3. РЕАЛИЗАЦИЯ ПОИСКА В СИСТЕМАХ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА

РЕАЛИЗАЦИЯ ПОИСКА В СИСТЕМАХ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА

В системах искусственного интеллекта различают слепой и эвристический поиск. Два основных подвида слепого поиска, различающиеся порядком раскрытия вершин, – это поиск в ширину и поиск в глубину, которые различаются выбором очередной вершины для очередного раскрытия. В алгоритме перебора в ширину вершины раскрываются в том порядке, в котором они строятся. В алгоритме же перебора в глубину прежде всего раскрываются те вершины, которые были построены последними.

Рассмотрим в качестве примера логическую задачу о «Ханойских башнях». Общий вид ее приведен на рисунке 7.

Рис. 7

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

Представим поиск решения приведенной задачи в виде графа в котором каждая из вершин будет являться очередным этапом, характеризующим перемещение одного из дисков на новую башню с собдюдением условий задачи. Условно примем запись нахождения соответствующего диска на соответствующей башне в следующем виде, который отвечает приведенной на рисунке 8 записи задачи: (ААА), где вершина А является исходной для рассматриваемой задачи, а вершина В на которую необходимо переместить все диски - целевой. Т.е.: диск самого большого диаметра находится на диске А – первая из букв; диск среднего диаметра находится на диске А – вторая из букв; диск наименьшого диаметра находится на диске А – третья из букв. Результат решения представлен на рисунке 8.

рис. 8

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

Рис.9. Поиск в ширину

Часть дерева, построенного в результате применения алгоритма поиска вширь к некоторой начальной конфигурации рассматриваемой задачи, причем выполнение алгоритма прервано после построения первых 9 вершин, при котором раскрыто 5 вершин. В вершинах дерева помещены соответствующие описания состояний. Эти вершины пронумерованы в том порядке, в котором они были построены в ходе поиска. На следующем шаге цикла алгоритма будет раскрываться одна из вершин с номерами 6 или 9.

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

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

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

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

На рис.10 показана часть дерева разбора, построенного на основе реализации поиска в глубину при граничной глубине равной 4. В качестве начального состояния взята та же самая конфигурация расмотренной задачи, приведенной в примере на рис.7. В ходе поиска построено 9 вершин и раскрыто 5. Вершины перенумерованы в том порядке, в котором они были построены. Как нетрудно убедиться, сравнивая два указанных рисунка с алгоритмами поиска в ширину и в глубину построены разные деревья поиска. Видно, что в алгоритме поиска в глубину сначала идет поиск вдоль одного пути, пока не будет достигнута установленная граничная глубина, затем рассматриваются альтернативные пути той же или меньшей глубины, которые отличаются от первого пути лишь последней вершиной от которой началось ветвление, и т.д.

Рис.10. Поиск в глубину

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

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

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

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

Рассмотрим реализацию эвристического поиска на рассмотренном выше примере (рис. 7). Первоначально необходимо определение параметров эвристической функции[1]. Одним из очевидных параметров является «нахождение диска на целевой башне» - . Для того, чтобы значение эвристической функции вершины графа на очередном этапе было не меньше значения функции предыдущих этапов дополнительно с указанным параметром необходимо учитывать глубину поиска . Тогда значение эвристической функции .

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

Рис. 11

После раскрытия вершины <ВБА> дальнейший разбор теряет смысл. Один из параметров эвристической функции не позволил повлиять на предсказуемость разбора. Более того - диск находящийся на целевой вершине пришлось переместить. Необходимо конретизировать данный параметр. Причиной перемещения диска с целевой башни стало несоответствие его расположения, зависящее от диаметра. Тогда параметр должен отражать нахождение диска на целевой вершине в соответствии с иерархией раположения. Кроме того необходимо введение нового параметра «готовность перемещения на целевую вершину в соответствии с иерархией раположения» - Тогда, . Результаты разбора приведены на рисунке 12.

Решение задачи глубиною найдено в результате раскрытия 9 и построения 13 вершин – это меньше, чем при использовании слепого перебора. Если построение дерева разбора обход осуществлять слева-направо тогда потребуется построить все 27 вершин графа. Но поиск в глубину с обходом справа-налево дает самый лучший результат даже в сравнении с эвристическим поиском - раскрыто 7 и построено 7 вершин. Но это лишь частный случай. Чаще использование эвристической информации приводит к существенному сокращению перебора.

Рис. 12

Очевидно, что алгоритм эвристического поиска с хорошо подобранной оценочной функцией находит решение задачи быстрее алгоритмов слепого перебора. Однако подбор удачной эвристической функции, существенно сокращающей поиск, – наиболее трудный момент при формализации задачи.

На основе рассмтренных алгоритмов посика в системах искусственного интеллекта приведен основные понятия необходимые при его формализации.

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

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

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

Таблица 1

Прим. 1 – максимальный диаметр, далее – по убыванию.