爲什麼克魯斯卡爾算法在貪婪的情況下找到最小生成樹？

Question

爲什麼克魯斯卡爾算法在貪婪的情況下找到最小生成樹？全局最優化問題不是最小生成樹嗎？是不是貪婪的一點是有沒有機會找到最理想的解決方案？那麼克魯斯卡爾怎麼能夠在貪婪的同時找到最小生成樹呢？

Answer 1

好吧，讓我們假設你是對的，所以克魯斯卡爾算法找不到最優解。通過克魯斯卡爾算法S和最優解T找到解。

必須有一個邊緣e = (u, v)出現在S但不在T。由於T是一棵生成樹，節點u和節點v之間必須有一條路徑。

現在我們應該注意到路徑u-v的至少一條邊的權重不小於e。否則，Kruskal算法會選擇路徑u-v中的所有邊而不是邊e。

這意味着，如果我們刪除邊緣並在解決方案T上添加e，則解決方案不會變得更糟。而且我們假設T是最優的，在這個變化之後，樹仍然是最優的。如果我們反覆應用這個邏輯，我們總是可以製作S。

Answer 2

我不確定你的意思。

然而，維基百科說：

Kruskal算法是最小生成樹算法發現在森林連接任何兩棵樹儘可能少的重量的邊緣[1]它是一種圖論中的貪心算法，因爲它找到了一個連接加權圖的最小生成樹，並在每一步增加了成本弧。[1] 這意味着它找到形成包含每個頂點的樹的邊的子集，其中樹中所有邊的總權重最小化。如果圖形未連接，則會找到最小生成樹林（每個連接組件的最小生成樹）。

與此同時，約最小生成樹，維基說：

甲最小生成樹（MST）或最小重量生成樹是一個連接的，邊加權無向圖的邊的子集的連接的所有頂點一起，沒有任何週期和儘可能小的總邊權重。也就是說，它是一個邊緣權重總和儘可能小的生成樹。更一般地說，任何無向圖（不一定連接）都有一個最小生成森林，它是連接組件的最小生成樹的聯合。

所以結合這兩個：克魯斯卡爾基本上使用貪心搜索方法找到最小生成樹或森林。

Answer 3

我可以理解爲以下問題 - 貪婪並不總是最佳的，那麼爲什麼克魯斯卡爾算法得到最佳解決方案？ 所以這個問題可以分兩部分回答 -

1.克魯斯卡爾算法是否給出最優解？ 這已由@miheyan回答。

2.如果貪婪總是給出最優解？ 一般來說NO，貪婪總是沒有給出最優解，但是存在一組問題，其中貪婪方法給出最優解，而克魯斯卡爾算法則存在於該組中。

讓我們來看一個問題陳述 - 有兩個玩家（玩家A和玩家B）給予一堆面額不同的錢。假設有4個貨幣票據，其值分別爲 - 100,50,20,10。玩家一次選擇一個鈔票，他們將選擇交易。玩家A開始遊戲。獲勝者將是獲得更多錢的人。兩個球員都打出最佳狀態。誰會贏得比賽？ 現在嘗試用貪婪的方法解決這個問題，看看貪婪的方法是否提供了最優解決方案？採取不同的價值觀，不同的例子，並做你的家庭工作。

因此，底線是 - 對於一組問題貪婪解決方案總是最優的但不是所有問題。 希望它有幫助！