Поиск кратчайшего пути на графе¶
В этом примере мы воспользуемся функциями библиотеки Graphs.jl чтобы создать граф и найти на нем кратчайший маршрут между двумя точками.
Работа с графами¶
Графы часто используются как элемент моделей в задачах логистики, транспортных, информационных или социальных сетей и других связанных систем. Они являются абстрактными математическими объектами, состоящими из вершин (vertex, vertices) и рёбер (edges). Обычно каждая вершина имеет свой уникальный номер, а ребра обозначаются двумя числами – номерами вершин, которые они соединяют.
К узлам и ребрам может быть привязана какая-то информация (например, координаты или пропускная способность). В библиотеке Graphs.jl предполагается, что дополнительная информация хранится во внешней таблице или словаре (Dict). Записи могут быть привязаны к вершинам (через их номера) или ребрам (через кортеж из чисел, идентифицирующих ребро). Для экономии можно использовать разреженные матрицы (SparseArrays.jl).
# Если библиотека у вас установлена, закомментируйте следующую строчку:
import Pkg; Pkg.add( ["Graphs", "GraphRecipes"] )
using Graphs, GraphRecipes
Пакет GraphsRecipes.jl отвечает за отрисовку графов.
Создадим простой направленный граф, содержащий три узла и несколько ребер.
g = DiGraph()
add_vertices!( g, 3 );
Сейчас в нашем графе три вершины, соединим их ребрами.
add_edge!( g, 1, 2 );
add_edge!( g, 1, 3 );
add_edge!( g, 2, 3 );
И выведем этот граф:
gr() # Упрощенная отрисовка
graphplot( g, names=1:nv(g) )
Обратите внимание, что имена узлов names взяты из "внешнего" массива 1:nv(g), где хранятся номера узлов от 1 до nv (number of vertices, количество вершин).
Создадим карту, на которой будем искать путь¶
В качестве поля для поиска кратчайшего пути мы возьмём случайную матрицу и зададимся целью пройти по ней вдоль главной диагонали. Связанность этой "карты" и возможность достичь точки Б из точки А, увы, не обеспечена ничем, кроме выбора "правильного" стартового значения генератора псевдослучайных чисел Random.seed!().
using Random;
Random.seed!( 4 )
карта = rand( 30, 30 ) .> 0.3;
heatmap( карта )
# Точка старта и финиша
точка_А = CartesianIndex(1,1)
точка_Б = CartesianIndex(30,30)
# Добавим на график токи старта и финиша
scatter!( [точка_А[1]], [точка_А[2]], c=:red )
scatter!( [точка_Б[1]], [точка_Б[2]], c=:green, leg=false )
Наш граф будет ненаправленным, то есть вдоль каждого ребра можно будет пройти как туда, так и обратно.
g = Graph();
индексы_доступных_точек = LinearIndices( карта )[ карта .== 1 ]
println( "Количество площадок, куда можно наступать: ", count(индексы_доступных_точек .> 0 ))
Вспомогательные объекты (перевод координат)¶
Сохраним матрицу, где будут храниться 2D координаты всех точек карты.
координаты_всех_точек = CartesianIndices( size(карта) );
Создадим граф, который переводит номер вершины графа в координату:
координаты_точек_графа = Dict(zip( 1:length(индексы_доступных_точек), координаты_всех_точек[индексы_доступных_точек] ))
first( sort(collect(координаты_точек_графа)), 5 )
Теперь – инвертируем этот словарь и получим возможность переводить координату в номер точки на графе.
индексы_точек_по_координатам = Dict(value => key for (key, value) in координаты_точек_графа)
first( sort(collect(индексы_точек_по_координатам)), 5 )
Сложим координаты точек в массивы xx и yy – их мы будем передавать в процедуру отрисовки графа.
xy = Tuple.(first.(sort(collect(индексы_точек_по_координатам))));
xx = first.(xy);
yy = last.(xy);
Наполнение графа¶
Поскольку мы будем пользоваться стандартной функцией для поиска кратчайшего пути, а не будем создавать ее сами с нуля, нам нужно создать граф, на котором этот поиск будет происходить.
g = Graph()
add_vertices!( g, length(координаты_всех_точек[ индексы_доступных_точек ][:]) )
Пройдемся по всем точкам и соединим их с соседними точками, если между ними есть проход.
MAX_X,MAX_Y = size( карта )
for вершина in 1:nv(g)
x,y = Tuple(координаты_точек_графа[вершина])
точка_справа = CartesianIndex( x + 1, y )
точка_снизу = CartesianIndex( x, y + 1 )
# Соединим текущую точку с точкой справа, если есть связанность согласно карте пройденных точек
if x < MAX_X && карта[точка_справа] == 1 add_edge!(g, вершина, индексы_точек_по_координатам[точка_справа]); end;
# То же самое для точки снизу
if y < MAX_Y && карта[точка_снизу] == 1 add_edge!(g, вершина, индексы_точек_по_координатам[точка_снизу]); end;
end
Посмотрим, добавились ли в наш граф ребра, и сколько их:
g
Судя по выводу, к 634 точкам добавилось 840 ребер. Выведем график:
heatmap( карта', title="Карта", titlefont=font(9), leg=:false )
graphplot!( g, x = xx, y = yy, nodeshape=:circle, nodecolor=:red, nodestrokecolor=:red, nodesize=1.5, edgecolor=:red, curves=true, size=(500,500) )
Нам не пришлось "раскладывать" граф, поскольку мы уже знаем координаты каждого узла. Остальные параметры отрисовки можно изучить здесь.
Поиск кратчайшего пути¶
Мы используем алгоритм A-star, осуществляющий поиск кратчайшего пути с использованием эвристик. На выходе мы получим набор ребер.
# Нахождение кратчайшего пути
path = a_star( g, индексы_точек_по_координатам[точка_А], индексы_точек_по_координатам[точка_Б] );
first( path, 5 )
Составим массив из точек графа, которые нужно посетить, чтобы пройти от точки А к точке Б.
points = Tuple.( vcat([точка_А], [ координаты_точек_графа[dst(v)] for v in path ]) );
first( points, 5 )
# Вывод карты (со смещенными значениями для нужной яркости графика)
heatmap( карта' .* 0.3 .+ 0.7, title="Кратчайший путь", leg=false, c=:grays, aspect_ratio=:equal )
# Вывод графа допустимых перемещений по карте
#graphplot!( g, x = xx, y = yy, curves=true, nodeshape=:circle, size=(400,400) )
# Вывод кратчайшего пути
plot!( first.(points), last.(points), lw=3, linez=range(0,1,length(points)), c=:viridis, yflip=true )
Заключение¶
Графы – очень мощные математические объекты, которые позволяют находить структуру в разрозненных данных – циклы, деревья, кратчайшие или наиболее длинные пути и связанные области. Возможность работать с ними из среды моделирования динамических систем дает инженерам очень интересные возможности.