1

誰もこの問題を見たことがありますか？NP完全であるはずです。

頂点 V_1,...,V_n と、各頂点の可能な親セットが与えられます。各親セットには関連するコストがあります。O を頂点の順序 (順列) とする。すべての親が順序で頂点の前に来る場合、頂点 V_i の親セットは順序付け O と一致すると言います。mcc(V_i, O) を、順序 O と一致する頂点 V_i の親セットの最小コストとします。合計コストを最小にする順序 O を見つける必要があります: mcc(V_1, O), ... ,mcc( V_n、O)。

「...すべての親が順序で頂点の前に来る場合」の部分がよくわかりません。どういう意味ですか？

4

1 に答える 1

1

いいえ、その問題は見たことがありません。

あなたが確信していないビットについては、順序付けはすべての頂点の順序にすぎないため、「順序付けですべての親が頂点の前に来る場合」は、まさにそれが言うことを意味すると思います。たとえば、(A, B) が D の 1 つの親セットであるとします。A と B は D の前にあり、順序 [A ,D,B,C]、B は D の後にあるため。ただし、(A) が D の別の親セットであるとします。これは、これらの両方の順序付けと一致しています。それは理にかなっていますか？

于 2012-05-27T07:22:02.957 に答える