길찾기에 사용되는 프로그래밍 알고리즘이 어떤 것이 있나요?

Question

안녕하세요.

예전에는 길찾기 알고리즘으로 A*(에이스타)를 많이 사용한 것으로 기억이 나는데요.

요즘은 인공지능과 알파고가 대두되면서 여러가지 알고리즘과 프로그래밍 방법이 나온 것으로 알고 있습니다.

요새는 어떤 방법으로 구현하는 지 간략하게 설명 부탁 드립니다.

Answer 1

될 수 있다. 하지만 가장 많이 사용되는 것은 A* 알고리즘일 것이다. 그래서 pathfinding의 경우 A* 알고리즘을 알아보려고 한다.

2. A* 알고리즘은 항상 f, h, g 값으로 이루어져있다. 그래서 각 노드에 f, h, g 값을 넣어서 계산을 한다. pathfinding의 경우 h값은 현재 노드에서부터 목적지까지 장애물이 없다는 가정하에 최단거리를 이용한다. g 값은 당연히 현재까지의 거리이다. f 값은 g 값과 h 값의 합이다. 참고로 원래 A*에는 일반적으로 이미 방문한 곳을 관리하는 Visited Queue가 존재한다. 근데 Queue를 관리하는 것이 메모리도 많이 잡아먹고, 시간도 오래걸린다. 그래서 pathfinding에서는 각 노드의 state를 open, visited(closed), blocked로 따로 관리했다. 내가 언어능력이 부족해서 설명이 잘 안된다. 그래서 그냥 동영상 링크로 대체한다.

https://www.youtube.com/watch?v=-L-WgKMFuhE

출처 http://blog.naver.com/PostView.nhn?blogId=zzing0907&logNo=220671022815