다익스트라 (2) 썸네일형 리스트형 A* 알고리즘 (A* Search Algorithm) A* 알고리즘(A* search algorithm), 그동안 개념만 얼추 알고 있던 알고리즘이었습니다. A* 알고리즘은 인공지능 분야에 더 가깝기 때문입니다. 따라서 저도 학부 인공지능 수업 시간에 잠깐 들었던 게 다였죠. 그런데 이번 학기 조교 일을 하면서 어쩌다 보니 A* 알고리즘을 좀 심도 있게 공부해야 할 모종의 사건(?)이 생겼습니다. 처음에는 뭐 이런 것까지 공부해야 하나 싶었지만, 이것저것 찾아 보고 공부하다 보니 웬걸 이론적으로도 흥미로운 내용이 많이 있더군요. 이번 기회에 공부한 내용을 정리하는 겸하여 이 글을 적습니다. 다만 본문의 내용은 제가 이해한 내용을 바탕으로 제 방식대로 재해석하여 적은 것입니다. 따라서 원래 인공지능 분야에서 이해되는 방식과는 다를 수 있습니다. 이점 양지하시.. 다익스트라의 알고리즘 (Dijkstra's Algorithm) 최단 경로 문제(shortest path problem)는 가장 유명한 조합론적 최적화 문제 중 하나로, 이름에서 유추할 수 있듯이 다양한 분야에서 널리 활용되는 문제입니다. 지난 포스트에서는 이 문제를 정확히 정의하고 최단 경로가 갖는 구조적인 특징을 이해하였으며, 마지막으로 \( O(|V||E|) \) 시간에 이를 해결하는 벨만-포드 알고리즘(Bellman-Ford algorithm)에 대해서도 공부했습니다. 2021.08.22 - [조합론적 최적화/Shortest path] - 최단 경로 문제 & 벨만-포드 알고리즘 (Shortest Path Problem & Bellman-Ford Algorithm) 최단 경로 문제 & 벨만-포드 알고리즘 (Shortest Path Problem & Bellman.. 이전 1 다음
