Информированный поиск. 
Системы искусственного интеллекта

В предыдущем разделе было показано, что в условиях отсутствия информации задача поиска может быть решена успешно, но при этом затраты времени и памяти могут быть совершенно неприемлемыми. Если задачу о ферзях попытаться решить на доске 100*100, то количество состояний будет около 10⁴⁰⁰. Пусть вас не введет в заблуждение компактная экспоненциальная форма представления этого числа. Число атомов в видимой части вселенной составляет около 10⁸⁰.

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

Рассмотрим следующую задачу. Пусть нам нужно добраться из Таллина в Москву воздушным транспортом. Расстояния между городами и воздушные трассы показаны на рис. 2.3.

Рис. 2.3. Пример воздушных трасс к задаче поиска.

Если бы мы не располагали никакими данными о расстояниях, то имел бы место слепой (неинформированный) поиск. Если мы знаем только расстояние от текущей точки до соседних, то мы в состоянии выполнить поиск по критерию стоимости. Ближайший пункт от Таллина — Хельсинки (100 км), затем — Петербург (295), Рига (476), Тверь (716), Москва (161). Общая протяженность пути — 1748 км, и она существенно отличается от оптимальной — 957 км.

Предположим, что нам известно расстояние от каждого из городов до Москвы по прямой (рис. 2.4).

Эта информация может использоваться для выбора следующего пункта маршрута. Так, доступными пунктами из Таллина являются Хельсинки (897 км), С. Петербург (634) и Рига (839). Стремясь на каждом шаге максимально приблизиться к цели, мы выберем на первом шаге С. Петербург, на втором шаге —.

Тверь, затем — Москву. Общая протяженность пути равна оптимальной.

Данный вид поиска называется жадным поиском по первому наилучшему соответствию. Каждый последующий узел для развертывания выбирается на основе функции оценки f (п). В связи с тем, что мы не располагаем точными оценками, используются эвристические функции h (п) или эвристики. В рассмотренном примере эвристическая функция — это расстояние до цели по прямой.

Рис. 2.4. Расстояния до пункта назначения по прямой.

Эта эвристика не является заведомо оптимальной. Если, например, между Тверью и Москвой самолеты не летают, то оптимальный маршрут Таллин — Рига — Москва будет существенно отличаться от предложенного алгоритмом жадного поиска по первому наилучшему совпадению: Таллин — С. Петербург — Тверь — Рига — Москва.

Жадный поиск по первому наилучшему совпадению напоминает поиск в глубину и страдает от тех же недостатков. На последней схеме без предотвращения повторяющихся состояний возможно бесконечное блуждание по отрезку С. Петербург — Тверь — С. Петербург и т. д. В наихудшем варианте сложность метода составляет b^m, где b — коэффициент ветвления, m — максимальная глубина пространства поиска. Однако, хорошая эвристическая функция позволяет существенно снизить такую сложность.

Рис. 2.5. Жадный поиск по первому наилучшему соответствию.

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

где g (п) — стоимость достижения n-го узла, h (п) — эвристическая функция стоимости достижения цели из n-го узла.

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

Следовательно, для развертывания узла будет выбран С.-Петербург, как имеющий минимальное значение функции оценки.

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

Следующим пунктом маршрута будет выбрана Тверь.

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

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

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

В задачах поиска важным является рациональный выбор эвристической функции. Рассмотрим еще один пример логической задачи. У нас она известна как игра «15». Мы же рассмотрим упрощенный вариант на девяти клетках с восемь фишками (игра «8»). Начальное и конечное состояния могут быть, например, следующими.

Фишки можно двигать по горизонтали и вертикали на свободную клетку. Средняя сложность решения составляет 22 хода. Коэффициент ветвления — 3 (4, если свободная клетка в центре, 2, если — в углу). Число состояний примерно З²² или 3.1 *10¹⁰. Устраняя повторяющиеся состояния, можно сократить их количество примерно в 170 000 раз. Это состояние уже поддается контролю, но соответствующее количество состояний для игры в 15 равно 10¹³, поэтому нужно найти хорошую эвристическую функцию. В качестве таких могут использоваться следующие функции:

h₂ — количество фишек, стоящих не на своем месте. На левом рисунке все фишки стоят не на своем месте, т. е. = 8. Данная эвристическая функция является допустимой, поскольку каждую фишку, стоящую не на своем месте, нужно переместить, по меньшей мере, один раз.

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

h₂ = 18.

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

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

Рис. 2.6. Локальный максимум и плато.

1. Локальные максимумы. Преодолеть их локальный поиск не в состоянии.

2. Плато. Область, в которой эвристика не меняется от хода к ходу.

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

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

• 1. Выбираются позиции с лучшими значениями эвристик (отбор).
• 2. Доска «разрезается» по вертикали или по горизонтали, и части доски от разных позиций соединяются вместе (скрещивание).
• 3. В полученные новые комбинации вносятся случайные изменения (мутации).
• 4. Если полученная позиция хуже предыдущих, она отбрасывается, если лучше, запоминается (отбор).
• 5. Из имеющихся лучших позиций все повторяется с п. 2.

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