알고리즘24 State Space

수업 때 배운 이야기 70,80%를 평소에 알고있어야한다,, 찔린다

 

 

빈공간과 상하좌우를 스와이프하는 퍼즐!

퍼즐을 부셔서 넣었을 때, 왼쪽 -> 오른쪽 상태로 맞출 수 있는가?

* 안되는 경우가 있다 *

 

 

 

한 그룹은 solve가능한 상태 /  한 그룹은 불가능한 상태

 

뽑아서 아무거나 두개를 바꾼다. => 못 푼다.

옆에 것도 뽑아서 바꾸면 => 다시 풀 수 있는 상태

 

하나의 판은 각각의 노드이고 두개를 연결하는 엣지가 있다.

(빈 칸에 인접한 칸이 3개이므로 엣지 3개)

 

16!은 생각보다 큰 숫자

다 그려서 알아낸 건 아니다.

 

 

16개짜리 수열로 나타내자 (빈칸 = 16)

 

number of inversion을 정의한다.

각각 뒤집어진 것의 갯수(자신보다 오른쪽 중 자신보다 작은 수의 갯수)를 구해서 모두 더하자

 

완성해야 하는 퍼즐은 number of inversion이 0이다.

 

parity란? number of inversion이 홀수냐 짝수냐

 

 

distance란? 맨끝(12)에서 빈칸(16)까지의 거리

전체 parity = parity + distance가 홀수인지 짝수인지!

 

 

 

3과 16을 바꾸면 num of inversion이 1 줄거나 1 늘어난다.

distance도 1 줄거나 1 늘어난다. 

=> 결국 total parity는 바뀌지 않는다

 

 

 

4하고 16이 바뀌면 중간의 8,1,11까지 바뀐다.

4칸 떨어져 있는 자리끼리 바뀌었을 때 무조건 inversion 7이 바뀐다

 

거리도 1 바뀌었다.

=> 결국 total parity는 바뀌지 않는다

 

 

 

* 결국 위 그림에서 1,2를 바꾸면 num of inversion은 바뀌지만

16의 위치는 그대로이므로 parity가 바뀐다! 

=> 정상적인 move가 아니다.

 

여기서 증명한 것은 짝수인 경우에 풀 수 있다가 아니라 홀수인 경우엔 못푼다는 것

(일단 절반을 걸러냄!)

 

 

트리를 키워가면서 문제를 풀 것이다.

끝까지 키우는 것이 아니라 답이 없다는 것이 보장이 되면 잘라버린다.

 

목표: A에서 부분집합을 골라내서 합이 S가 되게 한다.

2^n가지 중에 S가 있냐!

pseudopolynomial는 값이 커지면 안된다.

pseudopolynomial은 S의 값을 써놓고 푸는 것.  

 

search space의 크기는 2^n가지

노드를 만들어놓고 하는 것이 아니라 트리를 만들어가면서 한다!

 

 

트리처럼 노드를 만들어 나간다.

어느 노드의 child를 만들 것인지 작전을 짜야 한다.

그림은 BFS지만 (넓게)

DFS처럼 만드는 법도 있다. (길게)

 

 

한 쪽은 선택하고 한쪽은 버렸다는 의미

 

 

끝까지 다 그리면 leaf node는 a(i)중 모두 선택을 한 결과.

이 중에 S가 있는가? 

(물론 다 만들거면 위에꺼를 그릴 필요가 없음. 다 안 만들거임 cut off!)

 

 

a1선택해서

sum이 1000이라면 child는 1000이하가 없다.

근데 s가 100이라면? 이 밑은 더 이상 만들 필요가 없다!

 

물론 극단적인 경우만 줄어들지만 어쨌든 줄일 수 있다.

 

 

 

 

S=100

다는 못버리지만 a1+a2=110이므로 이 밑은 다 버릴 수 있다.

 

입력에 따라 성능이 크게 좌우될 것이고

어떤 입력에 따라 어떤 성능이라고 얘기하는 것이 쉬운 일이 아니다.

어쩔 수 없이 이렇게라도 한다.

 

C는 현재노드의 합

C가 S보다 크면 cut off를 할 수 있다.

 

레벨 i번째까지 선택을 했다.

a(i+1)부터 a(n)까지 선택할 수 있는데

다 합쳐도 S보다 작다면 cut off. 이정도.