Графы. Поиск в ширину и глубину на Prolog

Заказать решение задачи на Prolog или попросить помощь

В статье описываются:

  • алгоритмы обхода графа в глубину и в ширину;
  • представление графов на языке Prolog;
  • реализация алгоритмов обхода графа на языке Prolog.

1 Графы. Обходы графа

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

Кроме того, нередко встает задача поиска кратчайших путей. Во взвешенном графе (ребра графа имеют определенный вес) кратчайший путь имеет наименьшую сумму весов входящих в него ребер. Для поиска такого пути есть специальные алгоритмы (такие как Беллмана-Форда), но они не рассматриваются в этой статье [3, 4].

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

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

рис. 1 пример графа

рис. 1 пример графа

1.1 Обход графа в глубину

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

1. начало; функция breadth(G, Start, Finish)
         ; обход графа в ширину
         ; G - граф,
         ; Finish - начальная вершина,
         ; Start - конечная вершина
2. пометить вершину Start как обработанную;
3. выбрать дугу (Start, X), такую, что вершина X не обработана, если дуги нет - переход на п.4;
3.1. если в G есть дуга (Start, Finish) - вернуть (true, (Start, Finish));
3.2. (Res, Path) := breadth(G, X, Finish);
3.3. если Res = true - вернуть (true, (Start, X) + Path);
3.4. вернуть breadth(G, Start, Finish);
4. конец - вернуть (false, ()).

В результате рекурсивного вызова (п. 3.2) может быть найден путь, проходящий через одну из смежных со Start дуг. Если путь найден – то его необходимо дополнить соответствующей дугой (п.3.3), в противном случае – перейти к поиску пути, проходящему через другую дугу (п. 3.4).

Стоит отметить, что на шаге 3 алгоритма листинг 1 выбирается произвольная дуга, однако, выбор дуга влияет на результат, т.к. алгоритм не гарантирует что найденный путь будет кратчайшим. Например, если при поиске пути из вершины P а вершину F, первой будет выбрана дуга (P, D), то будет найден путь (P, D, F), однако, если первой будет взята дуга (P, B), то может быть найден путь (P, B, C, D, F).

1.2 Обход графа в ширину

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

На рис. 2 цветом показан порядок обработки вершин при поиске пути из узла B. Черным цветом выделены вершины, не достижимые из стартовой. Пунктирная линия изображает возможную альтернативу (вершина F может быть добавлена с использованием дуги (D, F) или дуги (E, F)).

рис. 2 обход графа в ширину

рис. 2 обход графа в ширину

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

1. начало; функция breadth(G, Queue_add, Queue_proc, Finish, Res)
         ; обход графа в ширину
         ; G - граф,
         ; Queue_add - очередь добавленных вершин (не обработанных)
         ; Queue_proc - очередь обработанных вершин
         ; Finish - конечная вершина
         ; Res - список использованных дуг
2. если Queue пуст - вернуть (false, Res);
3. получить H узел из начала Queue_add;
4. если H = Finish - вернуть (true, Res);
5. adj_nodes := список вершин, смежных с H;
6. удалить из adj_nodes вершины, присутствующие в Queue_add или Queue_proc;
7. удалить H из Queue_add, добавить H в Queue_proc;
8. добавить в конец Queue_add вершины из adj_nodes;
9. добавить в Res дуги между узлом H и вершинами из adj_nodes;
10. вернуть breadth(G, Queue_add, Queue_proc, Finish, Res);
11. конец.

По алгоритму листинг 2, поиск продолжается пока не будут обработаны все доступные вершины (п. 2), либо не будет найдена нужная вершина (п.4). Функция breadth выбирает вершину из начала очереди обработки (п.3), и добавляет новые в конец (п.8) – за счет этого обеспечивается требуемый порядок обхода – чем более узел удален от стартовой вершины – тем позже он будет обработан. Для устранения зацикливания алгоритма, в очередь добавляются только вершины, которые не были обработаны или добавлены в очередь обработки на предыдущих шагах (п.6).

Приведенный алгоритм возвращает не путь, а список дуг, по которому можно восстановить кратчайшие пути между стартовой и всеми обработанными вершинами (листинг 3).

1. начало; функция path(Start, Finish, Edges)
         ; восстановление пути между двумя вершинами по дугам
         ; Start - начало пути
         ; Finish - конец пути
         ; Edges - дуги, полученные поиском в ширину
