Поиск кратчайшего пути в графе (Prolog)

      Комментарии к записи Поиск кратчайшего пути в графе (Prolog) отключены

В этой теме 3 ответа, 2 участника, последнее обновление  Васильев Владимир Сергеевич 1 год, 5 мес. назад.

  • Автор
    Сообщения
  • #2380

    questioner
    Участник

    Необходимо написать программу на языке Prolog, выполняющую поиск кратчайшего пути в невзвешенном (все дуги имеют одинаковую длину) графе. Насколько я понимаю, надо использовать поиск в ширину, я вроде бы понимаю алгоритм и реализацию, описанную в вашей статье, но у меня есть другой код, который надо прокомментировать:

    path(Finish, [[Finish | PathPart] | _], [Finish | PathPart]).
    path(Finish, [[X | PathPart] | ProcList], Path):-
      findall(Y, step(X, PathPart, Y), AdjNodes),
      append(ProcList, AdjNodes, NewProcList), !,
      path(Finish, NewProcList, Path).  
      
    step(X,T,[Y,X|T]):-
      edge(X,Y),
      not(member(Y,T)).
     
    path(Start, Finish):-
      path(Finish, [[Start]], RPath),
      reverse(RPath,Path), write(Path).

    Помогите в нем разобраться.

  • #2381

    Функция step принимает исходную вершину и список посещенных вершин. Выбирает дугу, ведущую из текущей вершины в узел, который не был ранее посещен (для проверки используется встроенная функция member). Если такая дуга найдена — ее начальный и конечный узел добавляется в список посещенных вершин, результат возвращается в третьем аргументе. Функция является недетерменированной, т.е. ей можно перебрать все варианты дуг из стартовой вершины.

    Правило path\4 возвращает перевернутый путь (тут путь – последовательность вершин, а не дуг). Правило формирует двухуровневый список путей из начальной вершины в каждый посещенный узел. Правило выбирает смежные вершины, подобно тому, как это выполнялось в правиле add_adj. Из первого пути списка выделяется первый элемент (Х) и остаток пути (PathPart), которые передаются правилу step\3. За счет использования предикатов findall и step формируется список необработанных вершин, смежных со стартовой. Этот список присоединяется к очереди еще не обработанных вершин (ProcList) и передается в path\4.
    Процесс повторяется пока первого списка-пути не совпадет с конечной вершиной (в этом случае правило вернет перевернутый путь) или не кончится список путей (при этом правило завершится неудачей).

    В связи с тем, что вершины добавляются в начало списка, представляющего собой искомый кратчайший путь, он окажется перевернутым. Функция path/2 выполняет вызов path/4, инициализируя список посещенных вершин стартовой и переворачивает результирующий путь.

    Важно также то, что функция path\4 является недетерменированной (изменить это можно добавив оператор отсечения в обработку случая, когда путь найден), за счет этого можно найти кратчайшие пути во все остальные вершины.

    Вложения:
    • #2383

      questioner
      Участник

      Все приведенные реализации написаны на SWI Prolog, помогите переписать любую из них на Visual Prolog 5.2?

      • #2384

        В Visual Prolog первым делом надо описать типы данных, т.к. он является языком с явной типизацией:

        domains
          node_d = string
          edge_d = edge(node_d, node_d)
          way_d = edge_d*
          ways_d = way_d*

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

        Затем нужно описать прототипы используемых функций в секции predicates. В решении применяются стандартные функции member и append для поиска дуги в пути и соединения списков путей:

        nondeterm member(edge_d, way_d)
        append(ways_d, ways_d, ways_d)

        Граф должен задаваться дугами (edge_p), при этом сама по себе дуга является ориентированной, если требуется определить неориентированный граф — можно применить вспомогательную функцию (way_d_exist), выполняющую проверку наличия прямой или обратной дуги:

        nondeterm edge_p(edge_d)
        nondeterm way_d_exist(edge_d)

        Функция step формирует новый участок пути добавляя дугу к существующему пути:
        nondeterm step(node_d, way_d, way_d)

        Функция path принимает начальную вершину и список начальных путей, возвращает найденный путь, функция bfs_start запускает функцию path инициализируя аргументы:

        path(node_d, ways_d, way_d)
        bfs_start(node_d, node_d, way_d)

        В разделе clauses необходимо разместить реализацию функций и задать граф. Граф представляется в виде набора дуг:

        edge_p(edge("a", "b")).
        edge_p(edge("b", "c")).
        edge_p(edge("c", "d")).
        edge_p(edge("a", "e")).
        edge_p(edge("e", "d")).

        Функция way_d_exist принимает дугу и выполняет ее поиск. Если дуга не найдена — ищет дугу, направленную в обратную сторону:

        way_d_exist(edge(From, To)):-
          edge_p(edge(From, To)); edge_p(edge(To, From)).

        Функция step может как непосредственно обращаться к дугам (если граф надо рассматривать как ориентированный), так и к функции way_d_exist:

        step(From, PrevSteps, [edge(From, To)|PrevSteps]):-
          	way_d_exist(edge(From, To)),
          	not(member(edge(From, To), PrevSteps)).

        Функция path работает аналогично реализации на SWI Prolog и также возвращает перевернутый путь, но собирает не вершины, а дуги, поэтому для ее запуска требуется собрать все дуги, выходящие из стартовой вершины. Такая работа выполняется функцией bfs_start:

        path(Finish, [[edge(From, Finish) | PathPart] | _], [edge(From, Finish) | PathPart]):-!.
        path(Finish, [HeadPath | ProcList], Path):-
        	HeadPath = [edge(_From, To) | _PathPart],
          	findall(NewHeadPath, step(To, HeadPath, NewHeadPath), NewHeadPaths),
          	append(ProcList, NewHeadPaths, NewProcList), !,
          	path(Finish, NewProcList, Path).  
         
        bfs_start(Start, Finish, ResultPath):-
        	findall(Path, step(Start, [], Path), InitPaths),
            	path(Finish, InitPaths, ResultPath).

Для ответа в этой теме необходимо авторизоваться.