A*는 양방향 검색 알고리즘에 맞게 조정할 수도 있습니다. 정지 기준을 위해 특별한주의를 기울여야합니다. [32] 탐욕스러운 최고의 검색 알고리즘과 차별화되는 A*를 설정하는 것은 이미 이동한 비용/거리 g(n)를 고려한다는 것입니다. A*는 정보에 입각한 검색 알고리즘 또는 가장 좋은 첫 번째 검색으로, 가중치 기반 그래프의 관점에서 공식화됩니다: 그래프의 특정 시작 노드에서 시작하여 가장 적은 비용(가장 적은 거리 이동)을 갖는 주어진 목표 노드로가는 경로를 찾는 것을 목표로 합니다. (, 가장 짧은 시간 등) 이렇게 하려면 시작 노드에서 시작되는 경로 트리를 유지하고 해당 경로의 종료 기준이 충족될 때까지 해당 경로를 한 번에 한 가장자리씩 확장합니다. 알고리즘 A는 P의 모든 문제 P와 Alts의 모든 알고리즘 A′에 대해 P의 모든 문제 P에 대해 Alts의 집합에 대해 최적으로 효율적입니다. P를 해결에 A′ A*의 최적 효율에 대한 최종 연구는 리나 데히터와 유대 진주 때문입니다. [9] 그들은 Alts와 P의 다양한 정의를 A*의 추론이 단순히 허용가능하거나 일관되고 허용 가능한 것으로 간주했습니다. 그들이 입증 한 가장 흥미로운 긍정적 인 결과는 일관된 휴리스틱을 가진 A *가 모든 “비 병리학적”검색 문제에 대해 허용 가능한 모든 A * 와 같은 검색 알고리즘과 관련하여 최적으로 효율적이라는 것입니다. 대략 적으로 말하자면, 비 병리학 적 문제에 대한 그들의 개념은 우리가 지금 “넥타이 끊기까지”라는 의미입니다. 이 결과는 A*의 추론이 허용되지만 일관성이 없는 경우 유지되지 않습니다. 이 경우 Dechter와 Pearl은 일부 비병리학적 문제에 대해 A*보다 임의로 적은 수의 노드를 확장할 수 있는 A*와 같은 알고리즘이 존재한다는 것을 보여주었습니다. 왜 A * 검색 알고리즘? 비공식적으로 말하기, A * 검색 알고리즘, 다른 통과 기술과는 달리, 그것은 “두뇌”가 있습니다.

그것이 의미하는 바는 실제로 다른 기존의 알고리즘과 분리하는 스마트 알고리즘이라는 것입니다. 이 사실은 아래 섹션에서 자세히 지워집니다. 또한 많은 게임과 웹 기반 맵이 이 알고리즘을 사용하여 가장 짧은 경로를 매우 효율적으로 찾을 수 있다는 점도 언급할 가치가 있습니다(근사치). A* 검색 알고리즘이란 무엇입니까? A* 검색 알고리즘은 경로 찾기 및 그래프 탐색에 사용되는 가장 인기 있는 기술 중 하나입니다. 최적의 솔루션을 반환하는 것이 보장되는 경우 검색 알고리즘을 사용할 수 있다고합니다. A*에서 사용하는 추론 함수가 허용되는 경우 A*는 허용됩니다. 이에 대한 직관적인 “증명”은 다음과 같습니다: 원래 1968A* 용지[3]에는 휴리스틱 함수가 일관되고 A*의 타이 브레이킹 규칙이 적절하게 선택된 경우 A*와 같은 알고리즘[7]이 A*보다 적은 노드를 확장할 수 없다는 정리가 포함되어 있습니다. 몇 년 후 [8] 일관성이 필요하지 않다고 주장하는 “수정”이 발표되었지만, 이는 Dechter와 Pearl의 A*의 최적성(현재의 최적 효율성)에 대한 최종 연구에서 거짓으로 나타났습니다. 허용가능하지만 일관되지 않은 추론을 가진 A*는 대체 A*와 같은 알고리즘보다 임의로 더 많은 노드를 확장합니다. [9] A*는 자신의 행동을 계획할 수 있는 모바일 로봇을 구축하는 것을 목표로 하는 Shakey 프로젝트의 일환으로 만들어졌습니다.

Nils Nilsson은 원래 셰이키의 경로 계획에 그래프 트래버스 알고리즘[4]을 사용하여 제안했습니다. [5] 그래프 트래버스는 추론 함수 h (n) , {displaystyle h(n)}에서 노드 n {displaystyle n}에서 목표 노드까지의 예상 거리로 안내되며, g (n) 및 {displaystyle g(n)}를 완전히 무시합니다.