瞭解這種NP完全優化？

有沒有人見過這個問題？它應該是NP完全的。瞭解這種NP完全優化？

給出每個頂點的頂點V_1，...，V_n和可能的父集。每個家長組都有相關的成本。設O是頂點的排序（排列）。我們說如果所有的父母都在排序中的頂點之前，頂點V_i的父集合與排序O一致。令mcc（V_i，O）是頂點V_i父集合的最小代價，它與O的排序一致。我需要找到一個最小化總成本的排序O：mcc（V_1，O），...，mcc（ V_n，O）。

我不太瞭解部分「......如果所有的父母都在排序的頂點之前。」這是什麼意思？

來源

2012-05-27 Mark

也許它意味着三角不等式？ – Bytemain

校對說明：「是頂點$ V_i $的父集的最小開銷」位在您的文本中重複兩次。另外，$被包圍的字符串應該顯示爲特別的東西嗎？如果是，它不適合我。 – weronika

@weronika $符號圍繞乳膠中的數學表達式。它適用於http://cs.stackexchange.com/，但不適用於此站點。我們可以刪除它們並放置斜體。 –

不，我以前沒見過這個問題。

至於你不確定的位 - 排序只是所有頂點的順序，所以我認爲「如果所有的父母都在排序中的頂點之前」就意味着它的含義。例如，假設（A，B）是D的一個父集合：該父集合與排序[A，B，C，D]一致，因爲A和B在D之前，並且與排序[A ，D，B，C]，因爲B在D之後;然而，說（A）是D的另一個父親集合 - 那符合這兩個順序。那有意義嗎？

來源

2012-05-27 07:22:02 weronika

所以問題是要求找到頂點的拓撲排序？ –

@VitalijZadneprovskij - 老實說，我不確定問題是否有任何拓撲含義 - 問題的文本與調用項目頂點之外的圖形沒有任何關係。對期望排序的具體解釋取決於母公司和相關成本。 – weronika

瞭解這種NP完全優化？

回答

相關問題