A-Star 알고리즘 세부 정보

A * 알고리즘을 시작했지만 어떻게 작동하는지 알지 못합니다.A-Star 알고리즘 세부 정보

예 I 그래프를 그리고있다 :

A -> B = 9 (되지 90 원래 잘못 요청)

A -> C = 20

C -> D = 40

이제 A부터 시작하여 언급 된 경로를 사용하여 D로 가고 싶습니다.

이 경험적 방법을 사용하는 경우 : h (n) = D 방향으로의 거리 D B와 D 사이의 직선 거리는 2이지만 B와 D 사이의 경로는 없습니다.

내가 알고 싶은 것입니다 :

은 B와 D (목표)

또는 사이에 경로가 없기 때문에 A * 알고리즘은 첫 번째 (B로 이동 한 후 다시 A로 돌아합니까 내 휴리스틱 기능은? 허용하지

출처

2013-03-29 Dilon Duuuman

여기에 귀하의 질문이 확실하지 않은 경우 : A *는 0 점으로 A에서 시작하여 B 점을 찾아 90 점을 얻은 다음 C를 찾아 20 점을 지정합니다. A가 닫히고 B와 C가 "열린다". C는 열린 노드 중 가장 낮은 점수를 가지므로 거기에갑니다. 이제는 D를 찾고 중지합니다. 이것이 종말점 이었기 때문입니다. – Dave

좀 더 흥미로운 예에서, B는 C보다 점수가 낮을 것이므로 B로 갈 것입니다. 링크를 찾을 수 없으므로 (새로운 노드를 추가하지 않음) B를 닫습니다. 이제 C 만 열립니다. 그것은 거기에 간다. 나머지는 이전과 같습니다. – Dave

글쎄, 당신은 당신의 기능에 대한 자세한 내용을 알려 주어야한다 (그러나 i'v은 교과서에서 볼 수, 그것은 괜찮습니다).

는 일반적으로 A * 경로를 반환해야합니다, 말하기, 존재하는 경우 존재하지 않는 경로를 무한 비용 또는 "멈춤 - 여기"표시처럼. 대상에 도달하지 않고 경로의 끝에 도달하면 다른 가능성으로 이전 노드로 롤백합니다. 첫 번째 질문에 대한 대답은 '예'입니다.

출처

2013-03-29 23:07:26

아, 첫 줄, A -> B는 9 여야하고 그 점에 대해 미안합니다 ..... –

A-Star 알고리즘 세부 정보

답변

관련 문제