[인공지능 학습 노트] 파이썬 UCS 구현 상태 공간 그래프에 대한 균일 비용 탐색 알고리즘

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

정의

무정보 탐색 알고리즘의 한 종류, 최소 경로 비용을 기준으로 아직 방문하지 않은 노드를 탐색하는 기법

무정보 탐색이란 상태공간에 대한 아무런 정보 없이 정해진 순서에 따라 진행 하며 얻은 정보만 활용하여 탐색하는 방법

 

최소 경로 비용이란

우선 UCS에서 경로 비용이란 시작 노드에서 현재 노드까지 발생되는 모든 비용의 합이다.

예를 들면 시작노드 A 노드에서 C 노드로 갈 때 발생하는 비용은 4이다.

그리고 D 노드를 가는데 C 노드를 통해서 가게 되었다면 A -> C -> D 즉 7이다.

 

노드를 탐색할 때 방문되지 않은 노드의 경로 비용들에서 가장 최소가 되는 노드를 선택하여 탐색하는 방법이

최소 경로 비용을 선택하는 것 즉, 균일 비용 탐색 기법이다.

 

그래프 변환 예시

 

그래프를 탐색하려면 그래프를 트리로 변환해야한다.

그래프를 트리로 변환하는 것은 생각보다 귀찮은데 무방향 그래프라면 더더욱 귀찮아진다.

 

무방향 그래프를 트리로 변환하는 팁은

우리는 이미 시작지점과 도착지점을 알고 있고 그 동안 발생되는 비용을 알고 있다는 점을 이용하는 것이다.

 

우선 시작 노드에서 갈 수 있는 노드를 전부 그려준다 그리고 그 자식들도 모두 그려주는 대신

방문한 노드를 되돌아 가는 경우는 그리지 않는다.

 

즉, A 노드에서 갈 수 있는 노드는 B와 C니까 B와 C 노드를 그려주고 B노드에서 갈 수 있는건 A, C, D, E인데

B는 A노드에서 왔기 때문에 A 노드는 그리지 않고 C, D, E 만 자식으로 그려준다.

그리고 C에서 갈 수 있는 노드는 A, B, D, E인데 A 노드에서 C노드로 갔기 때문에 B, D, E 만그려준다.

 

 

그 다음 자식들을 그리는 기준은 현재 레벨과 상위 레벨에서 같은 이름의 노드 비용이 현재 노드의 비용보다 작거나 같으면 자식 노드를 그리지 않는다. 

 

 

A -> B - > C 노드는 자식 노드를 그리지 않는다. 왜냐하면 위 레벨에 같은 이름의 C 노드의 비용이 더 작기 때문에

A -> B -> D 노드는 자식 노드를 그리지 않는다. 왜냐하면 같은 레벨의 다른 D 노드의 비용이 더 작기 때문에

A -> B -> E 노드는 그린다 왜냐하면 같은 레벨의 다른 E 노드보다 작기 때문에

이러한 방식으로 3 레벨 까지 그리고 그 다음 자식들도 마찬가지로 같은 방법으로 자식을 그려준다.

 

UCS 탐색 방법

우선순위 큐를 이용하여 UCS 알고리즘으로

시작 노드 A 에서 목표 노드 G까지 탐색 방법은 최소 비용을 우선으로 고른다는것이다.

우선순위큐
데이터를 우선순위에 따라 정렬하고 우선순위가 가장 높은 데이터에 접근하여 데이터를 가져오는 큐 자료구조

 

먼저 A 노드를 우선순위 큐에 넣고 A를 빼면서 시작한다.

A 노드를 방문하고 자식 노드 B와 C를 큐에 넣는다.

 

우선순위에 따라 C 노드가 최소 비용이기 때문에 C 노드 방문

C 노드의 자식들도 큐에 넣게 되면 현재 큐에는 B(5), B(9), D(7), E(12) 이렇게 정렬되어 있을 것이다.

만약 우선순위 큐를 사용하지 않고 그냥 선입선출 큐를 사용하면
중복되는 이름의 노드는 비용에 따라 제거하는 연산이 필요할 것이다.

 

다음 우선순위에 따라서 C의 자식들을 방문하지 않고 A -> B 노드로 방문

B의 자식들 큐에 삽입 C 노드는 이미 방문했기 때문에 제외

 

그리고 큐에 들어있는 노드들 중 가장 작은 값의 비용을 가지는 노드는 D이므로 D로 방문

D 자식들 큐에 삽입 이미 방문한 B 노드는 제외

 

 

그 다음 가장 작은 노드는 B인데 B는 이미 방문 했기 때문에 제외

그리고 다음 가장 작은 비용의 노드는 F 방문 F 노드의 자식 큐에 삽입

목표 노드가 큐에 삽입되었다고 해서 도착한것은 아님

 

 

그 다음 작은 노드 E 방문 E의 자식들 큐에 삽입하는데 C는 이미 방문했기 때문에 제외

 

 

그 다음 작은 노드 G 방문 목표 노드 도착!

 

방문 순서는 A, C, B, D, F, E, G이며 최단 노드의 순서는 A, C, D, F, G 이다

 

파이썬 코드 작성

from collections import defaultdict
from queue import PriorityQueue


class Node:
    def __init__(self, name, path, cost=0):
        self.name = name  # 노드 이름
        self.path = path  # 시작 노드로 부터 경로
        self.cost = cost  # 시작 노드로 부터의 가중치 합

    def expand(self, graph):
        # 그래프에서 현재 노드의 자식 노드로 생성할 수 있는 노드를 리스트로 반환
        return [Node(i, [], graph.get(self.name).get(i)) for i in graph.get(self.name).keys()]

    def __lt__(self, other):
        return self.cost < other.cost  # 비교 연산자 재정의

    def __eq__(self, other):
        return self.name == other.name

    def __hash__(self):
        return hash(self.name)


