5

分類アルゴリズムを試しているときに、次のアルゴリズムの問​​題が発生しました。要素は多階層に分類されます。これは、単一のルートを持つ半順序集合であると私は理解しています。集合被覆問題によく似た次の問題を解決する必要があります。

ラテックスで作成した問題の説明をここにアップロードしました。

1と2を満たす近似アルゴリズムを考案するのは非常に簡単です。Gの頂点から開始して「上に移動」するか、ルートから開始して「下に移動」します。ルートから開始し、頂点を繰り返し展開してから、少なくともk個の副格子ができるまで不要な頂点を削除するとします。近似限界は、頂点の子の数に依存します。これは、私のアプリケーションでは問題ありません。

この問題に固有名があるかどうか、または問題のツリーバージョンがあるかどうかを誰かが知っていますか？この問題がNP困難であるかどうかを知りたいと思います。おそらく、誰かがNP困難な問題を減らすためのアイデアを持っているか、問題を解決するための多項式アルゴリズムを持っているかもしれません。あなたが両方を持っているならば、あなたの百万ドルの価格を集めてください。;）

4

1 に答える 1

2

DAGバージョンはセットカバーからの縮小（ドラムロール）によりハードです。k = 2に設定し、明らかなことを行います。条件（2）は、ルートを取得できないようにします。（（3）は、下限kのため、実際には（2）を意味しないことに注意してください。）

ツリーバージョンは、直並列ポセットバージョンの特殊なケースであり、多項式時間で正確に解くことができます。これは、多項式p（x）を与える再帰式です。ここで、x nの係数は、カーディナリティnのカバーの数です。

カバーされる単一の頂点：p（x）=x。

その他の頂点：p（x）= 1+x。

並列合成。ここで、qとrは2つの半順序集合の多項式です：q（x）r（x）。

系列構成。ここで、qは上部のポセットの多項式、rは下部の多項式です。上部のポセットにカバーする頂点が含まれていない場合、p（x）=（q（x）-1）+ r（x）; それ以外の場合、p（x）= q（x）。

于 2010-07-17T16:45:21.700 に答える