3

欲張りアルゴリズムとバック トラッキング アルゴリズムの両方を使用して、バック トレース アルゴリズムを実装しました。バック トラッキング アルゴリズムは次のとおりです。

MIS(G= (V,E): a graph): largest set of independent vertices
1:if|V|= 0
then return .
3:end if
if | V|= 1 
then return V
end if
pick u ∈ V
Gout←G−{u}{remove u from V and E }
Gn ← G−{ u}−N(u){N(u) are the neighbors of u}
Sout ←MIS(Gout)
Sin←MIS(Gin)∪{u}
return maxsize(Sout,Sin){return Sin if there’s a tie — there’s a reason for this.
 }

貪欲なアルゴリズムは、次数が最小のノードを繰り返し選択し、MIS に配置してから、そのノードとその隣接ノードを G から削除します。

エッジが存在する確率が 0.5 であるさまざまなグラフ サイズでアルゴリズムを実行した後、経験的に、バック トラッキング アルゴリズムは貪欲アルゴリズムよりも小さい最大独立集合を常に検出することがわかりました。これは期待されていますか？

4

2 に答える 2

0

あなたの解決策は奇妙です。バックトラッキングは通常、最適化ではなく、はい/いいえの問題に使用されます。あなたが書いたアルゴリズムは、あなたが選ぶ方法に大きく依存しますu。そして、あなたは決して後戻りしないので、それは間違いなく後戻りではありません.

このような問題は、次のようなさまざまな方法で解決できます。

  • 遺伝的プログラミング、
  • 徹底的な検索、
  • 双対グラフの問題を解く (最大クリーク問題)。
于 2013-05-28T23:01:06.700 に答える
0

Wikipediaによると、これは NP 困難な問題です。

A maximum independent set is an independent set of the largest possible size for a given graph G.
This size is called the independence number of G, and denoted α(G).
The problem of finding such a set is called the maximum independent set problem and is an NP-hard optimization problem.
As such, it is unlikely that there exists an efficient algorithm for finding a maximum independent set of a graph.

したがって、グラフの最大独立集合を見つけるには、利用可能なすべての状態をテストする必要があります (時間の複雑さが指数関数的であるアルゴリズムを使用して)。他のすべてのより高速なアルゴリズム (貪欲、遺伝的、ランダム化など) は、正確な答えを見つけることができません。彼らは最大の独立集合を見つけることを保証できますが、最大のものは見つけられません。

結論として、あなたのバックトラッキング アプローチは遅くて正確であると言えます。しかし、貪欲なアプローチは近似アルゴリズムにすぎません。

于 2019-05-23T12:00:42.677 に答える