선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 이 경우(전방 탐색과 후방탐색이 만난 경우) 탐색된 경로의 비용은 최적 경로의 비용과 평균적으로 큰 차이는 없으나, 만일 양방향에서 최적 경로를 탐색하고자 한다면 일반적으로 탐색 시간이 단방향에 비하여 오히려 증가하며 최악의 경우 탐색 시간이 2배 정도 소요될 수도 있다[6]. 본 논문에서는 양방향 /"알고리즘이 왜 최적 경로를 보장해 주지 못하는 가에 대하여 고찰해 보고 최적 경로를 보장하며 탐색 시간이 적게 소요되는 새로운 양방향 A* 알고리즘을 제안한다. 또한 제안된 양방향 A*알고리즘이 단방향 A* 알고리즘에 비하여 어느 정도의 탐색 시간 절약 효과가 있는지를 실험을 통하여 고찰해 보았다.
- 본 논문에서는 양방향 /"알고리즘이 왜 최적 경로를 보장해 주지 못하는 가에 대하여 고찰해 보고 최적 경로를 보장하며 탐색 시간이 적게 소요되는 새로운 양방향 A* 알고리즘을 제안한다. 또한 제안된 양방향 A*알고리즘이 단방향 A* 알고리즘에 비하여 어느 정도의 탐색 시간 절약 효과가 있는지를 실험을 통하여 고찰해 보았다.
- 본 논문에서는 최적 경로 탐색에 많이 사용되는 A*알고리즘의 효율성을 매우 개선한 새로운 양방향 A*알고리즘을 제안하였다. 제안된 알고리즘은 실험을 통하여 그 성능을 검증하였으며 실험 결과 탐색 노드 수와 탐색 시간에서 매우 우수한 성능을 보여주는 것을 알 수 있었다.
가설 설정
- 그리고 이 경로보다 경로 비용이 적은 또 다른 최적 경로가 어딘가에 존재한다고 가정하고, 이해를 돕기위해 그림 3.5에서 점 p는 양방향 탐색이 만난 교차점이고, s에서 m까지 그리고 점선을 거쳐 山에서 t까지의 경로가 최적 경로라고 하자.
- 정 리 1) 양방향 A* 알고리즘에서 전방 탐색과 후방 탐색이 만났을 때 탐색이 완료한 것으로 한다면, 양방향 A* 알고리즘은 최 적 경로를 보장하지 않는다.
- 정리 3) 양방향 A*알고리즘에서 최적 경로를 보장되기 위해서는 을 만족하여 야 한다. 여 기서 乙 姦과 L 氣은 지금까지 탐색된 최저 경로 비용를 갖는 경로에서, 乙»은 출발점에서 두 탐색이 만난 교차점까지의 경로 비용을 나타내고 L氣은 교차점에서 목적지까지의 경로 비용을 나타내며 전체 경로 비용은 두 경로 비용의 합인로 표현된다.
- 증명 : 양방향 탐색에서 두 탐색이 서로 만났고 이 로서 만들어 진 경 로가 지 금까지 탐색된 출발지와 목적지간의 경로 비용 중 가장 적다고 가정하자. 그리고 이 경로보다 경로 비용이 적은 또 다른 최적 경로가 어딘가에 존재한다고 가정하고, 이해를 돕기위해 그림 3.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.