부스트 그래프 라이브러리 A * 일관된 휴리스틱을 위해

Question

A *를 문제에 적용 할 때 경험적으로 일관성이 있다면 A * 검색을 더욱 최적화 할 수 있다는 것을 읽었습니다. Boost Graph Library는 A * 알고리즘의 두 가지 버전, astar_search 및 astar_search_tree을 제공합니다. 이 두 문서의 구별에 대한 문서는 명확하지 않습니다. 이 중 하나가 일관된 경험을 가정 한 최적화 된 검색을 수행합니까?

Answer 1

부스트 메일 링리스트에 문의하여 답변을 얻었습니다. 나는 후손 여기 답을 재현 할 수 있습니다 :

구분은 같은 정점을 여러 번 방문 을 방지하기 위해 만든 노력이 있어야 여부입니다. 버텍스가 일 때 많은 경로를 사용하여 도달 할 수있는 그래프의 경우, 버텍스와 그 후계자를 다시 방문하는 것을 피하기 위해 astar_search를 선호해야합니다. 같은 정점이 여러 경로에 나타나지 않거나 정점을 확인하는 것이 충분히 저렴하지 않으므로 작업을 반복하지 않는 경우 ast35_search_tree는 이 이전에 방문한 정점을 기억하지 못합니다. 반복 된 버텍스를 찾기위한 단점은 전에 참조 된 룩업 테이블 을 저장하는 데 메모리가 많이 필요하다는 것입니다. 검색에 시간이 걸리므로 이 테이블을 업데이트해야합니다. 두 버전의 알고리즘 모두 허용 가능한 휴리스틱 스가 올바르게 작동해야합니다. 나는이 생각하지 않습니다

Link to the thread

Answer 2

_tree과 비 _tree 부스트 그래프 알고리즘 버전의 차이는 _tree 버전이 그래프가 실제로 나무라고 가정한다는 것입니다. 따라서주기가없고 노드에 화살표가 하나만 있습니다.