Упражнения

11. 5.    Перепишите программу поиска в ширину Рисунок 11.10, используя разностное представление для списка путей-кандидатов и покажите, что в результате получится программа, приведенная на Рисунок 11.11. Зачем в программу Рисунок 11.11 включена цель
        Пути \== Z
Проверьте, что случится при поиске в пространстве состояний Рисунок 11.9, если эту цель опустить. Различие в выполнении программы, возникнет только при попытке найти новые решения в ситуации, когда не осталось больше ни одного решения.
11. 6.    Как программы настоящего раздела можно использовать для поиска, начинающегося от стартового множества вершин, вместо одной стартовой вершины?
Посмотреть ответ
11. 7.    Как программы этой главы можно использовать для поиска в обратном направлении, т.е. от целевой вершины к стартовой вершине (или к одной из стартовых вершин, если их несколько). Указание: переопределите отношение после. В каких ситуациях обратный поиск будет иметь преимущества перед прямым поиском?
11. 8.    Иногда выгодно сделать поиск двунаправленным, т. е. продвигаться одновременно с двух сторон от стартовой и целевой вершин. Поиск заканчивается, когда оба пути "встречаются". Определите пространство поиска (отношение после) и целевое отношение для заданного графа таким образом, чтобы наши процедуры поиска в действительности выполняли двунаправленный поиск.
11. 9.    Проведите эксперименты с различными методами поиска применительно к задаче планирования в "мире кубиков".