Prolog

Не разрешается вести поиск на глубине большей, чем МаксГлуб. Программная реализация этого ограничения сводится к уменьшению на единицу величины предела глубины при каждом рекурсивном обращений к вглубину2 и к проверке, что этот предел не стал отрицательным. В результате получаем программу, показанную на рис. 11.8.

Упражнения

11. 1.    Напишите процедуру поиска в глубину (с обнаружением циклов)

        вглубину1( ПутьКандидат, Решение)

отыскивающую решающий путь Решение как продолжение пути ПутьКандидат. Оба пути представляйте списками вершин, расположенных в обратном порядке так, что целевая вершина окажется в голове списка Решение.

Посмотреть ответ

11. 2.    Напишите процедуру поиска в глубину, сочетающую в себе обнаружение циклов с ограничением глубины, используя рис. 11.7 и 11.8.

11. 3.    Проведите эксперимент по применению программы поиска в глубину к задаче планирования в 'мире кубиков' (рис. 11.1).

11. 4.    Напишите процедуру

        отобр( Ситуация)

для отображения состояния задачи 'перестановки кубиков'. Пусть Ситуация - это список столбиков, а столбик, в свою очередь, - список кубиков. Цель

        отобр( [ [a], [e, d], [с, b] ] )

должна отпечатать соответствующую ситуацию, например так:

                е         с

      a        d         b

      ================

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

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

11. 3.    Поиск в ширину

В противоположность поиску в глубину стратегия поиска в ширину предусматривает переход в первую очередь к вершинам, ближайший к стартовой вершине. В результате процесс поиска имеет тенденцию развиваться более в ширину, чем в глубину, что иллюстрирует рис. 11.9.

Поиск в ширину программируется не так легко, как поиск в глубину. Причина состоят в том, что

Рис. 11. 9. Простое пространство состояний:  а  - стартовая вершина,

f  и  j  - целевые вершины. Применение стратегии поиска в ширину

дает следующий порядок прохода по вершинам: а, b, c, d, e, f. Более

короткое решение [a, c, f] найдено раньше, чем более длинное

[а, b, e, j]

нам приходится сохранять все множество альтернативных вершин-кандидатов, а не только одну вершину, как при поиске в глубину. Более того, если мы желаем получить при помощи процесса поиска решающий путь, то одного множества вершин недостаточно. Поэтому мы будем хранить не множество вершин-кандидатов, а множество путей-кандидатов. Таким образом, цель

        вширину( Пути, Решения)

истинна только тогда, когда существует путь из множества кандидатов Пути, который может быть продолжен вплоть до целевой вершины. Этот продолженный путь и есть Решение.

11. 3. 1.