Программирование на языке Пролог для искусственного интеллекта



           

Списковое представление множества кандидатов - часть 2


Поиск начинается с одноэлементного множества кандидатов

        [ [СтартВерш] ]

Общие принципы поиска в ширину таковы:

Для того, чтобы выполнить поиск в ширину при заданном множестве путей-кандидатов, нужно:

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

    line();

            решить( Старт, Решение) :-

                    вширь( [ [Старт] | Z ]-Z, Решение).

            вширь( [ [Верш | Путь] | _ ]-_, [Верш | Путь] ) :-

                    цель( Верш).

            вширь( [ [В | Путь] | Пути]-Z, Решение ) :-

                    bagof( [B1, В | Путь ],

                                ( после( В, В1),

                                   not принадлежит( В1, [В | Путь]) ),

                                Нов ),

                    конк( Нов, ZZ, Z),  !,

                    вширь( Пути-ZZ, Решение);



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