6

免責事項：著者はErlangの初心者です。

想像してみてください。1Mノードで構成されるグラフがあり、各ノードには0〜4個の隣接ノードがあります（エッジは各ノードからそれらの隣接ノードに出ているため、グラフは方向付けられて接続されています）。

これが私のデータ構造の選択です：

グラフを保存するには、ETSテーブルに基づく有向グラフを使用します。これにより、ノードのネイバーへの高速（O（1））アクセスが可能になります。

未訪問のノードのリストには、gb_sets：take_smallestを使用します（ノードは既にソートされており、フェッチ後に同時に削除されます）。

先行のリストには、dict構造を使用します。これにより、先行を次の方法で格納できます：{Node1、Node1_predecessor}、{Node2、Node2_predecessor}。

訪問したノードのリストには、単純なリストを使用します。

問題：

  1. 有向グラフ構造とUnvisited_nodes構造の両方でノードの重みを更新しようとすると、コードの読み取りと保守が非常に困難になります。2つのデータ構造で同時に更新する必要がある「フィールド」を持つ1つの「オブジェクト」を保持するのは正しい方法ではないようです。それを行う正しい方法は何ですか？
  2. 同じ質問が前任者リストについてです。ノード「オブジェクト」の先行「フィールド」をどこに保存する必要がありますか？多分グラフ（有向グラフ構造）にありますか？
  3. オブジェクト（ノードとエッジ）とそのフィールド（重み）ではなく、プロセスとメッセージの観点から、ダイクストラのアルゴリズム全体を再考する必要があるかもしれません。

UPD：

アントナコスの推奨に基づくコードは次のとおりです。

dijkstra(Graph,Start_node_name) ->

    io:format("dijkstra/2: start~n"),

    Paths = dict:new(),
    io:format("dijkstra/2: initialized empty Paths~n"),

    Unvisited = gb_sets:new(),
    io:format("dijkstra/2: initialized empty Unvisited nodes priority queue~n"),

    Unvisited_nodes = gb_sets:insert({0,Start_node_name,root},Unvisited),
    io:format("dijkstra/2: Added start node ~w with the weight 0 to the Unvisited nodes: ~w~n", [Start_node_name, Unvisited_nodes]),

    Paths_updated = loop_through_nodes(Graph,Paths,Unvisited_nodes),
    io:format("dijkstra/2: Finished searching for shortest paths: ~w~n", [Paths_updated]).




loop_through_nodes(Graph,Paths,Unvisited_nodes) ->
    %% We need this condition to stop looping through the Unvisited nodes if it is empty
    case gb_sets:is_empty(Unvisited_nodes) of
        false -> 
            {{Current_weight,Current_name,Previous_node}, Unvisited_nodes_updated} = gb_sets:take_smallest(Unvisited_nodes),
            case dict:is_key(Current_name,Paths) of
                false ->
                    io:format("loop_through_nodes: Found a new smallest unvisited node ~w~n",[Current_name]),

                    Paths_updated = dict:store(Current_name,{Previous_node,Current_weight},Paths),
                    io:format("loop_through_nodes: Updated Paths: ~w~n",[Paths_updated]),

                    Out_edges = digraph:out_edges(Graph,Current_name),
                    io:format("loop_through_nodes: Ready to iterate through the out edges of node ~w: ~w~n",[Current_name,Out_edges]),

                    Unvisited_nodes_updated_2 = loop_through_edges(Graph,Out_edges,Paths_updated,Unvisited_nodes_updated,Current_weight),
                    io:format("loop_through_nodes: Looped through out edges of the node ~w and updated Unvisited nodes: ~w~n",[Current_name,Unvisited_nodes_updated_2]),

                    loop_through_nodes(Graph,Paths_updated,Unvisited_nodes_updated_2);
                    true ->
                    loop_through_nodes(Graph,Paths,Unvisited_nodes_updated)
            end;
        true -> 
            Paths
    end.

