最大的N-聯接的連接子圖中的一個節點加權圖表

Question

取本節點的加權圖，例如：

• 正好含有1個節點的最大子圖（和「入口點」）將是14.
• 包含正好2個節點（和「入口點」）的最大子圖將是14/9。
• 包含正好3個節點（和「入口點」）的最大子圖將是3/19/15.
• 正好含有4個節點的最大子圖（和「入口點」）將是14/1/7/240

我不能設法認爲更好的方法的比暴力破解得到最大子圖。
如果沒有已知的高效算法，在這種情況下是否會找到遺傳算法（交叉看起來很棘手）？

Answer 1

我認爲你可以修改Dijkstra's algorithm來解決這個問題。

使用Dijkrasta算法，您正在求解最短路徑。只需改變它即可找到最大路徑。要將其限制爲圖中只有1,2,3個節點，請記錄在「訪問」時訪問每個節點所需的節點數。當沒有其他節點的計數小於要查找的節點數時停止。