형들 외판원문제 있잖아

[알려줭(114.201)]

외판원문제를 균일비용으로 풀이하면 결국 풀리긴 풀리지않아?

내친구들은 뭐 다 close list에 다 들어가서 실패로 끝난다..라고 말하던데

왜그런거야?

[ㅁㄴㅇㄹ(110.9)]

일단 잘못생각하고있는게, 외판원문제도 풀리긴 풀림. 단 몇년이걸릴지 몇십년이 걸릴지 몰라서 문제지

[ㅁㄴㅇㄹ(110.9)]

이런 외판원같은 NP문제는 보통 그리디하게 풀어서 완벽한 정답이아닌 근소한 차이의 정답을뽑아내는 문제고

[ㅁㄴㅇㄹ(110.9)]

니가 말하는 균일비용이란건 각 정점간의 가중치를말하는거??

[글쓴이(114.201)]

F = 초기노드에서의 거리 + 다음 노드까지의 거리 이 값으로 푸는건데 일단 다시 생각해보니까 도시들이 죄다 서로 연결되있기 때문에 죄다 close리스트에 들어가긴 하더라...

[ㅁㄴㅇㄹ(110.9)]

도시수가 작으면 순열이나 dfs로도 풀수있는데 아마 크기가 7이상이면 조오오오온나게 느렸던거같다