1

dijskstra のアルゴリズムを「グリッド」上で実行している場合、プライオリティ キューを使用しても意味がありません。

グリッドは次のようなマップになります: 頂点:

 ___________________
|A|_|_|_|_|_|_|_|_|_|
|C|B|_|_|_|_|E|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|D|_|_|_|_|_|F|_|_|_|
|_|_|_|_|_|_|_|_|_|_|

エッジ:

A <-> C
C <-> B
C <-> D
D <-> F
B <-> E
E <-> F

つまり、各エッジが水平または垂直にある頂点に接続しているが、斜めに接続できないマップ (たとえば、A から B へのエッジ、または A から F へのエッジは許可されません)。

さらに、エッジの重みは、グリッド内の位置に対して直感的です。たとえば、A <-> C の辺の重みは 1、C <-> B は 1、C <-> D は 6、B <-> E は 5、D <-> F と E <-> F は両方 6。

このようなグラフのために、しばらく前にダイスクトラのアルゴリズムを実装しましたが、可能な限り高速になるように最適化する必要があります。私の現在の実装（ルビー）：

def self.dj_start(g,source, goal)
    t = Time.now
    visited, distances, paths, already_queued = {}, {}, {}, {}

    curr = g.verticies[source]
    queue = [] # 

    queue.push(curr)
    already_queued[curr] = true
    distances[curr] = 0
    paths[curr] = curr
    @count = 0
    while(!queue.empty?)
      run_dijkstra(g, visited, distances, paths, queue, already_queued, goal)
    end
    t = Time.now - t
    print "ran dijkstra in #{t}s count = #{@count}\n"
    return [paths, distances]
end

def self.run_dijkstra(g, visited, distances, paths, queue, already_queued, goal)
curr = g.verticies[queue.delete_at(0)]
visited[curr] = true

curr.edges.each do |e|
    @count+=1
      if !already_queued[e.vertex] && !visited[e.vertex]
        queue.push(e.vertex) 
        already_queued[e.vertex] = true
      end

      nd = e.weight+distances[curr]
      if distances[e.vertex].nil? || nd < distances[e.vertex]
        distances[e.vertex] = nd
        paths[e.vertex] = curr

        if e.vertex.eql?(goal) # minor optimization
          queue = []
          return 1 # Code for exit due to this very minor optimization
        end
      end # end distance check
end

終わり

プライオリティ キューを使用して書き直すつもりでしたが、その必要性がわかりません。または、何か不足していますか？

4

1 に答える 1

0

通常、同様の問題は、各セルがグラフの頂点である幅優先探索を使用して解決されます。それでも解決している問題では、グリッド内のセルの数と比較して有効な位置の数が非常に少ないため、アプローチが機能する可能性があります。エッジの重み (つまり、位置間を移動する必要があるセルの最小数) は、何らかの方法でプログラムに提供する必要があることに注意してください。そうでない場合は、BFS を使用してこれらを計算する必要があるため、ダイクストラには意味がありません。

そうは言っても、私はあなたの質問に答えます。ここに示すようにエッジが提供されている場合、優先キューを使用する理由があります。これにより、アルゴリズムの計算の複雑さが桁違いに減少します。これは、より大きなグリッドでは明らかです。

ところで、フィボナッチ ヒープを実装する Ruby 用の本当にクールな gem があります。ここで示したサイズの grpah にフィボナッチ ヒープを使用するのは非常にやり過ぎかもしれませんが、フィボナッチ ヒープ ベースのダイクストラを使用することは常にクールだと思います。

この回答がお役に立てば幸いです。

于 2012-12-20T20:52:06.750 に答える