圖形理論 - 用有限數量的路線填充節點

Question

首先我必須說這不是一個家庭作業或相關的東西，這是一個名爲（freeciv）的遊戲的問題。好吧，在遊戲中我們通常有n個城市（8-12），每個城市通常可以有最大數量的'k'貿易路線（4），而這些貿易路線需要距離或更遠（曼哈頓8片）。

問題在於找到具有（最大距離或最小距離）的k * n交易路線，顯然這個問題可以用蠻力算法解決，但當玩家擁有超過10個城市，因爲該計劃必須進行幾次迭代;我試圖用圖論來解決它，但我不是一個非專家，我甚至問過我的一些老師，沒有人能向我解釋一個智能算法，所以我沒有來這裏找到確切的解決方案，但我做得到的想法或步驟來分析這一點。

Answer 1

的問題有兩個部分：城市

選擇哪對應當成爲貿易路線之間

1. 計算成對距離

我不認爲第一部分的計算速度可能快於O（n·t）其中t是瓦片的數量，因爲每次運行Dijkstra算法都會給你從一個城市到所有其他城市的距離。但是，如果我理解正確，兩個城市之間的距離永遠不會改變，並且是對稱的。所以每當建立一個新城市時，您只需要運行Dijkstra的算法並緩存距離。

對於第二部分，我期望貪婪算法的工作。按照適宜性對所有城市對進行排序，並在每個步驟中挑選第一個不違反每個城市的限制條件的城市。我不確定它是否可以被證明（證明應該類似於Kruskal's minimal spanning-tree algorithm存在的證據，但是我認爲即使你發現它在理論上不起作用，它在實踐中也能正常工作（我還沒有嘗試過。要麼證明或反駁它，這完全取決於你）

Answer 2

繼續@Jan鄔達克方式：

初始化階段：
可以說你有N個城市（C1，C2，... CN），你應該當列表中的每個實體的格式爲（cX，cY，Distance）（而X < Y，這是n^2/2時間）並按距離排序（按照最大距離或遞減排序）或建立一個連接列表最小距離），並且你還應該有一個數組/列表來保存連接的數量每個城市的離子數（cZ = W）在N-1的每個城市初始化，因爲它們都在開始時連接。

迭代： 迭代過連接 爲每個（CX，CY，d）的列表，如果連接的CX> k和CY> 10k，則刪除（CX，CY的數量（連接數陣列中）， D）從連接列表中減去1，並且在連接數組中減去cX和cY的值。

最後，你會得到你想要的值的連接列表。