저는 현재 보행자 탐색을위한 소프트웨어를 개발 중입니다. 어려운 주제는 그 작업에 가장 적합한 라우팅 알고리즘을 찾는 것입니다. 나는 A *가 그런 종류의 소프트웨어에서 실제로 사용되는 알고리즘 중 하나라고 들었다.보행자 내비게이션을위한 라우팅 알고리즘 비교
이 문제를 해결하는 다른 알고리즘을 제안 해 주시겠습니까? 그들은 공연에 대해 어떻게 비교합니까? 얼마나 많은 메모리와 공간이 필요합니까?
미리 답변 해 주셔서 감사합니다.
그럼 iterative deepening search을 살펴볼 수 있습니다. 제 의견으로는 당신의 문제에 매우 현명한 접근입니다.하지만 알고리즘이 완전한 탐색을하기 위해 설계되었으므로 훌륭한 경험적 방법으로 A *와 관련하여 상당히 시간이 많이 걸릴 위험이 있습니다. 위키
:
IDDFS는 깊이 우선 탐색 결합의 공간 효율성과 너비 우선 탐색 의 완전성 (분지 유한 요소 인 경우). 경로 비용이 노드의 깊이 의 감소하지 않는 함수 일 때 최적 인 것은 입니다. IDDFS의 공간 복잡성은 O (bd)이며, 여기서 b는 분기 인수이고 d는 가장 얕은 목표의 깊이입니다. 반복 심화 상태는 여러 번 방문하므로 낭비 적이지만 노드의 트리에서 대부분 이 최하위에 있으므로 너무 많은 비용이 드는 것으로 밝혀지지 않으므로 많은 경우 중요하지 않습니다. 어퍼 레벨은 여러 번 방문됩니다.
그리고 다시, 시간 복잡도에 관한 것에 대해 : O (BD) :
이균형 잡힌 나무 IDDFS의 시간 복잡도는 깊이 우선 탐색과 같은 을 할 밖으로 작동합니다.