a,b,c,d,e,f,g,h 이렇게 노드가 있는데 a에서 출발해서 b,c,d,e,f,g를 순서상관없이 전부 한번씩만 경유해서 최단경로로 h까지 가야함.
근데 이거 최소경로랑 비슷한거 같으면서도 좀 성질이 다른문제 아님?
다익스트라는 그래프상에서 중간에 뭘 경유하든 출발지에서 목적지까지 최소경로 아닌가?
근데 어렴풋이 다익스트라로 되겠거니 생각하고 있다가 진지하게 생각해보니까 모르겠다. 내가 바본가? 이거 다익스트라로 가능?
밑에 samchon처럼 나도 이거 a-h사이 모든 가능한 경로 다구해서 해야하나 생각하고있었는데 혹시 간단한 방법이 있나 해서 생각난김에 물어봄.
이런 비슷한문제 많이본거같았는데 정작 생각해보니까 모르겠네
그건 한붓그리기 문제임.
ㄴ맞다 한붓그리기! 내가 뭔가 딱 저거에 해당되는게 있었던거 같은데 기억이 안났음 ㄳ
약간 다르네 오일러패스는 edge를 한번씩만 쓰는거고 내가말한건 해밀턴패스네. 어쨋든 감사 새로운걸 알게됨ㅋㅋ
나도 아닌 거 같아서 찾아 봤는데, 한붓그리기(오일러 경로)랑 해밀턴 경로 둘 다 아니지. 해밀턴 경로도 시작과 끝은 전혀 상관 없고 그저 모든 점을 지나는 경로가 있나? 에만 주목한 거니...
TSP가 NP-Hard니까 그런 비슷한 류의 문제는 경우의 수를 다 체크해야 풀리는게 아닌지 의심해보는게 좋을듯
125.128/나도 대충 설명만보고 이거네 했다가 지금 다시 멘붕옴 결국 모든경우를 다체크해야하나...
58.239/땡큐 이거 처음 들었을때 엄청 간단하게 풀줄알았는데 아니라서 뭔가 찝찝하네
ㅇㅇ. 모든 경우를 체크하는 게 유일한 해임. 해밀턴 경로는 NP-완전(NP-complete) 문제라고 알려져 있고, 너의 문제는 시작점과 출발점을 그래프 상에서 지워버리면 해밀턴 경로 문제와 같아짐.
아 오타. 시작점과 출발점이 아니라 출발점과 도착점.
만약에 해밀턴 경로에 대한 효율적인 알고리즘을 찾아내면 넌 노벨상 탄다. P=NP 문제를 증명한 꼴이 되어서 밀레니엄 문제를 풀게 된 거고 수학계 역사에서도 길이 남을 거야.
노벨상이 아니라 튜링상이겠군.
125.128/그지? 해밀턴경로 다찾아서 출발점이랑 시작점 사이에서 최단경로인거 찾아야되는듯
ㅋㅋㅋㅋㅋㅋㅋ개간단한줄 알았는데 하다보니까 안간단해서 빡친다
ㅇㅇ 해밀턴 경로 찾는 게 NP-완전 문제이고, NP-완전 문제는 효율적인 알고리즘을 찾을 경우 P=NP 문제를 해결하게 됨. 왜냐하면 모든 NP 문제는 하나의 NP-완전 문제로 모두 고칠 수 있거든. P=NP이냐, P≠NP이냐를 가지고 밀레니엄 수학 7대 난제 중 하나가 바로 그거고 아직까지 안 풀렸는데 해밀턴 경로 알고리즘을 찾은 순간 그 문제는 같다는 걸로 결론나고 해결됨.
나도 출발점이랑 시작점이라고 썼네
해밀턴 경로에 한해서는 아주 극히 일부의 제한 조건만이 밝혀졌을 뿐, 구체적인 판별 알고리즘에 대해서는 전혀 나온 게 없어.