分區中的等值集

Question

我有一個簡單的非虛擬樹T。我應該找到一條名爲A的路徑，另一個名爲B的路徑，A和B沒有公共頂點。祕密是最大化Len(A)*Len(B)。

我想這個問題是模擬分區問題，除了在分區問題你有一套，但在這裏你有一個等效設置。解決方法是找到Len(A) ~ Len(B) ~ [n-1/2]兩條未交叉的路徑。這是否正確？我應該如何推崇這樣的算法？

Answer 1

首先。我認爲你正在以錯誤的方式看待這個問題。據我所知，你有一個相關的問題。你要做的就是

1. 建立一個最大生成樹和找​​到長度L
2. 現在，你說這兩個路徑上，不能有任何共同的頂點，所以我們要刪除的邊緣來實現這一點。我假設圖中的每個邊都是1.因此，在刪除邊之後，兩條路徑A和B的總和爲L-1。現在的問題是，你必須去除一個邊，使len（a）和len（b）的乘積最大化。你可以通過刪除L的最邊緣來做到這一點。爲什麼問題與優化具有固定周長的矩形的面積相同。關於這個問題的一個短的YouTube視頻可以找到here。

注意如果您的邊緣wheights不等於1，那麼你有一個困難的問題，因爲有可能存在多於一個最大生成樹。但是你也許能夠以不同的方式分割它們，如果是這樣的話，請寫回我，然後我會考慮一個解決方案，但我手邊沒有。

祝你好運。

Answer 2

我想有一個動態規劃解決方案，如果路徑長度只是路徑中的鏈接數量（因此鏈接沒有權重），那麼這個解決方案就很容易處理。

工作從葉子上。在每個節點上，您需要跟蹤限制在該子節點上的最佳解決方案對，並且對於每個k，使用長度爲k的路徑終止於該節點並且具有最大長度的第二個路徑的最佳解決方案在那個節點下面的某個地方並且不接觸路徑。

給出此節點的所有後代的信息，您可以爲該節點生成類似的信息，因此請按照路線行事。

如果您考慮一棵實際上只是一排節點的樹，您可以看到這一信息量是必需的。節點線的最佳解決方案是將其分成兩部分，因此如果只在線長度爲2n + 1時才制定出最佳解決方案，那麼您將不需要長度爲2n的行的構建塊+ 3.