State Space - 15 Puzzle, Subset Sum Problem

15 Puzzle

• 빈칸대로 순서대로 옮기면서 오름차순으로 나열하기
• 영원히 못맞추는 모양이 있다!!
  아무거나 두개 빼고 둘의 위치 교체해서 다시 넣으면 영원히 못맞춘다.

칸을 움직이면서 나올 수 있는 상태를 노드 하나로 치면
노드의 총 개수는 16!
이때 다음 상태로 한번에 갈 수 있는경우 엣지로 연결된다.
⇒ 16!은 너무 많으므로 다익스트라 불가능 2개의 connected component 가 생긴다.

그리고 두개 빼고 둘의 위치 교체해서 넣으면 그 전이랑 다른 컴포넌트에 무조건 들어가게 된다.
⇒ 답이 이전 컴포넌트에 있었다면 서로 연결 안되서 영원히 못맞춘다.

모든 노드에서 Parity of Permutation plus Parity of Distance of 16 from Corner 를 계산한다.
== 1 이면 못푼다.
== 0 이면 풀수 있다.

다익스트라를 사용하기 위해 노드를 일부만 만들자.
칸 1~8개는 그리디로 풀다가
칸 9~15개는 노드 생성해서 다익스트라로 풀자.

---

Subset Sum Problem

• A = {a1, a2, …, an} 의 원소들을 뽑고 더해서 S 만들기
• NP-Complete
• 동전 문제

flowchart TD t0((시작))---t2((a1 O)) t2---t4((a2 O)) t2---t5((a2 X)) t0---t1((a1 X)) t1---c1((a2 O)) t1---t3((a2 X))

 

state tree를 이렇게 구성하자
루트는 시작상태 (아무것도 고르지 않은 상태)

왼쪽 차일드는 a1을 고른 상태
오른쪽 차일드는 a1을 고르지 않은 상태

어떻게 cutoff(필요 없는 부분 잘라내서 최적화)할 수 있을까?
1. 현재 노드까지의 합 + 나머지 남은 a들의 합 < S 이면 cutoff 한다.
2. 현재 노드까지의 합 > S 이면 cutoff 한다.