Реализации поиска в ширину



Рисунок 11. 10.  Реализации поиска в ширину.

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

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

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

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

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

В случае примера Рисунок 11.9 этот процесс будет развиваться следующим образом:

line();

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

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

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


                bagof( [B1, В | Путь ],
                            ( после( В, В1),
                               not принадлежит( В1, [В | Путь]) ),
                            Нов ),
                конк( Нов, ZZ, Z),  !,
                вширь( Пути-ZZ, Решение);
                Пути \== Z,
            % Множество кандидатов не пусто
                вширь( Пути-Z, Решение).

line();



Содержание раздела