具有K額外節點的最小生成樹

Question

假設我們在2D平面上給出了一個圖，其中節點和每對節點之間的邊具有等於歐幾里得距離的權重。最初的問題是找到這個圖的MST，並且很清楚如何使用Prim's或Kruskal算法來解決這個問題。

現在我們假設我們有k額外的節點，我們可以將它放在我們的2D平面上的任何整數點上。問題是如果沒有必要使用所有這些額外節點，則爲這些節點查找位置，以便新圖具有儘可能最小的MST。

顯然不可能找到確切的解決方案（在多時間），但目標是找到最佳近似解（可在1秒內找到）。也許你可以想出一些最有效的拋出可能解決方案的提示，或者提供一些文章，其中涉及類似的問題。

Answer 1

這是你正在研究的非常有趣的問題。你有很多選擇來解決這個問題。在這種情況下最有名的啓發式是 - Genetic Algorithms,Particle Swarm Optimization,Differential Evolution和這類許多其他類型。

這種啓發式算法的好處在於，你可以限制它們的執行時間（比如說1秒）。如果這是我的任務，我會嘗試第一個遺傳算法。

Answer 2

您可以嘗試使用貪婪算法，嘗試MST中最長的邊緣，這可能會給您帶來最大的節省。

選擇最長的邊，現在從每邊從每個角度關閉的頂點獲取從所選角度關閉的邊的潛在邊。

從這些選擇最好的斯坦納點。

修復MST ...

重複，直到1秒消失。

挑戰是如果其中一個頂點本身是斯坦納點，該怎麼辦。