Алгоритм оценочных (штрафных) функций
Умело подобранные оценочные функции (в некоторых источниках - штрафные функции) могут значительно сократить полный перебор и привести к решению достаточно быстро в сложных задачах. В нашей задаче о людоедах и миссионерах в качестве самой простой целевой функции при выборе очередного состояния можно взять число людоедов и миссионеров, находящихся "не на месте" по сравнению с их расположением в описании целевого состояния. Например, значение этой функции f=x+y для исходного состоянияf0=6, а значение для целевого состояния f1=0.
Эвристические процедуры поиска на графе стремятся к тому, чтобы минимизировать некоторую комбинацию стоимости пути к цели и стоимости поиска. Для задачи о людоедах введем оценочную функцию:
f(n) = d(n) + w(n)
где d(n) - глубина вершины n на дереве поиска и w(n) - число находящихся не на нужном месте миссионеров и людоедов. Эвристика заключается в выборе минимального значения 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.
|
h1 S0 S1 |
5 >18 |
13 100-8!(=40320) |
8 | Поиск в ширину |
|
h2 S0 S1 |
5 18 |
11 43 |
8*2+8+1+1 | Поиск в глубину |