더 나은 휴리스틱 스 그러면 A *

Question

안녕하세요 여러분은 stenford의 ai-class.com에 등록되어 있습니다. 강의 첫 주에 * 알고리즘에 대해 배웠고 다른 검색 알고리즘을 더 잘 사용하는 방법을 배웠습니다. 아주 많이 나는 감사하고 A * 우리의 놀이에 대한 결과를 게시를 구현하는 조지 감사하지만 http://george.mitsuoka.org/StanfordAI/slidingBlocks/ :

나는 또한 내 클래스 메이트 중 하나는 그가에 게시 한 블록 퍼즐을 슬라이딩 4 × 4에 구현 보여줍니다.

나는 더 나은 프로세스를 만들 수있는 방법이 있는지 또는 더 나은 휴리스틱 스 A *가있는 지 궁금해했다. 목표를 달성하는 데 필요한 거리의 합계? 그리고 더 나은 알 고안이 있고 그런 문제에 대한 A *가 있다면, 나는 그들에 대해서도 알고 싶습니다.

도와 주셔서 감사 드리며 불일치가 발생하는 경우, 내 프로필을 다운 그레이드하기 전에 stackoverflow 방법을 배우면서 여전히 내 접근 방식을 업그레이드하거나 req에서 질문을 삭제할 수있는 기회를 제공하십시오.

Answer 1

귀하의 heuristic function에 따라 다릅니다. 예를 들어 완전한 휴리스틱 스 [h*], greedy 알고리즘 (*)을 사용하면 A *가 더 좋은 결과를 가져 오며 여전히 최적 일 것입니다. 솔루션에 필요한 노드 만 개발할 것입니다. 불행히도, 당신이 완벽한 경험을 가지고있는 경우는 거의 없습니다.
(*) greedy 알고리즘 : 항상 h 값이 가장 작은 노드를 개발하십시오.

그러나 휴리스틱이 매우 나쁜 경우 : h=0이면 A *는 실제로 BFS입니다! 이 경우 A *는 O(B^d) 개의 노드를 개발할 것입니다. 여기서 B는 분기 요인이고 d는 해결에 필요한 단계 수입니다.
이 경우 하나의 대상 기능이 있으므로 (*)은 O(2*B^(d/2))=O(B^(d/2)) 개의 노드 만 개발해야하기 때문에보다 효율적입니다. 이는 A *가 개발할 대상보다 훨씬 적습니다.
양방향 검색 : (*) 대상에서 BFS를 실행하고 시작 노드에서 각 반복은 각면에서 한 단계이며 알고리즘은 두 정면에 공통 정점이있을 때 종료됩니다.

평균의 경우, 완벽하지는 않지만 완전히 테럴하지 않은 경험적 방법을 사용하면 A *가 두 솔루션에서 모두 더 잘 수행됩니다.

평균적인 경우의 가능한 최적화 : 시작 쪽에서 A * :를 사용하여 실행할 수도 있고, 경험적으로 A *를 실행할 수도 있고 대상 쪽에서 정규 BFS를 실행할 수도 있습니다. 솔루션을 더 빨리 얻을 수 있습니까? 아무 생각도, 아마 두 가지 가능성을 벤치 마크하고 어느 것이 더 나은지 찾아야합니다. 그러나이 알고리즘에서 발견 된 솔루션은 BFS와 A *처럼 최적 일 것입니다.

Answer 2

A *의 성능은 동영상에서 배웠던 예상 비용 경험칙의 품질을 기반으로합니다. 해당 주에서 실제 비용에 최대한 근접하게 예상 비용 휴리스틱을 얻으면 확장해야하는 총 상태 수가 줄어 듭니다. 예를 들어 대형 주 공간 검색에서 하드웨어 제한 사항에 직면했을 때와 같이 특정 상황에서 더 잘 수행되는 다양한 변형이 있습니다.