Алгоритм Прима — это жадный алгоритм поиска дерева с наименьшей стоимостью, включающего все узлы графа, также называемого минимальным прямым деревом. Существует множество постов в блогах и учебников по его реализации, но мне было трудно найти информацию о реализации на функциональных языках или в функциональном стиле с неизменяемыми структурами данных.
В приведенной ниже реализации узлы графа задаются в виде неупорядоченного списка. Мне показалось, что проще всего работать со списком как с кортежем, к которому можно обращаться по индексу. Коллекция узлов не будет изменяться (никаких добавлений или вставок), но к ней будут часто обращаться. Поскольку доступ к кортежу по индексу осуществляется довольно быстро, я посчитал, что это хороший подход. Тем не менее, это не обязательно и может сделать алгоритм менее «функциональным» по стилю.
В алгоритме Прима вам нужны два математических множества — множество всех посещенных узлов (т.е. узлов, включенных в минимальное охватывающее дерево) и множество всех узлов в графе. Вы выбираете произвольный узел для начала и перебираете непосещенные узлы, чтобы найти минимальное расстояние для соединения с MST. Алгоритм завершается, когда эти два набора эквивалентны. В приведенной ниже реализации я решил просто отслеживать набор непосещенных узлов, и алгоритм будет завершен, когда этот набор будет пуст. Это связано с тем, что в данном случае меня интересует только стоимость MST, а не сама MST. Если бы мне нужно было вернуть MST, я бы отслеживал посещенные узлы наряду с исходным набором узлов.
Вам также нужен способ узнать стоимость любого ребра в графе. В данном случае я предполагаю, что граф задан в виде серии пар координат {x, y}, а вес ребра определяется манхэттенским расстоянием между ними.
Для начала мы инстанцируем набор непосещенных узлов, текущую «стоимость» минимального охватывающего дерева и очередь приоритетов. В данном случае я использую общее сбалансированное дерево в качестве структуры очереди приоритетов. Я знаю, что они не совсем эквивалентны, но в Erlang есть встроенное GBT, и я не хотел реализовывать очередь приоритетов с нуля.
Ключи GBT — это расстояния, а значения GBT — это список узлов, которые соединяются хотя бы с одним ребром на данном ключевом расстоянии. Поскольку я использую GBT в качестве очереди, а ключи должны быть уникальными, если я не использую список в качестве значения каждого узла GBT, очередь будет отбрасывать узлы и в итоге окажется некорректной. Это единственная проблема, с которой я столкнулся при использовании GBT в качестве приоритетной очереди.
def min_cost_connect_points(points) do
vertices =
points
|> Enum.with_index()
|> Enum.map(fn {pt, i} -> {i, pt} end)
|> Enum.into(%{})
len = length(points)
candidates = MapSet.new(0..len - 1)
# This will be our set of unvisited nodes, well, indices
# of nodes.
queue = :gb_trees.enter(0, [0], :gb_trees.empty())
# We initiate the priority queue with an arbitrary node
# that has a minimum distance of zero. The node index is
# wrapped in a list and entered into the GBT with key 0.
cost = 0
do_prims(vertices, candidates, queue, cost)
end
defp do_prims(vertices, candidates, queue, cost) do
if MapSet.size(candidates) == 0 do
# When the set of unvisited nodes (`candidates`) is
# empty we're done.
cost
else
{min_dist, [next_vertex | rest], new_queue} =
:gb_trees.take_smallest(queue)
# take_smallest/1 returns a 3 tuple of {key, value, new_tree}
# where the new_tree is the original tree with the node that
# has the smallest key removed.
# The next line is necessary to avoid 'deduplicating' the
# queue of nodes that have min_dist as a potential edge cost.
# Arbitrarily taking the head of the list does not impact the
# correctness of the algorithm.
new_queue = if rest == [] do
new_queue
else
# If multiple nodes have an edge where distance == min_dist,
# we need to put the min_dist key back in the queue with the
# rest of those nodes as the value.
:gb_trees.enter(min_dist, rest, new_queue)
end
if not MapSet.member?(candidates, next_vertex) do
# If the node we chose as the current smallest distance edge
# from the queue has already been visited (i.e., removed from
# the candidates set), then we skip next_vertex and try again
do_prims(vertices, candidates, new_queue, cost)
else
# If next_vertex has not been visited yet, we mark it as
# visited and update the queue with edges connecting to
# next_vertex. Note that while the queue may include edges
# that would be discarded due to involved nodes already
# having been visited, this step will only ever introduce
# edges for nodes that have not been visited yet.
candidates = MapSet.delete(candidates, next_vertex)
updated_queue =
candidates
|> Enum.reduce(new_queue, fn i, q ->
d =
distance(vertices[i], vertices[next_vertex])
# Here's where :gb_trees could really use an ergonomic
# update_or_insert function. There is an update/3 but it
# crashes if the key is not present. It also does not take
# a function as a parameter for the update, so it is less an
# update as a replace method. That's why we first check if the
# distance is already a key in the GBT. If it is, we have to
# get the value of that key and add the current node to the
# list. Otherwise we can just wrap the current node in a list.
is = if :gb_trees.is_defined(d, q) do
is = :gb_trees.get(d, q)
[i | is]
else
[i]
end
:gb_trees.enter(d, is, q)
end)
# We have updated the candidates list and the queue, so we
# recurse with the updated cost.
do_prims(vertices,
candidates,
updated_queue,
cost + min_dist)
end
end
end
defp distance([a, b], [c, d]), do: abs(a - c) + abs(b - d)
Надеюсь, кому-то это будет полезно. Если у кого-то есть советы по оптимизации или исправлению моего понимания алгоритма Прима, я буду рад их услышать. Спасибо за чтение!