loop_through_edges(Graph,[],Paths,Unvisited_nodes,Current_weight) ->
                    io:format("loop_through_edges: No more out edges ~n"),
    Unvisited_nodes;

loop_through_edges(Graph,Edges,Paths,Unvisited_nodes,Current_weight) ->
                    io:format("loop_through_edges: Start ~n"),
    [Current_edge|Rest_edges] = Edges,
    {Current_edge,Current_node,Neighbour_node,Edge_weight} = digraph:edge(Graph,Current_edge),
    case dict:is_key(Neighbour_node,Paths) of
        false ->
                    io:format("loop_through_edges: Inserting new neighbour node ~w into Unvisited nodes~n",[Current_node]),
            Unvisited_nodes_updated = gb_sets:insert({Current_weight+Edge_weight,Neighbour_node,Current_node},Unvisited_nodes),
                    io:format("loop_through_edges: The unvisited nodes are: ~w~n",[Unvisited_nodes_updated]),
            loop_through_edges(Graph,Rest_edges,Paths,Unvisited_nodes_updated,Current_weight);
        true ->
            loop_through_edges(Graph,Rest_edges,Paths,Unvisited_nodes,Current_weight)
    end.
4

1 に答える 1

1

データ構造の選択は問題ないように見えるので、ほとんどの場合、データ構造に何を挿入し、どのようにデータ構造を最新の状態に保つかが問題になります。私は次のことを提案します（私は名前を少し変更しました）：

  • Result：へのマッピングdict。ここで、はへのパスの総コストであり、はパス上のその前身です。Node{Cost, Prev}CostNodePrev

  • Open：のgb_sets構造{Cost, Node, Prev}。

  • フォームのエッジを持つグラフ{EdgeCost, NextNode}。

検索結果はで表されResult、グラフはまったく更新されません。マルチプロセッシングやメッセージパッシングはありません。

アルゴリズムは次のようになります。

  • に挿入{0, StartNode, Nil}します。OpenここNilで、はパスの終わりを示すものです。

  • しましょう{{Cost, Node, Prev}, Open1} = gb_sets:take_smallest(Open)。Nodeがすでに入っている場合はResult、何もしません。それ以外の場合は、に追加{Cost, Node, Prev}し、追加Resultのすべてのエッジ{EdgeCost, NextNode}に対して、がまだに含まれていない場合に限ります。セットが空になるまで続行します。Node{Cost + EdgeCost, NextNode, Node}Open1NextNodeResultOpen1

decrease_key()ダイクストラのアルゴリズムは、セットに対する操作を要求しOpenます。これはサポートされていないため、すでに存在している可能性がある場合でもgb_sets、タプルを挿入する回避策を使用しました。そのため、から抽出されたノードがすでににあるかどうかを確認します。NextNodeNextNodeOpenOpenResult

優先キューの使用に関する詳細な説明

ダイクストラのアルゴリズムで優先キューを使用する方法はいくつかあります。

ウィキペディアの標準バージョンでは、ノードvは1回だけ挿入されますがv、コストと先行バージョンvが変更されると、の位置が更新されます。

alt := dist[u] + dist_between(u, v)
if alt < dist[v]:
    dist[v] := alt
    previous[v] := u
    decrease-key v in Q

decrease-key v in Q多くの場合、実装は。に置き換えることで簡素化されadd v to Qます。これは、vを複数回追加できることを意味します。したがって、アルゴリズムはu、キューから抽出されたものが結果にまだ追加されていないことを確認する必要があります。

私のバージョンでは、上記のブロック全体を。に置き換えていadd v to Qます。したがって、キューにはさらに多くのエントリが含まれますが、それらは常に順番に抽出されるため、アルゴリズムの正確性には影響しません。これらの追加のエントリが必要ない場合は、辞書を使用して各ノードの最小コストを追跡できます。

于 2011-07-17T20:33:46.440 に答える