[python] 기본적인 탐색 알고리즘 1 - DFS

탐색 알고리즘에 대해 알아봅시다.

 

인공지능을 공부하면, 상당수의 개념이 상태공간에서 비롯됨을 알 수 있습니다.

 

이러한 상태공간을 탐색하는데에는 여러 방법이 있는데요. 그중에서도 아무런 기초 지식이 없을때 활용할 수 있는 탐색 방법중 하나인 망라적 탐색(Exhaustive Search)에 대해서 알아보도록 하겠습니다. 

 

 

 

망라적 탐색을 수행하려면 몇 가지 기본적인 Rule을 숙지해야합니다.

• 이미 확인한 곳을 다시 확인해서는 안됨 (closed list로 관리)
• 아직 확인하지 않은 곳을 알고 있어야함 (open list로 관리)
• 효율적인 순서로 탐색해야함 -> 깊이우선탐색(DFS), 너비우선탐색(BFS) 활용

 

그 중에서도 이번에는 깊이 우선 탐색인 Depth-First Search (DFS)에 대해 알아보고, 파이썬으로 구현해보는 시간을 갖도록 하겠습니다. 위 탐색 방법은 그래프와 리스트로 확인하는 것이 직관적으로 이해하기 수월할 것입니다. 아래의 그림을 살펴보죠

 

DFS 원리 설명

 

왼쪽의 그래프를 탐색한다고 가정해보자. 오른쪽의 open list, closed list로 관리가 가능하다.

이 그래프는 DFS의 전반적인 프로세스를 보여주고 있습니다.

각 노드 옆에 위치한 숫자는 탐색 순서를 나타내고 있습니다. 말 그대로 깊이 우선 탐색이기에 한쪽 가지의 뿌리까지 확인하고 그 다음(여기서는 오른쪽)으로 이동하여 다시 탐색을 수행하고 있습니다.

 

간단하게 유사코드로 설명을 드리자면, 아래와 같은 방식으로 DFS를 수행할 수 있습니다.

초기 상태 (최상단에 위치한 노드)를 open list로 넣고, closed list는 빈 리스트로 시작

while open list:
	
    - open list의 첫 요소(a)를 꺼내고, a를 closed list로 이동 (a 탐사 완료)
    - a가 목표 상태라면 해를 발견하였으므로 탐색 종료
    - a에 인접한 상태 중 아직 탐사하지 않은 상태(자식 노드)를 모두 open list의 첫 요소로 추가

 

DFS는 망라적 탐색의 한 방법으로써, 모든 가능성을 다 확인해보는것이 특징입니다. 그만큼 확인해야할 데이터가 많다면 탐색 시간은 오래 걸릴 수 있겠죠.

 

DFS 파이썬 코드 구현

이번에는 DFS 응용을 통한 코드 구현을 해보죠.

 

아래와 같은 미로가 있다고 가정해봅시다. 

 

인공지능이 이 미로를 풀고 Goal(G)까지 도달하기 위해서 DFS를 활용할 수 있을 것입니다.

 

위 미로를 그래프로 표현해보자면..

조금은 친숙한 트리 모양의 그래프로 나타낼 수 있습니다.

이제 오픈리스트와 클로즈 리스트를 만들어서 문제를 풀 수 있겠죠.

 

파이썬 코드는 다음과 같습니다.

# 그래프 내 노드 dictionary로 표현
graph = { 
    '0' : ['3'],   # key는 0번 노드, value는 0번 노드의 자식 노드
    '3' : ['4', '7'],  # key는 3번 노드, value는 3번 노드의 자식 노드 
    '4' : ['6', '1'],  # ...
    '7' : ['9', '8'],
    '6' : ['2', '100'],
    '2': [],   # 발단 노드는 value가 없는 것이 특징
    '100' : [],  # 100번 노드를 Goal이라고 가정
    '1': [],
    '9': [],
    '8': ['10', '5'],
    '10': [],
    '5': []
}


def dfs(graph, start_node):
	""" graph에 트리 구조 입력, start node에 뿌리노드(최상단 노드) 입력 """
    open, closed = [], []
    open.append(start_node)

    while open:
        node = open[-1]
        del open[-1]

        if node not in closed:
            closed.append(node)
            open.extend(graph[node])

        if node == '100':
            break

    return closed
    
    
dfs(graph, '0')  

# ------- 결과물 ------
# ['0', '3', '7', '8', '5', '10', '9', '4', '1', '6', '100']

 

양 갈래 길에서 왼쪽을 먼저 탐사할 지, 오른쪽을 먼저 탐사할 지 결정할 수 있는데요.  이부분은 랜덤으로 진행을 하거나, 특정한 룰을 주어 다음 단계로 전개할 수 있습니다.