ючается в выборе минимального значения f(n). Определяющим в эвристических процедурах является выбор оценочной функции.
Рассмотрим вопрос о сравнительных характеристиках оценочных целевых функций на примере функций для игры в "8" ("пятнашки"). Игра в "8" заключается в нахождении минимального числа перестановок при переходе из исходного состояния в конечное (терминальное, целевое).
2
8
3
1
6
4
7
5
1
2
3
8
4
7
6
5
Рассмотрим две оценочные функции:
h1(n) & Q(n)
h2(n) & P(n) 3S(n),
где Q(n) - число фишек не на месте; P(n) - сумма расстояний каждой фишки от места в ее целевой вершине; S(n) - учет последовательности нецентральных фишек (штраф 2 если за фишкой стоит не та, которая должна быть в правильной последовательности; штраф 1 за фишку в центре; штраф 0 в остальных случаях).
Сравнение этих оценочных функций приведено в таблица 3. 1.
Таблица 3. 1. Сравнение оценочных функций
Оценочная функция h
Стоимость (длина) пути L
Число вершин, открытых при нахождении пути N
Трудоемкость вычислений, необходимых для подсчета h S
Примечания
h1 S0
S1
5
18
13
100-8!(40320)
8
Поиск в ширину
h2 S0
S1
5
18
11
43
82811
Поиск в глубину
На основе сравнения этих двух оценочных функций можно сделать выводы.
Основу алгоритма поиска составляет выбор пути с минимальной оценочной функцией.
Поиск в ширину, который дает функция h1, гарантирует, что какой-либо путь к цели будет найден. При поиске в ширину вершины раскрываются в том же порядке, в котором они порождаются.
Поиск в глубину управляется эвристической компонентой 3S(n) в функции h2 и при
Страницы: << < 2 | 3 | 4 | 5 | 6 > >>