В противоположность поиску в глубину стратегия поиска в ширину предусматривает переход в первую очередь к вершинам, ближайшим к начальной вершине. На следующем рисунке показан пример, который иллюстрирует работу алгоритма поиска в ширину.
Поиск в ширину программируется не так легко, как поиск в глубину. Причина состоит в том, что приходится сохранять все множество альтернативных вершин-кандидатов, а не только одну вершину как при поиске в глубину. Более того, если при помощи процесса поиска необходимо получит решающий путь, то следует хранить не множество вершин-кандидатов, а множество путей-кандидатов. Для представления множества путей-кандидатов обычно используют списки, однако при таком способе одинаковые участки путей хранятся в нескольких экземплярах. Избежать подобной ситуации можно, если представить множество путей-кандидатов в виде дерева, в котором общие участки путей хранятся в его верхней части без дублирования. При реализации стратегии поиска в ширину решающие пути порождаются один за другим в порядке увеличения их длин, следовательно, стратегия поиска в ширину гарантирует получение кратчайшего решения первым.
Представленные выше стратегии поиска в глубину и поиска в ширину не учитывают стоимости, приписанной дугам в пространстве состояний. Если критерием оптимальности является минимальная стоимость пути, а не его длина, то в данном случае поиск в ширину не решает поставленную задачу.
Еще одна проблема, возникающая при решении задачи поиска – это проблема комбинаторной сложности. Для сложных предметных областей число альтернатив столь велико, что проблема сложности часто принимает критический характер, так как длина решающего пути (тем более, если их множество, как при реализации поиска в ширину) может привести к экспоненциальному росту длины в зависимости от размерности задачи, что приводит к ситуации, называемой комбинаторным взрывом. Стратегии поиска в глубину и в ширину недостаточно «умны» для борьбы с такой ситуацией, так как все пути рассматриваются как одинаково перспективные.
По-видимому, процедуры поиска должны использовать какую-либо информацию, отражающую специфику данной задачи, с тем, чтобы на каждой стадии поиска принимать решения о наиболее перспективных путях поиска. В результате процесс будет продвигаться к целевой вершине, обходя бесполезные пути. Информация, относящаяся к конкретной решаемой задаче и используемая для управления поиском, называется эвристикой. Алгоритмы поиска, использующие эвристики, называют эвристическими алгоритмами.
Одним из эвристических алгоритмов решения задач является алгоритм А*, который является усовершенствованным алгоритмом поиска в ширину. Это, так называемый, алгоритм поиска по заданному критерию. Для каждого возможного перехода за один шаг определяется эвристическая оценка и для продолжения поиска решающего пути выбирается наилучшая в соответствии с данной оценкой вершина.
Предполагается, что для всех дуг в пространстве состояний определена функция стоимости перемещения от вершины к вершинам-преемникам. Допустим, для эвристической оценки применяется функция f(n) такая, что для каждой вершины n она служит для оценки «сложности достижения n». Соответственно наиболее перспективной является та вершина, для которой значение функции f(n) является минимальным. Рассмотрим алгоритм А* на примере решения задачи «игра в восемь».
На следующем рисунке представлена задача «игра в восемь» в виде задачи поиска пути в пространстве состояний. В головоломке используется восемь перемещаемых фишек, пронумерованных цифрами от 1 до 8. Фишки располагаются в девяти ячейках, образующих матрицу 3х3. Одна из ячеек всегда пуста, любая смежная с ней фишка может быть передвинута в эту ячейку. Конечная ситуация – это некоторая заранее заданная конфигурация фишек.
При этом можно выделить четыре основных оператора:
1. Перемещение пустой фишки вниз;
2. Перемещение пустой фишки вверх;
3. Перемещение пустой фишки влево;
4. Перемещение пустой фишки вправо.
Оценочная функция f(n) формируется как стоимость оптимального пути к цели из начального состояния через n вершин дерева поиска. Значение оценочной функции для вершины n равно: f(n)=g(n)+h(n), где g(n) – стоимость оптимального пути от начальной вершины до n-ой, а h(n) – стоимость оптимального пути от n-ой вершины до целевой. Понятно, что h(n) это эвристическая гипотеза, основанная на имеющейся информации о данной конкретной задаче.
При этом g(n) принимается равной глубине пройденного пути на дереве поиска от начальной вершины до n-ой, а h(n) – расстояние Хемминга от n-ой вершины до целевой (в данном случае оно равно числу фишек, стоящих не на своих местах). Существует модификация алгоритма А*, в которой представляет сумму манхэттеновских расстояний (считается как сумма расстояний в горизонтальном и вертикальном направлениях) от каждой фишки до ёё «целевой клетки» плюс утроенное значение «оценки упорядоченности». Оценка упорядоченности определяет степень упорядоченности фишек текущей позиции по отношению к целевой позиции и высчитывается по следующим правилам:
· Фишка в центре имеет оценку 1;
· Фишка в другой позиции имеет оценку 0, если за ней в направлении по часовой стрелке следует соответствующий ей преемник;
· Фишка в другой позиции имеет оценку 2, если за ней в направлении по часовой стрелке не следует соответствующий ей преемник.
Стратегия выбора следующей вершины в пространстве состояний – минимальное значение оценочной функции.
Формулировка алгоритма:
1. Рассматриваем все варианты перемещения пустой фишки за один шаг и выбираем вариант с минимальной оценкой h(n).
2. Переходим в новое состояние.
3. Создаём вершины следующего уровня иерархии.
4. Выбираем состояние с минимальной оценкой h(n).
5. Повторяем до тех пор, пока не достигнем цели.
Цель не будет достигнута до тех пор, пока число перемещений меньше числа фишек, находящихся не на своих местах.
Для задачи, изображённой на рисунке, алгоритм находит решение за два шага. От начальной вершины возможен переход в два состояния с оценочной стоимостью f(1)=n+h(1)=1+4+3*(1+2)=14 и f(2)=1+3+3*(1+2+2)=19. Выбираем минимальную стоимость и переходим в состояние 1. Далее генерируем вершины 3 и 4 с оценочными стоимостями соответственно f(3)=2+2+3*(1+2+2)=19 и f(4)=2+0=2. Последняя вершина является целевой.
В соответствии с модифицированным алгоритмом оценочные стоимости вершин на первом шаге равны f(1)=n+h(1)=1+2=3 и f(2)=1+3=4
4.3 Сведение задачи к подзадачам и И/ИЛИ графы.
Для некоторых категорий задач более естественным решением является разбиение задачи на подзадачи. Разбиение на подзадачи дает преимущество в том случае, когда подзадачи взаимно независимы, и, следовательно, решать их можно независимо друг от друга. Проиллюстрируем это на примере решения задачи поиска на карте дорог маршрута между заданными городами как показано на рисунке.
Вершинами a,b,c,d,f,h,z – представлены города. Расстояние между городами обозначено весом дуги из одной вершины графа в другую. На карте есть река. Допустим, что переправиться через реку можно только по двум мостам: один находится в городе f, а второй – в городе d. Очевидно, что искомый маршрут обязательно должен проходить через один из мостов, а значит должен проходить либо через f, либо через d. Таким образом, мы имеем две главные альтернативы:
· путь из a в z, проходящий через f;
· путь из a в z, проходящий через d.
Затем, каждую из этих двух альтернативных задач можно, в свою очередь, разбить следующим образом:
1. для того, чтобы найти путь из a в z через f, необходимо:
· найти путь из a в f и
· найти путь из f в z.
2. для того, чтобы найти путь из a в z через d, необходимо:
· найти путь из a в d и
· найти путь из d в z.
Таким образом, в двух альтернативах мы получили четыре подзадачи, которые можно решать независимо друг от друга. Полученное разбиение исходной задачи можно изобразить в форме И/ИЛИ – графа, представленного на рисунке.
Круглые дуги на графе указывают на отношениеИмежду соответствующими подзадачами. Задачи более низкого уровня называются задачами-преемниками.
И/ИЛИ- граф- это направленный граф, вершины которого соответствуют задачам, а дуги – отношениям между задачами.
Между дугами также существуют свои отношения – это отношения И и ИЛИ, в зависимости от того, должны ли мы решить только одну из задач-преемников или же несколько из них. В принципе из верщины могут выходить дуги, находящиеся в отношении И вместе с дугами, находящимися в отношении ИЛИ. Тем не менее, будем предполагать, что каждая верщина имеет либо только И-преемников, либо только ИЛИ-преемников, так как в такую форму можно преобразовать любой И/ИЛИ- граф, вводя в него при необходимости вспомогательные ИЛИ-вершины. Вершину, из которой выходят только И- дуги называются И- вершиной; вершину, из которой выходят только ИЛИ- дуги,- ИЛИ- вершиной.
Решением задачи, представленной в виде И/ИЛИ- графа является решающее дерево, так как решение должно включать в себя все подзадачи И-вершин.
Решающее дерево T определяется следующим образом:
· исходная задача P – это корень дерева T;
· если P является ИЛИ-вершиной, то в T содержится только один из ее преемников (из И/ИЛИ-графа) вместе сос своим собственным решающим деревом;
· если P – это И-вершина, то все ее преемники (из И/ИЛИ-графа) вместе со своими решающими деревьями содержатся в T.
На представленном выше И/ИЛИ- графе представлены три решающих дерева, обозначенных штих-пунктирной, пунктирной и сплошной линиями. Соответственно, стоимости данных деревьев составляют 7, 12, 7. В данном случае стоимости определены как суммы стоимостей всех дуг дерева. Иногда стоимость решающего дерева определяется сумой стоимостей всех его вершин. В соответствии с заданным критерием, из всех решающих деревьев выбирается оптимальное.
4.4 Решение игровых задач в терминах И/ИЛИ- графа
Такие игры, как шахматы или шашки, естественно рассматривать как задачи, представленные И/ИЛИ- графами. Игры такого рода называются играми двух лиц с полной информацией. Будем считать, что существует только два возможных исхода игры:
· выигрыш;
· проигрыш.
Игры с тремя возможными исходами можно свести к играм с двумя исходами, считая, что есть: выигрыш и невыигрыш.
Так как участники игры ходят по очереди, то выделим два вида позиций, в зависимости от того, чей ход:
· позиция игрока;
· позиция противника.
Допустим, что начальная позиция P – это позиция игрока. Каждый вариант хода игрока в этой позиции приводит к одной из позиций противника G1, G2, G3 и так далее. Каждый вариант хода противника в позиции Gi приводит к одной из позиций игрока Pij.
В И/ИЛИ- дереве, показанном на рисунке, вершины соответствуют позициям, а дуги – возможным ходам. Уровни позиций игрока чередуются в дереве с уровнями позиций противника. Игрок выигрывает в позиции P, если он выигрывает в G1, G2, G3 и так далее. Следовательно, P – это ИЛИ-вершина. Позиции Gi – это позиции противника, поэтому если в этой позиции выигрывает игрок, то он выигрывает и после каждого варианта хода противника, то есть игрок выигрывает в Gi, если он выигрывает во всех позициях Pij. Таким образом, все позиции противника – это И-вершины. Целевые позиции – это позиции, выигранные согласно правилам игры. Для того, чтобы решить игровую задачу, мы должны построить решающее дерево, гарантирующее победу игрока независимо от ответов противника. Такое дерево задает полную стратегию достижения выигрыша: для каждого возможного продолжения, выбранного противником, в дереве стратегии есть ответный ход, приводящий к победе.
…. ….
Рассмотрим решение подобных задач на примере игры в «2 лунки».
Игрок или его противник может взять из одной любой лунки любое количество камешков. Проигрывает тот, кто берет последний камешек.
Дерево решений этой игры представлено на рисунке.
Пунктирной линией обозначена оптимальная стратегия игрока, которая приведет к выигрышу.
