알고리즘 a*
~에
? 가능성이 유망한 지 아는 방법?
- 함수를 통해 f (x) = g (x) + h (x)
- 휴리스틱 기능입니다
- g (x)는 원점에서 x 노드에 도달하는 비용입니다.
- h (x)는 다음 노드의 비용을 추정하기위한 휴리스틱 기능입니다.
- 우리는 항상 트리를 확장 할 가능성을보고 f (x)의 값을 계산합니다.
- 우리는 우리가 찾은 것 중에서 가장 작은 f (x)를 가진 노드를 추가합니다.
- OA*는 그래프에서 최소한의 방법으로 가장 효율적인 알고리즘입니다.
- 그러나 심각한 제한이 있습니다
- 허용되는 H (x)를 정의해야합니다. x에서 y까지 실제 거리보다 큰 값을 반환하지 않습니다.
- H (x)가 허용되지만 실제 거리를 너무 과소 평가하면 알고리즘은 매우 비효율적입니다. H (x)가 허용되지 않으면 알고리즘에 최소한의 방법을 찾지 못할 수 있습니다.
? 복잡성
- 복잡성은 사용 된 기능 H (x)에 직접적으로 의존합니다.
- 최악의 경우, 탐색 된 노드의 양은 가장 작은 경로의 크기가 지수되지만 h * (x) −h (x) ≤O (logh * (x)) 인 경우 다항식 복잡성이 있습니다.
? 언제 사용하는 것이 좋습니까?
- 지도에서와 같이 두 정점 사이의 거리를 과소 평가할 수있는 그래프
- 두 지점 사이의 가장 짧은 거리는 라인이지만 아마도 실제 거리는 그보다 클 것입니다.
? 이 경우 최소한의 방법은 무엇입니까?
프로젝트를 실행하십시오
결과
저자
특허
이 프로젝트는 MIT 아래에 있습니다. 자세한 내용은 여기를 참조하십시오.
