[2023 동계 모각코 6회차 회고록] a* 알고리즘 학습 및 적용

 이번 모각코 시간에는 a* 알고리즘을 복습했다. 현재 하고 있는 프로젝트에서 그래프를 만들어 최소 거리를 출력하여 하나의 결과물을 만들어내야 한다. 탐색을 적게 하면서 좋은 결과를 내기 위한 알고리즘을 찾기 위해서 적합한 search 방법을 찾아봤다. 2학년 알고리즘을 배웠을 때, a* 알고리즘을 이용하면 목표물과의 휴리스틱 값을 가중치로 더해주기 때문에 효율적인 탐색이 가하다는 것을 배웠다. 

 

 그때 당시의 강의자료를 살펴보다가 아래의 시각화 자료를 찾았다. 탐색 알고리즘에 따라 어떤 노드를 방문하는지 색깔로 알려주는 사이트였다. 파란색으로 칠한 부분은 탐색된 부분이고, 초록색은 탐색한 노드이다.  

 

https://qiao.github.io/PathFinding.js/visual/

PathFinding.js

 

아래 사진을 보면 빠른 편인 다익스트라와 a* 알고리즘을 비교했다. a*에 비해 다익스트라는 전체 탐색 부분이 보이지 않을 정도로 차이가 확연하게 난다. 이정도일 줄은 몰랐지만 시각화 된 것을 보니 차이를 제대로 배운 것 같다. 

 

다익스트라를 사용할 때 vs a-star 알고리즘을 사용할 때

 

 지금 하고 있는 프로젝트는 음악 feature를 사용해서 비슷한 음악 사이의 노드를 연결하고, 길을 찾는 것이다. 

기존의 것이 없어 우리만의 방법을 만들어야 한다. 실제 알고리즘 강의에서 배운 것을 활용할 수 있으면 좋겠다. 다양한 방법을 시도해볼 필요가 있다.