반응형
이건 전공과목 숙제에 관한 제 잡설입니다.
나중에 까먹지 않기 위해 적어두는거니
읽지 않으셔도 됩니다. ㅡㅡ;
슬라이딩 퍼즐은 기본적으로 state들로 볼 수 있다.
15-puzzle의 경우엔 총 16!개의 state가 존재하고
그 state들이 서로 얽히고 섥히도록 transition이 존재한다.
초기의 생각은 그런 state들을 그룹지어서..
각 transition에게 특성을 부여하는거였는데..
워낙 광범위하고, 정의하기가 어려워서 포기했다.
그러던 중 IDA* 알고리즘을 발견하게 됐고,
트리 형태로 구현하는 방법을 생각하게 됐다.
16!개의 state로 생각하지 말고...
현재의 state를 root로 두고...
모든 state는 child를 4개(4방향으로 움직일 수 있음, 실제론 3개-왔던방향으로 돌아가는건 의미없으므로)씩 갖고 있는 node라고 생각하면...
무한히 뻗어나갈 수 있는 트리를 생각할 수 있다.
이렇게 되면 transition은 아주 일반적인 것이 되므로..
각 node를 특성화 시키는게 필요한데
가장 간단한것이 node마다 어떤 숫자를 부여하는 것이다.
GOAL state로 부터 얼마나 떨어져있나 하는 숫자.
이때 쓴것은 Manhattan Distance 라고...
간단히 말해 |x1-x2| + |y1-y2| 를 구하는 것이다.
현재 15개의 cell에 대해 MD들을 다 합하면(empty cell 제외)
일정한 값이 되고 이 값이 각 state를 구분짓는 기준이 된다.
또한, 현재 state의 MD의 합은 곧 optimal solution의 move수의 lower bound가 된다.
(한번의 move에 반드시 하나의 cell이 empty cell과 바뀌므로)
이제 tree를 타고 내려가면서 검색을 시작한다.
tree라고 해서 직접 구현하는것이 아니라
recursive function을 통해 간단히 구현한다.
empty cell이 이동 가능한 지점들을 차례로 방문하면서
만약 그 지점으로 이동했을경우 MD+depth가 구해놓은 lower bound보다 작거나 같다면 제대로 찾아온 것이므로 검색을 계속한다(recursive call).
크다면 잘못 온것이므로 false를 return하면서 이동한것을 원래대로 복귀시킨다.
이렇게 검색을 하다가 MD = 0 이 되고 현재 node의 tree depth가 lower bound랑 같다면 해를 구한 것이 된다. 이 때는 true를 return하면서 구했던 solution을 저장한다.
만약 lower bound에 해당하는 모든 solution을 검색했으나 딱 떨어지는 solution이 없을 경우엔 lower bound를 2만큼 증가시켜 다시 검색을 시도한다.
(bound를 1 증가시키는건 의미가 없다.)
이번 숙제는 3차원 63-puzzle 이였는데
간단한 확장으로 어렵지 않게 구현이 가능하다.
구현에서는...
1. 어떤 숫자가 어떤 cell에 있을때의 MD들을 미리 다 구해서 table 형태로 저장해둔다. 매 node를 거칠때마다 MD를 계산하는 수고를 덜어서, 단지 읽어오기만 하면 된다.
2. 어떤 지점에서 움직임 가능한 지점은 총 6방향이 있는데(3차원에서) 방금 왔던 방향이나, 막혀있는 방향으로는 가면 안된다. 또, 선택한 방향으로 cell을 이동시킬경우 data를 처리하는데 있어서 어느 방향으로 이동했느냐에 따라 달라진다. 이 두가지를 한번에 해결하기 위한 방법을 고민했지만... 결국 한 방향에 대한 코드를 짜서 6배로 뻥튀기해서 구현했다. 다른 좋은 방법이 생각나지 않았다. ㅠ.ㅠ
3. 몇가지 교훈...
변수는 초기화 하자.
수정한 코드는 나중에 다시 한번 더 보자. 오타가 있다. ㅠ.ㅠ
공간상의 축에 대한 개념을 확실히 해놓고 시작하자.
등등...
한 3-4달만에 해보는 코딩이라... 낯설었는데
하다보니 금방 적응이 됐다.
이번엔 구상만 일주일을 했다. (물론 게을러서이기도 하고 ㅡㅡ;)
친구들은 코딩해서 결과물도 나오고 그러는데
속으로는 조바심도 나고 그랬지만..
참고 일단 구상부터 하자고 마음을 다잡았다.
그래서 90%정도 구상이 끝났을때 구현을 시작했고
일이 생각보다 빨리 진척됨을 느낄 수 있었다.
어느정도 나도 프로그래밍에 익숙해져 가나보다.
나중에 까먹지 않기 위해 적어두는거니
읽지 않으셔도 됩니다. ㅡㅡ;
슬라이딩 퍼즐은 기본적으로 state들로 볼 수 있다.
15-puzzle의 경우엔 총 16!개의 state가 존재하고
그 state들이 서로 얽히고 섥히도록 transition이 존재한다.
초기의 생각은 그런 state들을 그룹지어서..
각 transition에게 특성을 부여하는거였는데..
워낙 광범위하고, 정의하기가 어려워서 포기했다.
그러던 중 IDA* 알고리즘을 발견하게 됐고,
트리 형태로 구현하는 방법을 생각하게 됐다.
16!개의 state로 생각하지 말고...
현재의 state를 root로 두고...
모든 state는 child를 4개(4방향으로 움직일 수 있음, 실제론 3개-왔던방향으로 돌아가는건 의미없으므로)씩 갖고 있는 node라고 생각하면...
무한히 뻗어나갈 수 있는 트리를 생각할 수 있다.
이렇게 되면 transition은 아주 일반적인 것이 되므로..
각 node를 특성화 시키는게 필요한데
가장 간단한것이 node마다 어떤 숫자를 부여하는 것이다.
GOAL state로 부터 얼마나 떨어져있나 하는 숫자.
이때 쓴것은 Manhattan Distance 라고...
간단히 말해 |x1-x2| + |y1-y2| 를 구하는 것이다.
현재 15개의 cell에 대해 MD들을 다 합하면(empty cell 제외)
일정한 값이 되고 이 값이 각 state를 구분짓는 기준이 된다.
또한, 현재 state의 MD의 합은 곧 optimal solution의 move수의 lower bound가 된다.
(한번의 move에 반드시 하나의 cell이 empty cell과 바뀌므로)
이제 tree를 타고 내려가면서 검색을 시작한다.
tree라고 해서 직접 구현하는것이 아니라
recursive function을 통해 간단히 구현한다.
empty cell이 이동 가능한 지점들을 차례로 방문하면서
만약 그 지점으로 이동했을경우 MD+depth가 구해놓은 lower bound보다 작거나 같다면 제대로 찾아온 것이므로 검색을 계속한다(recursive call).
크다면 잘못 온것이므로 false를 return하면서 이동한것을 원래대로 복귀시킨다.
이렇게 검색을 하다가 MD = 0 이 되고 현재 node의 tree depth가 lower bound랑 같다면 해를 구한 것이 된다. 이 때는 true를 return하면서 구했던 solution을 저장한다.
만약 lower bound에 해당하는 모든 solution을 검색했으나 딱 떨어지는 solution이 없을 경우엔 lower bound를 2만큼 증가시켜 다시 검색을 시도한다.
(bound를 1 증가시키는건 의미가 없다.)
이번 숙제는 3차원 63-puzzle 이였는데
간단한 확장으로 어렵지 않게 구현이 가능하다.
구현에서는...
1. 어떤 숫자가 어떤 cell에 있을때의 MD들을 미리 다 구해서 table 형태로 저장해둔다. 매 node를 거칠때마다 MD를 계산하는 수고를 덜어서, 단지 읽어오기만 하면 된다.
2. 어떤 지점에서 움직임 가능한 지점은 총 6방향이 있는데(3차원에서) 방금 왔던 방향이나, 막혀있는 방향으로는 가면 안된다. 또, 선택한 방향으로 cell을 이동시킬경우 data를 처리하는데 있어서 어느 방향으로 이동했느냐에 따라 달라진다. 이 두가지를 한번에 해결하기 위한 방법을 고민했지만... 결국 한 방향에 대한 코드를 짜서 6배로 뻥튀기해서 구현했다. 다른 좋은 방법이 생각나지 않았다. ㅠ.ㅠ
3. 몇가지 교훈...
변수는 초기화 하자.
수정한 코드는 나중에 다시 한번 더 보자. 오타가 있다. ㅠ.ㅠ
공간상의 축에 대한 개념을 확실히 해놓고 시작하자.
등등...
한 3-4달만에 해보는 코딩이라... 낯설었는데
하다보니 금방 적응이 됐다.
이번엔 구상만 일주일을 했다. (물론 게을러서이기도 하고 ㅡㅡ;)
친구들은 코딩해서 결과물도 나오고 그러는데
속으로는 조바심도 나고 그랬지만..
참고 일단 구상부터 하자고 마음을 다잡았다.
그래서 90%정도 구상이 끝났을때 구현을 시작했고
일이 생각보다 빨리 진척됨을 느낄 수 있었다.
어느정도 나도 프로그래밍에 익숙해져 가나보다.
반응형