8퍼즐에 휴리스틱 알고리즘을 적용하고 있습니다.
글쓴이: 고양이를부탁해 / 작성시간: 월, 2009/05/25 - 6:14오후
안녕하세요 KLDP 식구여러분들...
8퍼즐의 평가값을 계산하는 부분에 Manhattan Distance와 Miplaced Tiles 방법을 적용하고 있습니다.
그런데 실행시켜보면(초기퍼즐값에 따라 다르지만)
1000개 이상의 노드와 상당한 시간이 걸리는 경우가 많더라구요
교수님께서는 이렇게 나올 수가 없다고 하시던데
다른 분이 짠 프로그램을 돌려봐도 1000개 이상 나오는 경우가 허다하던데...
혹시 경험있으신 분 있다면
답변좀 부탁드립니다 ^^;;
Forums:
좀더 자세히 설명 부탁.
8 puzzle 이 뭐죠? Sam Loyd 의 slide puzzle 인가요?
8퍼즐은..
예를 들어 아래의 퍼즐을 시작퍼즐이라고 하면
0 8 7
6 5 4
3 2 1
다음과 같은 목표 퍼즐로 탐색하는 기법을 적용하고 있습니다.
1 2 3
4 5 6
7 8
좀 더 빠른 탐색을 위해 인공지능적인 기법을 사용하는 프로그램입니다
어떤 노드로 탐색을 진행해야 시행착오를 덜 하면서 빠르게
목표노드를 찾을 지 판단하는데 사용하는게 휴리스틱입니다.
제가 제대로 설명했는지 걱정이네요.
감사드립니다^^
------------
힘들면 즐겁다.
------------
힘들면 즐겁다.
평가 자체에 1000개
평가 자체에 1000개 이상의 노드가 생성된다는 뜻인가요? 그건 아닌 것 같고..
분기 이후 각 state를 노드라고 한 것이라면...
휴리스틱 알고리즘 안넣고 greedy하게 모든 분기점을 가면 1000개는 물론 넘겠지요. (cycle이 생길수도 있고 -_-; )
그러므로 평가값이나 추세를 보고 적당히 자르는 휴리스틱 알고리즘이 있는겁니다.
이거 굳이 heuristic algorithm 이 필요한가요?
9! 해봐야 얼마 안 나오는데. BFS로 다 찾아보는 것도 가능할 듯.
고작해봐야 4만개의 노드도 검사하지 않는데 말이죠.
실제 찾아볼 수 있는 노드는 그 반인 2만개도 안 됩니다.
예전에 5*5 puzzle을 해본 경험이 있는데 3*3은 별로 안 걸릴 것 같은데요.
방문노드가 1000개를 넘지 말아야 한다는 것이 규정이라면 이해합니다만 시간문제는 이해가 안 갑니다.
교수님이 감이 없으신 것 같네요
(perfect) heuristic 사용한 A* 이죠?
저도 해본지 오래 되어서 기억은 잘 안납니다만
1000 개 expansion 하는 건 정상적인 게 아닌가 싶네요.
희미한 기억으론 manhattan distance 를 heuristic 으로 사용시 10000 개 이상 node 를 생성하게 되는 경우도 있던 것 같군요.
8-puzzle 류는 문제의 간단함에 비해 search complexity 가 비약적으로 증가하는 대표적인 문제 중 하나입니다.
댓글 달기