蠻力方法和併發線程之間的選擇

Question

我有一個關於圖的問題。考慮一個帶有節點和邊的圖，每個邊都有成本。問題是訪問所有節點，以便所遍歷的邊的成本總和最小（我猜想是旅行推銷員問題）。

你會推薦哪種方法？通過遞歸使用蠻力方法，或者通過產生線程來使用蠻力來同時傳播不同的路徑並計算它們的成本。

還是你有更好的方法來解決這個問題？

Answer 1

我會去多線程的方法，因爲它會並行地做事情。作爲一個附加的優化，我還會保留某個共享變量中完整路徑的最低成本，並讓每個線程檢查成本 - 如果在遍歷之間它們超過了該成本，我將立即終止處理。

Answer 2

因爲我不知道你爲什麼這樣做，也不知道你的約束是什麼，我投票選擇單線程遞歸。這很容易。

Answer 3

遞歸更簡單，並且由於它的蠻力，多線程並不能保證更快地爲您提供解決方案。但是你另起爐竈之前，請協和TSP求解：

http://www.tsp.gatech.edu/concorde/index.html

這是一個免費下載，包括源。

Answer 4

TSP是NP難的。參見維基百科。它的規模可怕。 多線程它在一個4核心可以使它快4倍， 這是沒有什麼比100,1000或1000000次慢 當你嘗試一個稍大的問題。 只需嘗試一下真實大小的數據，它可能需要幾年時間才能完成。

一個解決方案是元啓發式，有幾個庫，如Drools Planner（開源，Java）的 。看看其TTP示例。