1

次の問題のアルゴリズムを構築するのに助けが必要です。

他のポイントCを「見る」ことができるポイントGのセットがあります。GからCのすべてをカバーする最小セットを見つけるアルゴリズムが必要です( Gは必ずしもCの一部ではありません)。

これは動的計画法で解決すべきだと感じています。しかし、私は私を助けることができる解決策/アイデアに対してオープンです.

ありがとう！

編集1：

問題を完全に理解していない可能性があります。

ポイントは、地形の高さを持つ 3D サーフェス上にあります。地形はポイント間で特定の高さまで上昇する可能性があり、ポイントが他のポイントを見ることができないようになります。直接の視線がある限り、距離に関係なく、ポイントは互いに見ることができます。

  • 点a ( Gから) が点b ( Cから) を見ることができ、点bが( Cから) dを見ることができる場合、 aはdを見ることができます。これが違いを生むかどうかはわかりません。

  • a ( Gから)だけがb ( Cから) を見ることができる場合、すべてのCをカバーするためにaを選択する必要があります。

新しい情報に照らして、他に違いがあるかどうかはまだ考えています.

4

1 に答える 1

2

あなたの問題はSet cover problemと呼ばれます。NP完全です。

貪欲な log( n ) 近似アルゴリズムを使用します。すべてのステップで、まだカバーされていない (C) のポイントの最大数をカバーする (G) の要素を選択します。

インターネット上にある講義ノートのほとんどは、上記の近似アルゴリズムのみを示しています。

Lund & Yannakakis (1994) によって証明されているように、上記のアルゴリズムよりもはるかに優れた処理を行うことは非常に困難です。ウィキペディアの記事内で参照を見つけることができます。

セット カバー問題の同等の整数線形問題定式化を使用することもできます。しかし、ここでも log(n) 近似アルゴリズムが得られます。

近似アルゴリズムは他にもありますが、ほとんどが研究論文に書かれているため、説明がわかりにくいです。「近似アルゴリズムセットカバー」をグーグルで検索するだけでそれらを見つけることができます

問題がNP完全であるか、動的計画法などを使用したソリューションが存在する既知の問題tiのバリアントであるかを知るための経験則があるかどうかはわかりません。しかし、ここに質問を投稿しました。

( Gからの) aだけが ( Cからの) bを見ることができる場合については、欲張りアルゴリズムはCからのすべてのポイントが見られる場合にのみ停止するため、とにかくaを選択します。アルゴリズムが点を選択する順序によって、解が変わることはありません。

点a ( Gから) が点b ( Cから ) を見ることができ、点bが( Cから) dを見ることができる場合、 a がdを見ることができるという事実は、問題を平面グラフでモデル化することを許可しません。平面グラフには、貪欲なアルゴリズムよりも優れた、問題に対するより優れた近似アルゴリズムがあります。

于 2012-05-14T19:57:22.747 に答える