1

次の NP 完全問題があります。

与えられた:

  • N × N フィールド内の位置のセット、
  • m 個のノードのセット、および
  • ノードの接続性グラフ (つまり、エッジが互いに接触しているノードのすべてのペアを表す無向グラフ)、および
  • 接触範囲 R (N × N フィールドと同じ長さ単位)、

接続グラフを考慮してフィールド内のノードの配置を見つける (つまり、接触しているペアが R よりも近く、接触していないペアが R よりも遠いようにノードを配置する)、またはそのような配置が存在しないことを示します。

この問題を還元できる有名な NP 完全問題はありますか?

(問題の最適化バージョン、つまり最適な配置を見つけることも考えられます)

4

1 に答える 1

0

セットカバーは、この問題のように聞こえます。実際、それはほぼ正確にこの問題である可能性があります。さらに良いことに、最適解の O(log n) 以内にあることが保証された近似アルゴリズムがあります。

于 2011-12-03T16:30:07.077 に答える