def generateGraph(edges):
    graph = defaultdict(dict)
    for u, v, dist in edges:
        graph[u][v] = dist
    return graph


def UCS(graph, src, dest):
    queue = PriorityQueue()  # 우선 순위 큐 생성
    queue.put(Node(src, [], 0))
    visited = set()

    while queue:
        current = queue.get()
        
        if current not in visited:  # 이미 방문한 노드가 아니면
            visited.add(current)  # 현재 노드를 방문 했다고 체크, set을 이용하여 O(1) 시간 복잡도를 보장
            print(f'방문: {current.name}')

            for state in current.expand(graph):  # 현재 노드의 자식 노드 생성
                if state not in visited:
                    state.cost += current.cost  # 방문된 가중치 합을 자식 노드에 넣는다
                    state.path = current.path + [current.name]  # 자식 노드의 경로에 부모 노드의 경로와 부모 노드를 추가
                    queue.put(state)  # 큐에 추가

        if current.name == dest:  # 현재 노드가 목표 노드면 종료
            current.path.append(current.name)  # 도착 목표 노드에 도달하면 path에 목표 노드를 추가한다
            print(f'Shortest distance is {current.cost}')  # 최단 거리 비용을 출력한다
            print(f'And Search path is {current.path}')  # 최단 거리 경로를 출력한다
            return


if __name__ == "__main__":
    weighted_edges = [['a', 'b', 5], ['b', 'a', 5],
                      ['a', 'c', 4], ['c', 'a', 4],
                      ['b', 'c', 5], ['c', 'b', 5],
                      ['b', 'e', 6], ['e', 'b', 6],
                      ['c', 'e', 8], ['e', 'c', 8],
                      ['b', 'd', 7], ['d', 'b', 7],
                      ['c', 'd', 3], ['d', 'c', 3],
                      ['e', 'g', 3], ['g', 'e', 3],
                      ['d', 'f', 3], ['f', 'd', 3],
                      ['f', 'g', 2], ['g', 'f', 2]]

    graph = generateGraph(weighted_edges)
    UCS(graph, 'a', 'g')

 

자바 언어가 익숙하다 보니 뭐든간에 클래스로 만들려고 하는 버릇이 있는데 오히려 좋은거같다.

노드를 클래스로 만들고 각종 연산자 메서드를 재정의하고 BFS 코드를 기반으로 코드를 작성했다.

 

큐에서 데이터를 접근할 때 선입선출 큐가 아니라 우선순위 큐를 사용하면 최소 경로 비용의 노드를 선택할 수 있다.

 

우선순위 큐를 사용하고 싶지 않다면 단순히 min 함수를 사용해서 리스트에서 뽑아 쓰면 된다. 정말 쉽다.

 

 

---

 

 

학교 과제

파이썬을 이용하여 아래의 State Space Graph에 대한 Uniform Cost Search 알고리즘을 구현하시오.

from collections import defaultdict
from queue import PriorityQueue


class Node:
    def __init__(self, name, path, cost=0):
        self.name = name  # 노드 이름
        self.path = path  # 시작 노드로 부터 경로
        self.cost = cost  # 시작 노드로 부터의 가중치 합

    def expand(self, graph):
        # 그래프에서 현재 노드의 자식 노드로 생성할 수 있는 노드를 리스트로 반환
        return [Node(i, [], graph.get(self.name).get(i)) for i in graph.get(self.name).keys()]

    def __lt__(self, other):
        return self.cost < other.cost  # 비교 연산자 재정의

    def __eq__(self, other):
        return self.name == other.name

    def __hash__(self):
        return hash(self.name)


def generateGraph(edges):
    graph = defaultdict(dict)
    for u, v, dist in edges:
        graph[u][v] = dist
    return graph


def UCS(graph, src, dest):
    queue = PriorityQueue()  # 우선 순위 큐 생성
    queue.put(Node(src, [], 0))
    visited = set()

    while queue:
        current = queue.get()

        if current not in visited:  # 이미 방문한 노드가 아니면
            visited.add(current)  # 현재 노드를 방문 했다고 체크, set을 이용하여 O(1) 시간 복잡도를 보장
            print(f'방문: {current.name}')

            for state in current.expand(graph):  # 현재 노드의 자식 노드 생성
                if state not in visited:
                    state.cost += current.cost  # 방문된 가중치 합을 자식 노드에 넣는다
                    state.path = current.path + [current.name]  # 자식 노드의 경로에 부모 노드의 경로와 부모 노드를 추가
                    queue.put(state)  # 큐에 추가

        if current.name == dest:  # 현재 노드가 목표 노드면 종료
            current.path.append(current.name)  # 도착 목표 노드에 도달하면 path에 목표 노드를 추가한다
            print(f'Shortest distance is {current.cost}')  # 최단 거리 비용을 출력한다
            print(f'And Search path is {current.path}')  # 최단 거리 경로를 출력한다
            return


if __name__ == "__main__":
    weighted_edges = [['a', 'b', 6], ['a', 'c', 3], ['b', 'c', 1],
                      ['c', 'b', 4], ['b', 'd', 2], ['c', 'd', 8],
                      ['c', 'e', 2], ['d', 'e', 9], ['e', 'd', 7]]

    graph = generateGraph(weighted_edges)
    UCS(graph, 'a', 'd')