Эвристический метод поиска решений на графе.
Алготирм:
1) Cоздать граф поиска G (с вершиной S0). Занести S0 в список открытых (OPEN)-вершины, возможные кандидаты на раскрытие;
2) Cоздать список закрытых вершин (CLOSED)- в него заносится вершины, путь до которых из S0 найден;
3) Цикл, если список открыт, вершины пусты, то неудача. Конец.
4) Инече:Выбрать первую вершину. N из OPEN перенести в CLOSED
5) Если n- целевая, конец, успех;
6) Раскрыть n - найти множество ее потомков, не являющихся ее предками;
7) Выбрать из n те вершины, которые не встречались в графе поиска G (ни в OPEN, ни в CLOSED). Добавить их в OPEN, связать указателем с вершиной n. Для тех элементов из n, которые, уже есть в списке CLOSED, решить надо ли переустанавливать указатели.
8)Переупорядочить OPEN в соответствии с некоторой произвольной схемой или эвристической зависимостью. Фактически это - выбор одного из возможных путей.
9) Перейти на метку Цикла.
Пример: Игра в восьмерки. Пусть эвристическая функция f(n)=d(n)+W(n).
f(n)-сумма кол-ва ранее сделанных шагов и кол-ва фишек на своем месте.
d - глубина поиска или количество шагов от исходной.
W - количество фишек, стоящих не на своем месте.
Наилучшим будет считаться ход, у которого функция f - максимальна: