保存用遞歸回溯找到的最佳路徑

Question

我已經部分地解決了a problem on the UVA judge（參見下面的代碼），其中遞歸回溯/動態編程和位掩碼。

這給包含的測試用例提供了正確的最終答案，但是，我還必須打印最佳路徑路線，我不確定如何在遞歸例程中進行保存。

的問題是旅行商問題，基本問題是這樣的：

鑑於n座標，找到所有這些座標之間的最短路徑。

#include<iostream> 
#include<cmath> 
#include<climits> 
#include<cstdio> 
using namespace std; 

#define MAX_N 10 

struct Computer{ 
    double x; 
    double y; 
}; 

Computer computers[MAX_N]; 
double dist[MAX_N][MAX_N]; 
double DP[MAX_N][1 << MAX_N]; 

size_t n; 

double d(Computer a, Computer b) { 
    return sqrt(pow((a.x - b.x), 2.0) + pow((a.y - b.y), 2.0)) + 16.0; 
} 

double recurse(int i, int switched) 
{ 
    if(switched == (1 << n) - 1) return 0; 
    if(DP[i][switched] != 0) return DP[i][switched]; 

    double local_min = INT_MAX; 
    for(int j = 0; j < n; j++) 
    if(i != j && !(switched & (1 << j))) 
     local_min = min(dist[i][j] + recurse(j, switched | (1 << j)), local_min); 

    return DP[i][switched] = local_min; 
} 

int main() 
{ 
    for(unsigned int p = 1; cin >> n; p++) { 
    if(n == 0) return 0; 
    memset(DP, 0, sizeof DP); 

    for(size_t i = 0; i < n; ++i) { 
     Computer c; cin >> c.x >> c.y; 
     computers[i] = c; 
    } 

    for(size_t i = 0; i < n; ++i) for(size_t j = 0; j < n; ++j) 
     dist[i][j] = d(computers[i], computers[j]); 

    printf("%d: %.2f\n", p, recurse(0, 1)); 
    } 
} 

Answer 1

存儲路徑的常用方法是跟蹤存儲路徑搜索器到達當前點所用節點的附加地圖。當您找到到達最終節點的最佳路線時，您可以查詢該地圖，直到您返回到起始節點。

Answer 2

收集在一個玩家拼圖最佳路徑是類似的問題如保存在兩個玩家的遊戲，如國際象棋中主要變例。關於如何實施它，請參閱此link。

這個想法是存儲一個指向矢量/步驟數組的指針（在國際象棋中移動），並且只要你的回溯算法在最短路徑上發現改進，就更新該數組。