樹中的兩個節點不相交的路徑，使得這些長度的乘法得到最大值

我想在一棵有n個節點的樹中找到兩條路徑，以便這兩條路徑沒有任何公共節點，並且長度的乘法這兩條路徑的最大值。任何人都可以幫助我如何解決這個問題？樹中的兩個節點不相交的路徑，使得這些長度的乘法得到最大值

來源

2013-01-06 Nstar

爲什麼長度的乘法？ –

如果在這棵樹中有兩條長度爲L和M的路徑，那麼L * M應該是最大的！這是一個實踐問題，並沒有任何特別的理由：D – Nstar

邊緣長度的限制是什麼？所有的邊都有長度1嗎？或者他們可以是正面的長度？他們可以是非整數？ –

首先，使用遞歸過程生成每個可能的唯一路徑的列表。

您最終得到m個可能的路徑。

其次，建立一個m×m個元素的數組。

用所有其他m-1路徑檢查每一條m路徑，並將相應長度的乘積存儲到數組中。這樣做檢查兩條路徑是否有共同的節點。如果這樣存儲的話0.

第三，檢查m×m數組中的值最大的元素。

你還能做什麼？這是非常蠻力的，但如果沒有更多關於樹屬性的信息，這是唯一的方法。

來源

2013-01-06 21:05:39 Paolo

非常感謝你的回答:)。這棵樹最多包含1000個節點，並且沒有更多的信息，但是這個程序應該在2秒內運行！所以可能是蠻力無效的工作！ – Nstar

如果這是一個實踐問題（正如您在發帖下方的評論中所述），那麼2秒運行時的原因是什麼？如果你想要任何可行的解決方案，那麼上面的貪婪算法修改將會起作用。但是，如果你想要（獨特的？）MAXIMUM解決方案，那麼 - 不知怎的，你需要所有可能的組合。沒有實際搜索每種可能性並評估每個可行性和「成本」（L * M）的理由，沒有理論方法來獲得這些可能性。 –

報價：「但這個程序應該運行在2秒以下」。這三個步驟都適合寫入獨立線程中運行。如果你用編譯語言編寫程序（我建議使用普通的C語言），它是多線程的，它可以在不到2秒的時間內完成任務。如果不是......添加內核。但是，再一次......這僅僅是一個IT謎團，還是這個樹實際上是出自一些真實的場景？我猜想可以根據數據的來源做出一些假設。這可能會以更復雜但更高效的算法結束。 – Paolo

有些想法。如果有兩個值a和b合計爲n，則a * b的最大值是a == b（爲了簡單起見，假設n是偶數）。如果有一條路徑經過所有n個節點，將其切割成兩個幾乎相等的部分。對於偶數n的這樣的圖，答案將是（n^2）/ 4，對於奇數n，它將是（n-1）/ 2 *（n + 1）/ 2 =（n^2 - 1）/ 4。如果沒有路徑經過所有n個節點，則必須使用其他一些技術。但上限如上。

來源

2013-01-07 00:23:29 user1952500

我認爲在樹中沒有路徑經過所有n個節點！ – Nstar

一些嚴重不平衡的樹有n個節點的路徑。 – user1952500

是啊:)但不是所有的樹！所以它不能成爲這個問題的完整答案 – Nstar

樹中的兩個節點不相交的路徑，使得這些長度的乘法得到最大值

回答

相關問題