Search Algorithm [3]. 균일 비용 탐색 (Uniform Cost Search : UCS)

균일 비용 탐색(Uniform Cost Search : UCS)

균일 비용 탐색 이란?

* 사전적 정의 : 균일 비용 탐색은 그래프에서 노드 간의 최단 경로를 찾아주는 Dijkstra Algorithm(다익스트라 알고리즘)을 이용해서 탐색하는 방식을 의미한다.

* 간단한 정의 :  현재 우선순위 큐에 들어있는 노드들의 인접한 노드들을 탐색하는데 소요되는 총 비용을 비교하여 가장 작은 비용이 드는 노드를 탐색하는 방식으로 시작 state와 골 state가 정해진 다익스트라 알고리즘이라고 생각하면 된다.

균일 비용 탐색 의 데이터 저장 구조

균일 비용 탐색은 자식노드로 가는데 드는 총 비용들을 검사해서 비교한 후 가장 작은 비용이 드는 노드를 저장소에 추가하면서 데이터를 확장한다.

이때 자식노드로 움직이는데 드는 총 비용을 비교해가면서 새로운 확장을 해 나가기 때문에 노드와 그 노드까지의 총 비용이 하나로 합쳐져서 저장되는 구조를 발견할 수 있다.

이러한 데이터와 비교해야할 비용이 합쳐져서 저장되는 데이터 구조에 가장 적합한 것은 Priority Queue 구조이다.

따라서 균일 비용 탐색을 사용할 때에는 Priority Queue를 저장구조로 사용하는 것이 매우 편리하다.

균일 비용 탐색 의 탐색 과정 & 데이터 저장 과정

* 아래의 그래프 쉽게 보는 법

- 초록색 점선으로 이루어진 노드는 아직 방문한적도 없고 스택에 들어있지도 않은 노드를 의미

- 실선에 흰색 배경인 노드는 현재 스택에 들어있는 노드를 의미

- 실선에 회색 배경인 노드는 방문한 적이 있는 노드를 의미

- 검은색으로 칠해진 노드는 방문한 적이 있고 그 노드 아래의 자식 노드들까지 전부 방문했음을 의미

(1)	Priority Queue  = [(A,0)]
(2)	Priority Queue = [(B,7),(C,8)]
(3)	Priority Queue = [(C,8),(D,7+9),(E,7+5)]
(4)	Priority Queue = [(D,7+9),(E,7+5),(F,8+10),(G,8+6)]
(5)	Priority Queue = [(D,7+9),(F,8+10),(G,8+6),(J,7+5+2),(K,7+5+13)]
(6)	Priority Queue = [(D,7+9),(F,8+10),(J,7+5+2),(K,7+5+13),(N,8+6+4),O(8+6+11)]
(7)	Priority Queue = [(D,7+9),(F,8+10),(K,7+5+13),(N,8+6+4),O(8+6+11)]
(8)	Priority Queue = [(F,8+10),(H,7+9+1),(I,7+9+14),(K,7+5+13),(N,8+6+4),(O,8+6+11)]
(9)	Priority Queue = [(F,8+10),(I,7+9+14),(K,7+5+13),(N,8+6+4),(O,8+6+11)]
(10)	Priority Queue = [(I,7+9+14),(K,7+5+13),(L,8+10+3),(M,8+10+12),(N,8+6+4),(O,8+6+11)]
(11)	Priority Queue = [(I,7+9+14),(K,7+5+13),(L,8+10+3),(M,8+10+12),(O,8+6+11)]
(12)	Priority Queue = [(I,7+9+14),(K,7+5+13),(M,8+10+12),(O,8+6+11)]
(13)	Priority Queue = [(I,7+9+14),(M,8+10+12),(O,8+6+11)]
(14)	Priority Queue = [(I,7+9+14),(M,8+10+12)]
(15)	Priority Queue = [(M,8+10+12)]

위의 그림과 같이 각 노드를 탐색하는데 드는 비용이 그래프처럼 되어 있다면 균일 탐색 비용으로 이 그래프를 탐색할 경우

[A -> B -> C-> E -> G -> J -> D -> H -> F -> N -> L -> K -> O -> I -> M] 

의 순서로 노드들을 탐색할 것이다.

균일 비용 탐색 의 속성

 

균일 비용 탐색은 깊이보다는 비용으로 탐색하기 때문에 노드의 개수 b나 전체 깊이 d 로는 복잡도를 표현하기가 매우 어렵다.

(C는 최적의 해에서의 총 비용을 의미, ε은 탐색하는데 소용되는 비용의 최소값을 의미)

* 시간 복잡도 (Time Complexity)

균일 비용 탐색의 시간 복잡도는  이다.

* 공간 복잡도 (Space Complexity)

저장 공간에 저장해야할 노드들은 트리에서 현재 검사하고 있는 노드와 깊이가 같은 노드들과 현재 깊이에서 검사를 마친 노드들의 자식노드들이다.

최적의 해에서의 총 비용이 C이고 모든 탐색에 소요되는 비용은 ε 이상이므로 C/ε 깊이에 탐색하고자 하는 노드가 있다고 볼 수 있다.

이때 균일 비용 탐색에서 사용하는 전체 저장 공간은 아래와 같다.

따라서 균일 비용 탐색의 공간 복잡도는   이다.

균일 비용 탐색 의 장단점

* 장점

- 출발 노드에서 목표 노드까지의 최단 길이 경로를 보장할 수 있다.

- 무한한 루프에 빠지지 않게 해준다.

* 단점

- 기하급수적으로 메모리 공간이 필요하기 때문에 깊이가 커질수록 메모리 공간이 많이 필요하다.

균일 비용 탐색 의 의사코드(수도코드, Pseudo Code)

procedure UniformCostSearch(Graph, start, goal):

    

    node <- start

    cost <- 0

    frontier <- priority queue containing node only

    explored <- empty set

    do:

        if frontier is empty:

            return failure

        node <- frontier.pop()

        if node is goal:

            return solution

        explored.add(node)

        for each of node's neighbors n:

            if n is not in explored or frontier:

                frontier.add(n)

            else if n is in frontier with higher cost:

                replace existing node with n