TSP 문제 의 상 압 dp
TSP (Traveling Salesman Problem) 。
N ， ，
， ， 。 ，2<=N<=15。
n 의 이 범 위 를 보면 많은 경우 에 상 압 입 니 다. 모든 가능 한 노선 이 모두 있 기 때 문 입 니 다 (n - 1)!종, 이 건 값 이 너무 커 요.상 압 은 상 태 를 하나의 정수 로 압축 한 후에 이 정수 로 상 태 를 표시 하 는 것 이다.가방 에 있 는 바 이 너 리 최적화 처럼 모든 요소 의 선택 과 선택 하지 않 는 것 이 바 이 너 리 에 대응 합 니 다.
먼저, 우 리 는 상 태 를 설계 하려 고 합 니 다. 현재 방문 한 정점 의 집합 이 S 라 고 가정 하고 현재 있 는 정점 은 v 이 며, dp [S] [v] 로 v 에서 출발 하여 남 은 모든 정점 을 방문 하고 마지막 으로 정점 0 으로 돌아 가 는 경로 의 총 과 최소 값 을 표시 합 니 다.v 에서 출발 하여 아직 방문 하지 않 은 정점 까지 갈 수 있 습 니 다. 경 계 는 모든 정점 을 방문 하고 정점 0 으로 돌아 가 는 것 입 니 다.전달 식 을 보기 전에 지식 을 알 아야 하 는데......................................................
일부 집합 은 빈 집합 을 나타 낸다.S 와 T 의 집합 S * 8746 ° T – > S | T 집합 S 와 T 의 집합 S ∩ T – > S & T
이상 의 지식 이 있 으 면 전달 식 은 이해 하기 쉽다.전달 식 은 dp [V] [0] = 0 이다.(경계) dp [S] [v] = min {dp [S ∪ {u}] [u] + d [u] [v] | u 는 S} 에 속 하지 않 습 니 다.
ok, 상 code (^ ^) 우선 우 리 는 전달 식 으로 기억 화 검색 을 쓸 수 있 습 니 다.
int rec(int S,int v)
{
if(dp[S][v]>=0)
return dp[S][v];
if(S==(1<1&&v==0) //
return dp[S][v] = 0;
int res = inf;
for(int u = 0; u < n; ++u)
if(!(S>>u&1)) // u S
// u
res = min(res,rec(S|1<return dp[S][v] = res; //
}
void solve()
{
memset(dp,-1,sizeof(dp));
printf("%d
", rec(n,0));
}
그러나 이 문제 에서 임의의 두 정수 i 와 j 에 대해 그들 이 대응 하 는 집합 이 S (i) 를 S (j) 에 포함 시 키 면 i < = j 가 있 기 때문에 우 리 는 순환 방식 으로 쓸 수 있다.
void solve()
{
for(int S = 0; S < 1<//
}
dp[(1<0] = 0; //
//
for(int S = (1<2; S >= 0; ++S){
for(int v = 0; v < n; ++v){
for(int u = 0; u < n; ++u){
if(!(S>>u&1)){ // u S
dp[S][v] = min(dp[S][v],dp[S|1<printf("%d
",dp[0][0]);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