2. если в Edges нет дуги (Start, Finish) - переход к п.3;
2.1. вернуть список из одной дуги (Start, Finish);
3. получить дугу (X, Finish) из Edges;
4. PartPath := path(Start, X, Edges)
5. PartPath := (X, Finish) + PartPath;
6. конец (вернуть PartPath).

Если алгоритм поиска в ширину (функция breadth) вернул true – то соответствующий набор дуг гарантированно содержит искомый путь и функция path в п.3 найдет дугу, принадлежащую этому пути.

2 Обход графа в ширину и глубину на языке Prolog

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

В базе удобно хранить информацию об узлах (node) и дугах (edge). Граф рис. 1 мог бы быть описан следующими фактами:

/*
 nodes
*/
node(a).
node(b).
node(c).
node(d).
node(e).
node(f).
node(g).
node(h).
node(k).
node(m).
node(p).
node(s).

/*
 edges
*/

edge(a, b).
edge(a, c).
edge(a, g).

edge(b, a).
edge(b, c).

edge(c, e).
edge(c, d).

edge(d, f).

edge(e, g).
edge(e, f).
edge(e, h).

edge(f, k).

edge(g, c).
edge(g, e).

edge(m, d).

edge(p, b).
edge(p, d).

2.1 Реализация алгоритма поиска в глубину на Prolog

dfs(From, To, _, [edge(From, To)]):-
  edge(From, To).
dfs(From, To, VisitedNodes, [(From, X)|TailPath]):-
  edge(From, X), 
  not(member(X, VisitedNodes)),
  dfs(X, To, [From|VisitedNodes], TailPath).

Первые 2 строки соответствуют пункту 3.1 алгоритма листинг 1, четвертая строкапункту 3.2, третья и пятая – 3.3. В случае если пути между заданными вершинами нет – правило завершается неудачей (вместо флага результата).

рис. 3 пример поиска в глубину на Prolog

рис. 3 пример поиска в глубину на Prolog

Вызовы правила dfs на рис.3 проводились для графа рис. 1. Как видно, описанный предикат позволяет найти все пути из начальной вершины в конечную. В связи с этим, если нужен кратчайший путь и не важна оптимальность работы алгоритма – можно найти все пути и выбрать кратчайший.

2.2 Реализация алгоритма поиска в ширину на Prolog

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

/*
 path\3 возвращает путь @3 из вершины @1 в вершину @2
*/
path(A, B, Path):-
  breadth([A], [], [], B, UE),
  path(A, B, UE, Path).

Правило восстановления пути (path\4) соответствует алгоритму листинг 3.

/*
 path\4 восстанавливает путь @4 из вершины @1 в вершину @2 по дугам @3
*/
path(A, B, UE, [(A, B)]):-
  member((A, B), UE), !.
path(A, B, UE, Path):-
  member((X, B), UE), !,
  path(A, X, UE, TPath),
  append(TPath, [(X, B)], Path).

