2D 그리드 (배열)로 이동하기위한 로봇의 최소 비용 계산/표시

Question

현재 로봇 (위치 x, y)의 이동 비용을 계산하는 할당 질문을하고 있습니다.

몇 가지 장애물 (기호 ##)이있는 2D 그리드 (2 차원 배열)의 크기가 제공됩니다. 다음은 샘플 그리드입니다. 우리는 또한 로봇의 시작 위치를 제공받습니다. 현재 위치에는 '비용'이 00 (고정)입니다. 할당에 필요한 것은 무엇

.................................................. ........................................##........ ........................................##........ ........................................##........ ..........######################################.. ........................................##........ ........................................##........ ........................................##........ ....################..........00........##........ ....################....................##........ ....################....................##........ ....################....................##........ ........................................##........ .................................................. ..................................................

알 수없는 각 그리드 (..)의 비용을 계산하는 것입니다 그래서 로봇이 해당 위치로 이동하기 위해 확인해야하는 비용을 보여줍니다.

가로 이동은 이전 그리드의 비용에 +2입니다.
대각선 이동 +3 이전 그리드 비용.
로봇은 장애물을 넘을 수 없으며 주위를지나 가야합니다.
각 값은 최소 비용을 가져야합니다 (예 : 수평 및 수직보다 대각선으로 이동하는 데 드는 비용 절감). 지금 내가 문제가 시각화가 있어요

http://i.stack.imgur.com/JiDl1.png

/태클 : 아래

는 (더 읽을 수 있도록 일부 값이 생략에만 비용의 마지막 두 자리 숫자를 표시하는) 우리가해야 결과입니다 문제. 우리는 '거품 정렬 알고리즘과 도덕적으로 유사합니다'라는 새로운 최소 비용이 발견 될 때마다 모든 것이 다시 계산된다는 말을 들었습니다.

사과이 몹시 혼란 경우, 어떤 제안은

Answer 1

이럴 노드의 연결된 네트워크로이다 (그래프) 경로 문제를 시각화하는 가장 쉬운 방법, 이웃 (코드 또는 의사가 크게 될 환영) 노드 (로봇이 현재 위치에서 움직일 수있는 정사각형)는 무게가있는 모서리 (무게는 노드 사이의 이동 비용 임)로 서로 연결됩니다.

N  @  N -2- N -2- N 
|\   /|\ /| /
2 3  3 2 3 2 3 
| \/ |/ \|/ 
N -2- N -2- N -2- N  @ 

N = 노드, 숫자 및 선 가중치와 가장자리이며, @는 더 많은 옵션을 예를 http://en.wikipedia.org/wiki/Shortest_path_problem에 대한 참조를 위해

Djikstra's algorithm이 제안 이미 장애물을합니다. Binary min heap은 우선 순위 큐로 작동합니다. (afaik, A * + 바이너리 미니 힙은 속도 때문에 실시간 게임에서 많이 사용됩니다).

편집 : 이전에 A *를 제안했지만 생각해 보니 단일 소스 최단 경로에 대해서는 작동하지 않습니다.