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

Графы в программе можно задавать различными способами, например — матрицами/списками смежности/инцидентности. При этом в программе объект графа часто хранится в виде массива (одномерного или двумерного). В языке Prolog для этого можно использовать списки или встроенную базу данных. Если граф будет часто меняться — то вариант с базой данных скорее всего будет более эффективным.

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

Задавать граф одними дугами нельзя, т.к. при таком способе мы не сможем описать изолированные вершины (вершина s в приведенном графе).

Также, вместо информацию о дугах можно хранить прямо внутри описания вершины:

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

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

Алгоритм поиска в глубину подробно описан в статье «Графы — Поиск в ширину и глубину«. На языке Prolog его можно записать так:

Реализацию функции member можно взять там.

Первые 2 строки обрабатывают ситуацию когда в графе есть дуга непосредственно из вершины From в вершину To . Если такой дуги нет — выполняется остальная часть программы: четвертая строка — выбирает дугу, начинающуюся в вершине From ; в пятой строке проверяется что вершина X , являющаяся вторым концом дуги еще не была посещена; наконец, в шестой строке запускается рекурсивный поиск пути из вершины X . В случае если пути между заданными вершинами нет — правило завершается неудачей.

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

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

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

Алгоритм поиска в ширину тоже подробно описан в статье «Графы — Поиск в ширину и глубину«. Код в этом разделе приведен для SWI Prolog, однако в конце статьи есть ссылка на реализацию поиска в ширину на других диалектах пролога.

Разберем этот алгоритм на примере решения следующей задачи:

минимального расстояния (количества остановок).
минимального числа пересадок;

В обоих случаях надо найти кратчайший путь, отличаются лишь критерии «минимальности».

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

Пример задания маршрутов:

Соответствующая этой схеме иллюстрация:

Реализация поиска кратчайшего по количеству остановок пути

Нам потребуется вспомогательная функция, выполняющая поиск подсписка. Эту операцию можно выполнить с помощью функции divide_list.

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

Функция принимает 2 аргумента, каждый из которых представлен кортежем из трех элементов, задающих станцию (тип транспорта, номер, название станции).

В строке 2 эта функция выбирает маршрут (организуется перебор всех возможных маршрутов). В строках 7-10 выполняется поиск в списке станций подсписка из двух элементов. Дело в том, что если текущая станция StA , то следующая (на которую я могу попасть) – StB может находится в списке станций маршрута:

Непосредственно следом за StA – тогда ищем подсписок [StA, StB] ;
Перед StA (граф неориентированный, если я могу попасть из A в B – то и из B в A тоже могу) – ищем подсписок [StB, StA] .

Можем запустить эту функцию чтобы получить список станций, на которые можно попасть за одну остановку от текущей:

В данном случае вывод такой – из станции st1 я могу попасть на автобусе с номером 1 на станцию st2 , на трамвае с номером 3 – на станцию st5 и так далее.

В ходе поиска пути мы будем перебирать вершины, при этом осуществлять переход из X в Y , а дальше – искать путь уже из Y . При этом нам нужно помещать уже посещенные вершины – иначе программа будет вечно переходить из пункта A в пункт B и из B в A (назад).

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

Если мы уже были на станции «Воробьевы горы» — то зачем нам на нее возвращаться (не важно на каком трансорте)? При этом функция move вернет станцию с указанием типа транспорта, нам надо разобраться эту структуру (выбрать из нее имя станции – вторая строка кода) и проверить ее отсутствие в списке Used (строка 3).

Функция member является стандартной и выполнят поиск элемента в списке, оператор \+ выполняет отрицание (т.е. третья строка сработает когда элемента нет в списке).

Теперь, когда написаны все вспомогательные функции, можно перейти к непосредственной реализации поиска кратчайшего пути (поиску в ширину).

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

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

Для генерации дополненных путей (старый путь + одна из вершин для перехода) написана такая функция:

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

Теперь поиск кратчайшего пути можно записать так:

Тут первое правило (строки 1-3) срабатывает если крайняя вершина первого пути совпадает с искомой). В строке 4 из списка путей выбирается первый ( HeadPath ). В строке 5 из этого пути выбирается крайняя (последняя посещенная) вершина – HeadStation . В строке 6 с помощью стандартного предиката findall все вершины, в которые можно перейти из HeadStation помещаются в список AllNextStations . В строке 7 с помощью findall и описанного выше правила path_with_station формируется новый набор путей из HeadPath и AllNextStations – к существующему пути прибавляется по очереди каждая станция из AllNextStations . В строке 8 с помощью стандартной функции append в конец списка путей добавляются новые. В строке 9 – новые вершины ( AllNextStations ) добавляются в список Used . В строке 10 запускается рекурсивных поиск (выбирается следующий путь из списка).

Чтобы использовать эту функцию надо передать ей в качестве списка путей список, единственным элементом которого является список из первой станции, например: bfs([[(bus, 1, st1)]], st5, [], Path).

При этом будет получен список Path , задающий список станций кратчайшего пути. Этот список будет перевернут, так как функция bfs последнюю вершину пути помещает в начало списка пути. Напишем вспомогательную функцию, с более удобным набором параметров, которая формирует данные для bfs и переворачивает (с помощью стандартной функции reverse) найденный путь.

На рисунке приведены результаты работы функции:

Исходный код целиком:

Поиск пути с минимальным числом пересадок

Чтобы найти путь, содержащий минимальное число пересадок можно изменить функцию move – путь она возвращает не только следующую станцию, а любую станцию на текущем маршруте:

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

📎📎📎📎📎📎📎📎📎📎