Traveling Salesman Problem S노드 부터 시작해서 S노드로 되돌아오는 최소 경로 각 노드는 한번만 방문 가능 엣지 웨이트 존재. (최소합) NP-Complete HTML 삽입 미리보기할 수 없는 소스 state tree를 이렇게 구성하자 루트는 시작 노드 s 차일드는 연결된 노드들 (일단 s까지 계속 연결되는 모든 노드들을 구성하자.) 어떻게 cut off 할 수 있을까? 1. 노드는 한번만 방문해야 하므로 만약 a노드의 자손들에서 다시 a노드가 나온다면 cut off 한다. 2. DFS를 한다치면 왼쪽 자손들 부터 값을 계산해나간다. 일단 a 자손들에서의 답 A를 찾았다고 치자. 그러면 나머지 b 자손들 부터의 답 B는 A보다 작아야지만 의미가 있다. 따라서 자손들을 순회하면서 계산..

15 Puzzle 빈칸대로 순서대로 옮기면서 오름차순으로 나열하기 영원히 못맞추는 모양이 있다!! 아무거나 두개 빼고 둘의 위치 교체해서 다시 넣으면 영원히 못맞춘다. 칸을 움직이면서 나올 수 있는 상태를 노드 하나로 치면 노드의 총 개수는 16! 이때 다음 상태로 한번에 갈 수 있는경우 엣지로 연결된다. ⇒ 16!은 너무 많으므로 다익스트라 불가능 2개의 connected component 가 생긴다. 그리고 두개 빼고 둘의 위치 교체해서 넣으면 그 전이랑 다른 컴포넌트에 무조건 들어가게 된다. ⇒ 답이 이전 컴포넌트에 있었다면 서로 연결 안되서 영원히 못맞춘다. 모든 노드에서 Parity of Permutation plus Parity of Distance of 16 from Corner 를 계산한다..