Графы. Поиск в ширину и глубину на Prolog — Блог программиста

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

11.12.2013алгоритмы

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

  • алгоритмы обхода графа в глубину и в ширину;

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

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

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

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

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

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

Графы. Поиск в ширину и глубину на Prolog — Блог программиста
рис. 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)).

Графы. Поиск в ширину и глубину на Prolog — Блог программиста
рис. 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

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

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

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

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

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

  /*   path4 восстанавливает путь @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).  

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

  /*   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_adj6 использует adj_filter4 для реализации п.6 алгоритма, и add_adj_edges4 — для реализации п.7.

  /*   adj_filter4    удаляет из списка вершин @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 пример поиска в ширину

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

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

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

Метки:

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

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