LSGame Algorithm Performance

LS-Game의 해법 중 가장 단순한 것은 특정 상태를 기억했다가 S 인 cell 을 모두 누르면 된다는 것인데, 이 방법은 최적화를 필요로 한다. 만일 최초의 상태에서 한 번만 눌렀다면, 그 해는 역시 한 번이 되어야 하는 것이다. 이런 최적화를 하기 위해 두 가지 방법을 찾아 냈는데, 그 두 가지 최적화 사용 여부에 따른 성능을 아래 표에 정리하였다. 숫자는 Board 를 N 번 눌러서 섞었을 때 몇 번만에 문제를 푸는가를, 수만 번 실행시킨 평균으로 표시한 것이다.

많이 섞었을 때는 두 방법을 사용하는 것이 비슷한 효율을 보였지만, 한 번만 섞었을 때는 첫번째 방법이, 두 번만 섞었을 때는 두번째 방법이 월등한 성능을 보여 주었다. 섞은 수에 관계 없이, 두 방법을 모두 적용한 것이 가장 나았다.

N of Scrambles	No optimization	`optimize1()`	`optimize2()`	`optimize1()` & `optimize2()`
100	12.52	7.17	7.13	6.74
10	12.51	6.99	6.98	6.61
5	12.50	6.14	6.41	5.73
4	12.41	5.26	5.44	4.73
3	12.25	5.03	6.83	4.84
2	11.51	3.86	1.92	1.92
1	9.00	1.00	7.00	1.00

Back to: GyonG이의 Programming-Languages 홈페이지로 가기

GyonG 이의 홈페이지로 가기