Elixir의 Prim 알고리즘

Prim의 알고리즘은 그래프의 모든 노드를 포함하는 최저 비용 트리를 찾기 위한 그리디 알고리즘이며 최소 스패닝 트리라고도 합니다. 이를 구현하는 방법에 대한 블로그 게시물과 자습서가 많이 있지만, 데이터 구조가 변경되지 않는 기능적 스타일이나 기능적 언어의 구현에 대한 정보를 찾기가 어려웠습니다.

아래 구현에서 그래프의 노드는 정렬되지 않은 목록으로 제공됩니다. 인덱스로 액세스할 수 있는 튜플로 목록을 사용하는 것이 가장 쉽다는 것을 알았습니다. 노드 모음은 변경되지 않지만(추가 또는 삽입 없음) 자주 액세스됩니다. 인덱스로 튜플에 액세스하는 것이 매우 빠르기 때문에 이것이 좋은 접근 방식이라고 느꼈습니다. 즉, 필요하지 않으며 실제로 스타일에서 덜 "기능적"이 될 수 있습니다.

Prim의 알고리즘에는 방문한 모든 노드 집합(즉, 최소 스패닝 트리에 포함된 노드)과 그래프의 모든 노드 집합이라는 두 가지 수학적 집합이 필요합니다. 시작할 임의의 노드를 선택하고 방문하지 않은 노드를 반복하여 MST에 연결할 최소 거리를 찾습니다. 이 두 세트가 동일할 때 알고리즘이 완료됩니다. 아래의 구현에서 저는 단순히 방문하지 않은 노드 집합을 추적하도록 선택했으며 집합이 비어 있을 때 알고리즘이 완료됩니다. 이 경우 MST 자체가 아니라 MST 비용에만 관심이 있기 때문입니다. MST를 반환해야 하는 경우 원래 노드 집합과 함께 방문한 노드를 추적합니다.

또한 그래프에서 모든 에지의 비용을 알 수 있는 방법이 필요합니다. 이 경우 그래프가 일련의 {x, y} 좌표 쌍으로 주어지고 가장자리의 가중치가 그들 사이의 Manhattan distance에 의해 주어진다고 가정합니다.

시작하려면 방문하지 않은 노드 집합, 최소 스패닝 트리의 실행 "비용"및 우선순위 대기열을 인스턴스화합니다. 이 경우에는 일반 균형 트리를 우선 순위 대기열 구조로 사용하고 있습니다. 정확히 동일하지는 않지만 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)

누군가 이것이 도움이 되기를 바랍니다. 누구든지 Prim의 알고리즘에 대한 이해에 대한 최적화 또는 수정에 대한 팁이 있으면 듣고 싶습니다. 읽어 주셔서 감사합니다!