재귀 적 역 추적으로 최적 경로를 찾음

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을 참조하십시오.

아이디어는 단계의 벡터/배열 (체스 이동)에 대한 포인터를 저장하고 백 트랙 알고리즘이 지금까지 최단 경로에서 개선을 찾을 때마다 해당 배열을 업데이트하는 것입니다.