목록Algorithm (1)
계밥의 작업소
Dijkstra VS Best-First-Search (Heuristic) VS A* (A Star)
핑크색을 출발점, 보라색을 도착점이라고 하면!! 다익스트라 알고리즘은 인접하면서 탐색되지 않은 Vertice들을 확인한다.(사방으로 모두 탐색!!!) 그러나 사방으로 다 탐색하기 때문에 효율성은 떨어진다. 대신 모든 방면을 다 확인하기 때문에 확실한 최단거리를 구할 수 있다. 최상우선 탐색 알고리즘은 도착점으로 향하는 방향으로만 탐색한다. 여기엔 휴리스틱(Heuristic)이라는 수치가 사용된다. 휴리스틱이란 영단어로 ‘습득하여 배우는’이라는 의미의 형용사로 여기선 “현위치에서 도착점까지의 거리”를 의미한다. 이 휴리스틱이라는 개념덕분에 탐색해야할 범위가 적고 탐색시간이 빠르다는 장점이 있다. 다만, 휴리스틱이라는 수치에 대한 의존도가 너무 크기 때문에 이런 망케이스가 나올 수 있음 A Star> 다른 ..
Algorithm
2014. 9. 9. 23:09