Prolog

случае, условием допустимости следует считать оптимальность первого из найденных решений. Обозначим через h*(n)  стоимость оптимального пути из произвольной вершины  n   в целевую вершину. Верна следующая теорема о допустимости А*-алгоритма:  А*-алгоритм, использующий эвристическую функцию  h,   является допустимым, если

        h( n) <= h*( n)

для всех вершин  n  пространства состояний.

Этот результат имеет огромное практическое значение. Даже если нам не известно точное значение  h*,  нам достаточно найти какую-либо нижнюю грань  h*  и использовать ее в качестве  h  в А*-алгоритме - оптимальность решения будет гарантирована.

Существует тривиальная нижняя грань, а именно:

        h( n) = 0,                         для всех вершин  n  пространства состояний.

И при таком значении  h  допустимость гарантирована. Однако такая оценка не имеет никакой эвристической силы и ничем не помогает поиску. А*-алгоритм при  h=0  ведет себя аналогично поиску в ширину. Он, действительно, превращается в поиск в ширину, если, кроме того, положить  с(n, n' )=1  для всех дуг  (n, n')   пространства состояний. Отсутствие эвристической силы оценки приводит к большой комбинаторной сложности алгоритма. Поэтому хотелось бы иметь такую оценку  h,   которая была бы нижней гранью  h*   (чтобы обеспечить допустимость) и, кроме того, была бы как можно ближе к  h*  (чтобы обеспечить эффективность). В идеальном случае, если бы нам была известна сама точная оценка  h*,   мы бы ее и использовали: А*-алгоритм, пользующийся   h*,  находит оптимальное решение сразу, без единого возврата.

Упражнение

12. 1.    Определите отношения после, цель и  h  для задачи поиска маршрута рис. 12.2. Посмотрите, как наш алгоритм поиска с предпочтением будет вести себя при решении этой задачи.

Назад | Содержание | Вперёд

Назад | Содержание | Вперёд

12. 2.    Поиск c предпочтением применительно к головоломке 'игра в восемь'

Если мы хотим применить программу поиска с предпочтением, показанную на  рис. 12.3, к какой-нибудь задаче, мы должны добавить к нашей программе отношения, отражающие специфику этой конкретной задачи. Эти отношения определяют саму задачу ('правила игры'), а также вносят в алгоритм эвристическую информацию о методе ее решения. Эвристическая информация задается в форме эвристической функции.

/*  Процедуры, отражающие специфику головоломки

'игра в восемь'.

Текущая ситуация представлена списком положений фишек;

первый элемент списка соответствует пустой клетке.

Пример:

3

2

1

  1   2   3

  8        4

  7   6   5

    1   2   3

        Эта позиция представляется так:

[2/2, 1/3, 2/3, 3/3, 3/2, 3/1, 2/1, 1/1, 1/2]

'Пусто' можно перемещать в любую соседнюю клетку,

т.е. 'Пусто' меняется местами со своим соседом.