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 的一个父集：该父集与排序 [A,B,C,D] 一致，因为 A 和 B 在 D 之前，并且与排序 [A ,D,B,C]，因为 B 在 D 之后；但是，假设 (A) 是 D 的另一个父集 - 一个与这两个顺序一致。那有意义吗？

于 2012-05-27T07:22:02.957 回答