A *와 탐욕스러운 베스트 퍼스트 검색의 차이점은 무엇입니까?

두 알고리즘 모두 “최우선 검색”범주에 속합니다. 알고리즘 : $ g (n) $ 로 표시되는 검색 공간을 탐색하는 동안 지금까지 습득 한 지식을 모두 사용할 수 가능한 알고리즘입니다. 및 각 노드 에 대해 목표 노드까지의 거리를 추정하는 $ h (n) $ 로 표시되는 휴리스틱 함수 검색 공간에서 $ n $ (종종 그래프로 표시됨).

각 검색 알고리즘은 그래프 (또는 검색 공간)의 각 노드 $ n $ 에 대해 “평가 함수”를 정의합니다. $ f (n) $ . 이 평가 함수는 검색하는 동안 어떤 노드가 먼저 “확장”되는지, 즉 “프린지”(또는 “프론티어”, 또는 “경계”) , 하위 항목을 “방문”합니다. 일반적으로 “best-first”범주의 알고리즘 간의 차이점은 평가 함수 $ f (n) $ 의 정의에 있습니다.

욕심 많은 BFS 알고리즘 의 경우 평가 함수는 $ f입니다. (n) = h (n) $ , 즉 탐욕스러운 BFS 알고리즘은 먼저 목표까지의 예상 거리가 가장 작은 노드를 확장합니다. 따라서 탐욕스러운 BFS는 “과거 지식”(예 : $ g (n) $ )을 사용하지 않습니다. 따라서 그 의미는 “욕심”입니다. 일반적으로 탐욕스러운 BST 알고리즘은 완료되지 않음 입니다. 즉, 항상 그렇지 않은 경로를 선택할 위험이 있습니다. 목표를 달성하십시오. 탐욕스러운 BFS 알고리즘에서 경계 (또는 프린지 또는 프론티어)의 모든 노드는 메모리에 유지되며 이미 확장 된 노드는 메모리에 저장할 필요가 없으므로 버릴 수 있습니다. 일반적으로 탐욕스러운 BFS도 최적이 아닙니다 . 즉, 발견 된 경로가 최적의 경로가 아닐 수 있습니다. 일반적으로 시간 복잡도는 $ \ mathcal {O} (b ^ m) $ 입니다. 여기서 $ b $ 은 (최대) 분기 요소이고 $ m $ 는 검색 트리의 최대 깊이입니다. 공간 복잡성은 가장자리의 노드 수와 발견 된 경로의 길이에 비례합니다.

A의 경우 * 알고리즘 , 평가 함수는 $ f (n) = g (n) + h (n) $ 입니다. 여기서 $ h $ 는 허용되는 휴리스틱 함수 입니다. 종종 별표로 표시되는 “별표”(*)는 A *가 허용 가능한 휴리스틱 함수를 사용한다는 사실을 나타냅니다. 이는 본질적으로 A *가 최적 즉, 항상 시작 노드와 목표 노드 사이의 최적 경로를 찾습니다. A *는 또한 완료 입니다 (검색 공간에서 탐색 할 노드가 무한히 많은 경우 제외). 시간 복잡도는 $ \ mathcal {O} (b ^ m) $ 입니다. 그러나 A *는 검색하는 동안 주변에있는 노드뿐만 아니라 모든 노드를 메모리에 유지해야합니다. A *는 본질적으로 “완전한 검색”(휴리스틱 기능을 사용한다는 의미에서 “정보를받은”)을 수행하기 때문입니다. ).

요약하면 탐욕스러운 BFS는 완전하지 않고 최적이 아니며 시간 복잡성이 $ \ mathcal {O} (b ^ m) $ 및 다항식 일 수있는 공간 복잡성. A *는 완전하고 최적이며 $ \ mathcal {O} (b ^ m) $ 의 시간 및 공간 복잡성을가집니다. 따라서 일반적으로 A *는 탐욕스러운 BFS보다 더 많은 메모리를 사용합니다. A *는 검색 공간이 크면 실용적이지 않습니다. 그러나 A *는 시작 노드와 목표 노드 사이에서 발견 된 경로가 최적의 경로이고 알고리즘이 결국 종료되도록 보장합니다. 반면 Greedy BFS는 메모리를 덜 사용하지만 A *의 최적 성과 완전성을 보장하지 않습니다. 따라서 어떤 알고리즘이 “최고”인지는 컨텍스트에 따라 다르지만 둘 다 “최상”우선 검색입니다.

참고 : 실제로는 이러한 알고리즘을 사용할 수 없습니다. 대신 IDA * 를 사용하세요.

댓글

• 댓글은 확장 된 토론; 이 대화는 채팅으로 이동 되었습니다.

책에 따르면 인공 지능 : 현대적인 접근 방식 (3 판), Stuart Russel 및 Peter Norvig, 구체적으로 섹션 3.5.1 탐욕스러운 최고의 검색 (p. 92)

Greedy best-first search는 목표에 가장 가까운 노드를 확장하려고합니다. 신속하게 해결책을 찾을 수 있습니다. 따라서 휴리스틱 함수 만 사용하여 노드를 평가합니다. 즉, $ f (n) = h (n) $ 입니다.

같은 섹션에서 저자는 탐욕스러운 best-first 검색이 최적도 완전하지도 않음을 보여주는 예를 제공합니다.

3.5.2 섹션 A * 검색 : 동일한 책 (93 페이지)의 총 예상 솔루션 비용 을 최소화하면

A * 검색은 $ g (n) $ , 노드 도달 비용 및 $ h (n)을 결합하여 노드를 평가합니다. $ , 노드에서 목표 $$ f (n) = g (n) + h (n). $$

$ g (n) $ 는 시작 노드에서 노드 $ n $까지의 경로 비용을 제공하므로 및 $ h (n) $ 는 $ n $ 목표에 도달하면 $ f (n) $ = $ n $ 까지 가장 저렴한 솔루션의 예상 비용입니다.

따라서, 가장 저렴한 솔루션을 찾으려는 경우 가장 먼저 시도해야 할 합리적인 방법은 가장 낮은 값이 $ g (n) + h (n) $ 인 노드입니다. 이 전략은 합리적인 것 이상으로 밝혀졌습니다. 휴리스틱 함수 $ h (n) $ 가 특정 조건을 충족한다면 A * 검색은 완전하고 최적입니다. 알고리즘은 A *가 $ g $ 대신 $ g + h $ 를 사용한다는 점을 제외하면 균일 비용 검색과 동일합니다. span>

당신이 말한 내용이 완전히 틀린 것은 아닙니다. 그러나 휴리스틱 함수 h가 허용되면 A * 알고리즘이 최적이되고 완전 해집니다. 즉,이 함수가 목표 도달 비용을 절대 과대 평가하지 않습니다.이 경우 A * 알고리즘이 탐욕스러운 검색 알고리즘보다 훨씬 낫습니다.

댓글

• 자신의 답변을 자세히 설명해 주시겠습니까? 죄송하지만 요점을 이해하지 못했습니다.
• @IramShah-TemmanRafk A *가 최적이고 완전하다는 증거에 대해 이야기하는 것입니다. 이렇게하려면 삼각형 부등식으로 인해 목표까지 남은 거리를 추정하는 휴리스틱이 과대 평가되지 않은 것으로 표시됩니다. 자세한 설명을 보려면

  en.wikipedia.org/wiki/Admissible_heuri stic