A*, 다익스트라, Bfs차이 질문

Question

저 3개의 알고리즘(?)을 공부하면서 느낀건데 뭔가 큰 차이가 없는것 같아요 bfs에서 최소거리를 찾는 알고리즘을 만든게 다익스트라 이고 A*는 우선순위큐를 사용해서 최소거리를 빠르게(?) 찾는 그런 차이밖에 안느껴지는데 정확하게 이해가 어려운것같아요 제가 이해한게 맞나요?

Rookiss · Answer

BFS : 너비 우선. 모든 간선은 모두 공평하게 +1 depth가 늘어남. 목적지라는 개념이 없어서, 반대 방향도 같이 서칭을 함. 목적지를 찍고 가는 개념이 아니라 찾다 보니 어쩌다 목적지가 얻어 걸린 느낌. Dijikstra : 간선에 가중치의 개념이 추가. (예를 들어 지하철 노선도라면, 역마다 무조건 이동 거리가 동일하지 않겠죠). 특이사항은, 뒤늦게 찾은 경로가 더 좋은 경로일 수도 있음. A* : 목적지를 찍고 간다는 개념이 가장 다른 부분. 목적지에 따라 현재 상황을 휴리스틱이라는 공식으로 평가를 해서, 가능하면 좋은 쪽으로 가려고 노력 (뒤로 가기보다는, 목적지를 '향해' 가려고 시도). Dijikstra처럼 뒤늦게 발견한 경로가 더 좋은 경로일 수도 있음. 어떻게 보면 근본은 BFS이지만, BFS -> Dijikstra -> A* 순서로 조금씩 개선하는 점이 생기는 것입니다.

communityai8509 · Answer

안녕하세요, 인프런 AI 인턴입니다. kamdabin3님. A*, 다익스트라, 그리고 BFS는 각각의 목적에 따라 조금씩 다른 구현을 가진 경로 탐색 알고리즘이며, 각각의 특징과 차이점이 있습니다. 아래에 간단히 설명드리겠습니다. BFS (너비 우선 탐색) : BFS는 최단 경로를 찾는 알고리즘이 아니라, 모든 경로를 확인하기 위한 탐색 방법입니다. 무게가 없는 그래프에서 최단 경로를 보장할 수 있지만, 무게가 있는 그래프에서는 적합하지 않습니다. FIFO(First In First Out) 방식의 큐를 사용하여 특정 지점에서 시작해 인접한 노드를 차례로 방문하며 탐색합니다. 다익스트라 알고리즘 : 다익스트라는 무게가 있는 그래프에서 최단 경로를 찾기 위해 설계된 알고리즘입니다. 각 노드로의 최단 경로를 갱신하며 우선순위 큐를 사용해 탐색합니다. 무게가 있는 경로에서 가장 경제적인 경로를 찾습니다. A* 알고리즘 : A*는 다익스트라의 변형으로, 목표 지점까지의 거리 추정치를 고려하여 효율적으로 경로를 탐색합니다. 다익스트라와 달리 휴리스틱을 사용해 목표에 가까워지는 경로를 우선적으로 탐색합니다. 이로 인해 계산 속도가 빨라질 수 있습니다. 이 차이로 인해, 구체적인 시나리오에 맞춰 적합한 알고리즘을 선택하는 것이 중요합니다. 일반적으로 BFS는 단순 무게 없는 그래프에서, 다익스트라는 무게가 있는 그래프에서, A*는 게임이나 로봇 탐색 등 목표 지점을 빠르게 찾아가는 상황에서 사용됩니다. 더 구체적인 이해를 위한 유사한 질문이 올라와 있으니, 참고하시면 더욱 좋을 것 같습니다: &ldquo;BFS 에 대해서&rdquo; - BFS의 기본적인 개념에 대해 배울 수 있는 내용입니다. &ldquo;최단 경로 판단에 대하여&rdquo; - BFS와 다익스트라를 비교하여 설명한 내용입니다. &ldquo;BFS 관련 질문드립니다.&rdquo; - BFS의 너비 탐색 원리를 이해하는 데 도움이 됩니다. 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.