A * 알고리즘의 노드 간 비용 거리에 대한 비율 조정

Question

노드 노드 관련 비용 모음 인 데이터가 있습니다. 이 비용은 거리로 표현됩니다.

또한 각 노드마다 x-y 좌표가 있습니다. 이제 A * 알고리즘에서 노드에서 노드로 비용을 추가하고 중간 노드에서 목적지까지의 휴리스틱 비용을 추가해야합니다. 그러나이 두 값은 동일한 메트릭/단위를 가져야합니다. 하나는 피트로, 다른 하나는 좌표 거리로 가질 수 없습니다.

이 작업을 수행하기 위해서는 우선 피트에서 x-y 좌표 거리로 비용을 확장하는 배율 인수를 찾아야한다는 것을 알고 있습니다. 권리? 제가 말할 수있는 것은이 모든 비용이 확장 가능하다는 것입니다. 따라서이 베타 값은 노드 노드의 모든 쌍에 대해 동일합니다. 질문은 어떻게이 값을 찾을 수 있습니까?

내가 지금 한 것은 node - node 간의 좌표 거리를 구한 다음 비용을 피트 단위로 비교하는 것입니다. 따라서 베타 버전을 찾을 수 있습니다.이 버전은 상수이며 모든 노드 노드 비용 (피트)에 대해 작동해야합니다 ... 이것이 사실인지 확실하지 않습니다. 나는 여기서 마술 트릭을 찾고 있지 않다. 이것을 해결할 수있는 간단한 방법/수학.

Answer 1

보통 우리는 그리드가 스케일 팩터에서 물리적 세계를 모델링하고 있다는 것을 알고있다. 너 이미 그걸 몰라?

어쨌든 나는 당신의 직감이 옳다고 생각합니다. 즉, 실제 비용을 피트로 알고 두 점 사이의 좌표 거리를 계산하고 하나를 다른 숫자로 나눠서 배율 인수로 계산하십시오. 물론 "비용"은 두 노드 간의 직선 거리라고 가정합니다.

즉 node1과 node2 사이의 거리가 3 피트이고 노드 좌표가 각각 [0,0]과 [0,9] 인 경우 "배율 인수"는 3/9 ... 또는 9/3이며, 전환을 원하는 방식에 따라

이 경우 좌표 거리의 한 단위는 1/3 피트입니다. 또는 한 발은 좌표 거리가 3 단위입니다. 좌표에서 발로 가려면 3으로 나눕니다. 발에서 좌표로 이동하려면 3을 곱합니다.