2

Kruskal の MST 構築アルゴリズムは貪欲だと言われていますが、このアルゴリズムは Prim のアルゴリズムとは異なり、局所的最小値ではなく大域的最小値を選択します。Kruskalのアルゴリズムが貪欲なアプローチと見なされる方法を誰かが説明できますか?

4

3 に答える 3

1

クラスカルで何をしますか？まず、重みに従ってエッジを並べ替えます。次に、重みが最小のエッジを選択します。循環しない場合は、そのエッジを追加します。このように貪欲に前進します。だから貪欲なアプローチです。:)

貪欲なアプローチは貪欲と呼ばれます。これは、期待する各段階で最適な選択が必要であり、それが全体の最適解を与えるからです。

于 2014-12-24T16:58:41.077 に答える
1

まず第一に、貪欲であるとはどういう意味ですか？

貪欲なアルゴリズムは、グローバルな最適を見つけることを目的として、各段階で局所的に最適な選択を行うという問題解決ヒューリスティックに従う任意のアルゴリズムです。
----ウィキペディア https://en.wikipedia.org/wiki/Greedy_algorithm

したがって、「貪欲なアルゴリズム」とは、評価するのに費用がかかりすぎない限定された「短期」基準に従って、個々の選択が最適になるように、順番に選択を行うことです。

ここでクラスカルのアルゴリズムでは、「選択」は「次に低い重みでエッジを選択し、既に選択されたエッジでサイクルを形成しない」ことであり、ソートアルゴリズムとユニオン検索データ構造を考えると、評価するのにそれほど高価ではありません。

質問で言及した極小値は、隣接する頂点やエッジではなく、グラフの現在の知識として理解する必要があります。

于 2020-03-10T04:55:03.753 に答える
0

これは貪欲なアルゴリズムです。利用可能な最小の重みに従って各ステップで頂点の 2 つのセットを結合することを選択し、その時点で最適に見えるエッジを選択したからです。これは貪欲なステップであるため、アルゴリズムは貪欲であると言われます。

ウィキペディアの疑似コード (添付) では、貪欲なステップは の選択にあり(u,v)ます。これは、2 つの接続されていないコンポーネントを接続する最も重みの低いエッジです。

KRUSKAL(G):
1 A = ∅
2 foreach v ∈ G.V:
3   MAKE-SET(v)
4 foreach (u, v) ordered by weight(u, v), increasing:
5    if FIND-SET(u) ≠ FIND-SET(v):
6       A = A ∪ {(u, v)}
7       UNION(u, v)
8 return A
于 2014-12-24T16:55:52.467 に答える