1

以下は、CSアルゴリズムの講師によるクラスカルの最小スパニングツリーアルゴリズムの擬似コードです。MSTアルゴリズムが非決定論的であるかどうかを知りたいと思いました。同じ重みを持つ2つのエッジが与えられた場合、Tに追加するときにどちらのエッジもサイクルを形成しなかった場合、アルゴリズムはどのようにそれらを決定しますか。確かにランダムである場合、Tに追加された正確なエッジの結果を判断できません。

    Given an undirected connected graph G=(V,E)    
    T=Ø //Empty set, i.e. empty
    E'=E
    while E'≠Ø do
    begin
        pick an edge e in E' with minumum weight
        if adding e to T does not form a cycle then
            T = T∪{e} //Set union, add e to T
        E' = E'\{e} //Set difference, remove e from E'
    end

ありがとう！

4

2 に答える 2

3

クラスカルのアルゴリズムは、選択肢がある場合に決定論的選択関数を選択すると決定論的であり、そうでない場合は非決定論的です。無作為に選択すると、複数の可能性がある場合に MST で最終的にどのエッジになるかわかりません。

于 2012-05-26T15:28:31.360 に答える
2

同じ重みを持つ 2 つのエッジが与えられた場合、T に追加するときにどちらのエッジもサイクルを形成しない場合、アルゴリズムはそれらをどのように決定しますか? 確かに、それがランダムである場合、どの正確なエッジが T に追加されるかの結果を決定できませんか?

これは実装次第です。

Kruskal のアルゴリズムは、接続された重み付きグラフ (ツリーではない) の多くの可能な MST の 1 つを見つけます。これは、反復ごとに複数の選択肢があるためです (エッジ内から同じ重みを持つエッジを選択する)。これは非決定論的ビットです。もちろん、アルゴリズムを実装するときは、選択を行います (つまり、順序を課す) ことになりますが、別の実装では別の順序を課すことができます。したがって、アルゴリズムの 2 つの実装があり、同じ問題を正しく解決しますが、最終結果が異なる可能性があります。

于 2012-05-26T15:29:30.867 に答える