Обход графа в ширину реализуется правилом breadth\5 в соответствии с листинг 2, при этом, реализация пунктов 5 и 6 (добавления и фильтрация смежных вершин выполняется правилом add_adj\6.

/*
 breadth обход графа в ширину
  @1 список добавленных вершин
  @2 исходный список использованных дуг
  @3 список пройденных вершин
  @4 конечная вершина
  @5 результат - список использованных дуг
*/
breadth([], _, _, _, _):-!, fail.
breadth([H|_], UE, _, H, UE):-!.
breadth(V, UE, UV, FV, RUE):-
  add_adj(V, UE, UV, TV, TUE, TUV),
  breadth(TV, TUE, TUV, FV, RUE).

Правило add_adj\6 использует adj_filter\4 для реализации п.6 алгоритма, и add_adj_edges\4 – для реализации п.7.

/*
 adj_filter\4
  удаляет из списка вершин @1, вершины, входящие в @2 или @3. Результат в @4
*/
adj_filter([], _, _, []):-!.
adj_filter([H|T], L1, L2, [H|TR]):-
  not(member(H, L1)), not(member(H, L2)), !,
  adj_filter(T, L1, L2, TR).
adj_filter([_|T], L1, L2, TR):-
  adj_filter(T, L1, L2, TR).

/*
 add_adj_edges
  добавляет дуги из вершины @1 до вершин списка @2 в список @3. Результат в @4
*/
add_adj_edges(_, [], R, R):-!.
add_adj_edges(SV, [H|T], IL, [(SV,H)|TR]):-
  add_adj_edges(SV, T, IL, TR).

/*
 add_adj/6
  @1 исходный список добавленных вершин
  @2 исходный список дуг
  @3 исходный список пройденных вершин
  @4 результат - список добавленных вершин
  @5 результат - список дуг
  @6 результат - список пройденных вершин
*/

add_adj([], _, _, _, _, _):-!, fail.
add_adj([H|T], UE, UV, RV, RUE, RUV):-
  findall(X, edge(H, X), AVHL), % получили список смежных вершин
  adj_filter(AVHL, UE, UV, FAVHL), % убрали из него лишние вершины

  append(T, FAVHL, RV), % изменив порядок соединения списков,
                        % можно получить обход в глубину
  add_adj_edges(H, FAVHL, UE, RUE),
  RUV = [H|UV], !.

рис. 4 пример поиска в ширину

рис. 4 пример поиска в ширину

Исходный код алгоритма поиска в ширину можно скачать. При реализации использовался SWI Prolog, однако, код писался так, чтобы его без особых усилий можно было запустить Visual Prolog 5.2.

Список использованных источников

  1. Валетов В.А., Орлова А.А., Третьяков С.Д. Интеллектуальные технологии производства приборов и систем. Учебное пособие, – СПб: СПб ГУИТМО, 2008. – 134 с.
  2. Афонин В.Л., Макушкин В.А. Интеллектуальные робототехнические системы, Интернет-университет информационных технологий, 2005
  3. Макоха А.Н., Сахнюк П.А., Червяков Н.И. – Дискретная математика. Учеб. пособие (ФМЛ, 2005)
  4. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. Учебник. М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002
  5. Книги раздела “Алгоритмы”
  6. Вариант реализации поиска в ширину на невзвешенном графе.

9 thoughts on “Графы. Поиск в ширину и глубину на Prolog

  1. Jack

    Уважаемый Admin!
    Хотел изучить и разобраться основательнее – скачал пособие (Валетова, Орловой, Третьякова).
    Возможно, я плохо читал, но в пособии ничего не увидел из того,
    что приводится в этой статье. Посоветуйте учебники по Prolog.

    Reply
    1. admin Post author

      Пособие Валетова посвящено искусственному интеллекту, скорее всего там есть что-то про поиск в глубину и ширину (поэтому я его упомянул).

      Интересная книга по прологу у Сергиевского (описан SWI Prolog).

      Если не секрет, какой именно пролог Вы хотите изучать и с какой целью?

      Reply
  2. Алексадр

    Здравствуйте. Перепроверьте, пожалуйста, алгоритм поиска в глубину. Он должен выдавать все возможные варианты. Также, как у Вас написано, он должен работать и с SWI, и с визуальным прологом. На SWI код для поиска в ширину работает прекрасно, а вот код поиска в глубину выдает всегда по 1 результату (вместо всех возможных).

    Reply
    1. admin Post author

      Чтобы получить все результаты нужно убрать отсечение в первом правиле поиск в глубину:
      [plain collapse=”false”]dfs(A, B, _, [(A, B)]):-
      edge(A, B).[/plain]

      Reply
  3. Александр

    Убрал отсечение, как вы написали. Оставил только:

    dfs(A, B, _, [(A, B)]):-
    edge(A, B).

    Теперь вообще ничего не ищет и выдает одни false.
    Поиск в глубину дает false

    Кстати говоря, поиск в глубину у Вас используется в эвристическом поиске для решения задачи лабиринта (оттуда ссылку на этот поиск). Ну и соответственно, эвристический тоже не работает. Потому в нем я решил применить вместо поиска в глубину, поиск в ширину. Кстати говоря…не знаю, как вы собирались решить задачу лабиринта поиском в глубину. Оптимальный путь ищется поиском в ширину.

    В качестве базы фактов использую вашу базу для поиска в глубину. Так, почему код не работает? что бы вы посоветовали?

    Reply
    1. admin Post author
      1. вы убрали отсечение только из первого правила? – у меня все работает, проверил еще раз поиск в ширину и поиск пути в лабиринте;
      2. нет разницы какой поиск использовать – и поиск в ширину, и поиск в глубину возвращают путь из начальный вершины в конечную;
      3. в логической задаче про лабиринт не требуется искать кратчайший путь, если вы внимательно посмотрите скриншоты к решению – то увидите, что на экран выводятся все возможные пути, а не только кратчайший.
      Reply
  4. Александр

    1) в поиске в глубину там всего одно правило.
    2) Вообще..по теории поиск в глубину должен методом проб и ошибок перебирать все пути и выдавать все возможные пути списком. А поиск в ширину ищет и выдает оптимальный путь из точки A в точку B. И это, кстати говоря..отражено на ваших скриншотах. Там в соответствии с теорией выдает правильные результаты: поиск в глубину – различные варианты, поиск в ширину – оптимальный вариант. Но код, если посмотреть, делает не то, что представлено на скриншотах.
    Я ваши методы подправил. Теперь код работает как надо. Поиск в глубину ищет все, поиск в ширину – оптимальный. читайте теорию. А то потом народ будет использовать ваши коды и буду ломать голову, что не так.
    3) на счет лабиринта..я и не говорил, что нужно искать оптимальный путь для решения данной задачи.

    Получается, что вы забили базу фактов и в программе сделали запрос к функции dfs – а это функция из поиска в глубину на вашем сайте.
    Я проверил в начале эвристический ваш – он не работал. Потом догадался проверить поиск в глубину – он тоже не работает.

    Поиск в глубину доработал – он стал выводить все маршруты. Но это я доработал вывод на печать. А для внешнего использования, скажем…тем же эвристическим поиском, он не пригоден. Пришлось применять в ширину для этого.

    И ещё: если вы выкладываете решение для задачи, то не разбрасывайте эти кусочки решения по всему сайту и не связанно друг с другом. Помощь с прологом очень актуальна для студентов. Но если студент увидит эти непонятные куски, он будет долго тупить. Код есть код: выкладывать нужно в один листинг, чтобы потом не было критики, недовольств и вопросов. Это я быстро вник, т.к. уже по статусу положено. А делать надо сайт для людей, тогда будут люди довольными и больше посещаемость. Если так один, второй, третий, пятый, десятый…не разберутся с вашим сайтом, то и забьют на него сразу же.

    Reply
    1. admin Post author

      в поиске в глубину там всего одно правило.

      В реализации поиска в глубину из статьи, которую вы комментируете два правила. Отличия правила и предиката описаны в статье “введение в логическое программирование”, которая есть на блоге.

      Но код, если посмотреть, делает не то, что представлено на скриншотах.

      Как я получил скриншоты? – я взял код (который приведен на сайте, запустил его и нажал print screen). Это значит, кто скриншоты соответствуют коду. В прошлом сообщении я уже писал вам, что взял и запустил код еще раз – в результате получил те же самые результаты. Я уже перепроверил все.

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

      Вы говорили следующее:

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

      из этого можно сделать лишь один вывод.

      Reply
    2. admin Post author

      Поиск в глубину доработал – он стал выводить все маршруты. Но это я доработал вывод на печать. А для внешнего использования, скажем…тем же эвристическим поиском, он не пригоден. Пришлось применять в ширину для этого.

      Я же писал выше, что перепроверил – код работает. Это с одной стороны. С другой стороны, оба поиска (в ширину и в глубину) выдают путь. Если работает один – то работает и второй.

      И ещё: если вы выкладываете решение для задачи, то не разбрасывайте эти кусочки решения по всему сайту и не связанно друг с другом. … Код есть код: выкладывать нужно в один листинг.

      Поиск в ширину – это общий алгоритм, он почти никак не связан с поиском в лабиринте и конкретной задачей. Но конкретная задача связана с реализацией поиска в ширину ссылкой. Мало того, после вашего обращения я поправил поиск в ширину так, что теперь он выводит не один путь, а все (и опять же, я проверил, что это работает). Если бы я делал так, как вы советуете (запихивал каждый раз весь код в один листинг) – мне пришлось бы править все задачи, использующие dfs (а их на этом блоге не менее сотни).

      А делать надо сайт для людей, тогда будут люди довольными и больше посещаемость. Если так один, второй, третий, пятый, десятый…не разберутся с вашим сайтом, то и забьют на него сразу же.

      На сайте есть раздел “о блоге” – там написано для чего я создал сайт и зачем поддерживаю его в настоящее время. С другой стороны, посещаемость разделов сайта, связанных с прологом, за год выроста более чем в 10 раз. Из этого я делаю вывод, что с сайтом легко разобраться.

      Reply

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Вы не робот? *