PACMAN : 모든 점을 먹는 짧은 경로

Question

큰 미로에서 모든 점을 먹는 짧은 경로 (가장 짧지는 않지만 좋은 경로는 아님)를 찾는 PACMAN 문제에 대한 해결책을 찾으려고합니다. TSP, Dijsktra, BFS, A *에 대해 많은 사람들이 이야기하는 것을 보았습니다. 나는 내가 시작한 곳으로 돌아갈 필요가 없기 때문에 이것은 TSP라고 생각하지 않는다. 원한다면 나는 노드를 반복 할 수있다. 그리고 Dijsktra, BFS 및 A *가 가장 짧은 경로를 찾고 있지 않기 때문에 도움이 될 것이라고 생각하지 않습니다. 그렇다고해도 합리적인 시간에 답변을 제공하지 못합니다.

아무도 내게이 힌트를 줄 수 있습니까? 어떤 종류의 문제입니까? 이것이 TSP입니까? 어떤 종류의 알고리즘이 효율적인 방법으로이 문제에 접근합니까? 구현에 대한 힌트를 주시면 감사하겠습니다.

Answer 1

30 초 이내에 큰 미로에서 최단 경로를 찾은 경연 대회를하려고합니까?

나는 작년에 실제로 재미로했다 (대학 시절은 경연을하지 않았다). 몇 주 동안 연구 끝에 30 초 이내에 미로에 대한 정확한 해결책을 제시 할 수있었습니다.

내가 사용한 경험적 방법은 실제로 정확한 경험적 방법이었습니다. 나는 그래프 분해와 동적 프로그래밍에 기반을 둔 훨씬 더 효율적인 알고리즘을 사용하여 최소한의 경로 길이를 찾도록 코드를 작성한 다음 그 결과를 '경험적'값으로 A *에 다시 입력했습니다.

그래프의 크기가 매우 크지 만 (273 노드), 조각 너비가 낮기 때문에 (5), 고정 매개 변수 추적 알고리즘을 사용하여 효율적으로 해결할 수 있습니다.

바라 건데 그것은 올바른 길을 잡기에 충분한 키워드입니다.

는 업데이트 :I wrote a blog post explaining the solution