글 읽기 - tsp알고리즘 어디서 틀렸는지 조언 부탁드립니다!

barcelonamessi 7년 전 0

저는 탐색 하면서

D[i][j] = i에서 경로 j로 갈때의 최소값

라는 정보를 중심으로 탐색을 하였는데요

dfs함수에서는 현재부터 경로 path를 갈때 최소값을 찾는것입니다.

이 과정에서 d[i][j]라는 정보를 얻게 되는데 이 다음 탐색 에서 d[i][j]가 생기면

탐색을 하지 않고 이값을 가져옵니다. 또한 모든 점을 방문하였을때는 그 지점에서 시작지점으로돌아오는 값을 더해주었습니다.

또한 탐색 과정에서는 경로를 보면서 방문을할 수 있는지 파악하고, 방문할 수 있다면 경로를 업데이트하고 진행을 해주었습니다.

어디서 오류가 있었을 까요??

#include <iostream>
#include <stdio.h>
using namespace std;
int map[17][17];
int D[17][1<<17];

int dfs(int cur, int N, int move_sum, int path){
	if(move_sum==N-1){
		return map[cur][1];
	}
	
	
	if(D[cur][path]!=0)
		return D[cur][path];
		
	int result=1000000000;
	
	for(int i=1;i<=N; i++){
		///printf("cur = %d , path= %d , 1<<(i-1) = %d, path&(1<<(i-1))= %d\n", cur,path,1<<(i-1), path&(1<<(i-1)));
		//printf("path&(1<<(i-1)) = %d, (1<<(i-1)) = %d\n", path&(1<<(i-1)), 1<<(i-1) );
		if((path&(1<<(i-1)))==(1<<(i-1))){ //가도된다면
			//printf("gogo\n");
			int next_path=path& (~(1<<(i-1)));
			//printf("next_path= %d\n", next_path);
			int temp=map[cur][i]+dfs(i, N, move_sum+1, next_path);
			if(temp<result){
				result=temp;
			}
		}
		
	}
	D[cur][path]=result;
	
	return	result;
	
	
}
int main() {
	int N;
	scanf("%d", &N);
	int result=1000000000;
	int path=0;
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++){
			scanf("%d", &map[i][j]);
		}
	}
	for(int i=1; i<=N; i++)
		path|=(1<<(i-1));
	
	path-=1;
	result=dfs(1, N, 0, path);
	printf("%d\n", result);
	return 0;
}

barcelonamessi 7년 전 1

점a에서 점 b까지방문 안하는 경우도있었는데 그것을 빼먹었습니다. ㅜㅜ

이 경우를 관리해주었더니 해결되었네요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

tsp알고리즘 어디서 틀렸는지 조언 부탁드립니다!

barcelonamessi 7년 전 0

barcelonamessi 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말