[그림으로 개념을 이해하는 알고리즘] Breadth first search, 너비 우선 탐색

너비 우선 탐색 (breadth-first-search)

• 너비 우선 탐색을 사용하여 두 항목 간의 최단 경로를 찾을 수 있다.

  • 체커 게임에서 가장 적은 수로 승리할 수 있는 방법을 계산하는 인공지능
  • 맞춤법 검사기(실제 단어에서 가장 적은 개수의 글자를 고쳐서 올바른 단어를 만드는 방법을 찾는다.)
  • 네트워크에서 가장 가까운 의사 선생님을 찾기

그래프란?

---

• 연견의 집합을 모형화한 것.
• 정점(node)과 간선(edge)으로 이루어져 있다.
• 정점은 여러 개의 다른 정점과 바로 이어질 수 있고, 이러한 정점들을 이웃(neighbor) 이라고 한다.

너비우선 탐색

• 너비 우선 탐색은 그래프를 대상으로 하는 다른 종류의 알고리즘이다.

  • 질문 유형 1 : 정점 A에서 정점 B로 가는 경로가 존재하는가?
  • 질문 유형 2 : 정점 A에서 정점 B로 가는 최단 경로는 무었인가?

• 아래와 같은 그림은 ... 사실 Markdown에서 Graph를 그릴 수 없어 sequence를 그린 것이다...

• 위의 그림과 같이 3명의 친구가 망고를 파는지 확인하는 작업을 수행한다고 할때, 우선 찾아볼 친구 목록을 작성 한다. 그리하여 망고를 판매하는지 하지 않는지 순차적으로 수행하면 될 것이다.

  ​

• 위와 같이 새로운 친구의 목록을 그릴 수 있다면 우선 우리가 1단계에서 만날 수 있는 친구들에게 물어본 후 망고를 판매하지 않는다면 그 친구의 친구를 목록으로 하나씩 올리는 방식으로 수행한다.

  • Bob -> Anuzi를 목록에 올리고 우선 첫번째 있었던 친구들의 목록을 찾아본다 (Clare, Alice)
  • Clare, Alice의 경우도 Bob과 마찬가지로 망고를 판매하지 않는다면 그 친구들의 친구들을 하나씩 목록에 올린다. 그 순서대로 다시 찾는다

최단 경로 찾기

---

• 질문 유형 1 : 정점 A에서 정점 B로 가는 경로가 존재하는가?
• 질문 유형 2 : 정점 A에서 정점 B로 가는 최단 경로는 무었인가?

• 3촌 관계보다는 2촌 관계, 2촌 관계 보다는 1촌 관계를 선호 할 것이다.

  • 1촌 관계인 판매상 중 망고를 판매하는 상인이 없을 경우에만 2촌 관계를 탐색 할 것이다.
  • 이것이 너비 우선 탐색이다.
  • 즉, 같은 거리에 있는 곳 우선으로 탐색 후 그 Node에서 뻗어 나가는 Edge를 찾아 가는 형태.

큐

---

• 큐(대기열)은 실생활에서 동일 하게 동작하는 자료구조 중 하나이다.
• FIFO(First In First Out) <-> LIFO(Last In First Out) : Stack
• 임의의 원소에 임의 접근이 불가능하다.
• enqueue(삽입), dequeue(제거) 2가지 연산을 가지고 있다.

그래프의 구현

 
xxxxxxxxxx
graph = {}
graph["you"] = ["alice","bob","claire"]
graph["bob"] = ["anuj","peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom","jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []

• 아누지, 페기, 톰 그리고 조니는 이웃이 없다.

  • 이들에게 향한 화살표는 있어도 이들이 가리키는 화살표는 없다.
  • 이렇게 방향을 가진 그래프는 directed graph라고 한다.
  • 관계에는 방향성이 있다.
  • 무방향성 그래프의 경우 연결만 된다면 서로 이웃이 된다는 뜻이다.

알고리즘 구현

1. 확인할 사람의 명단을 넣을 큐를 준비한다.

2. 큐에서 한사람을 꺼낸다.

3. 이 사람이 망고 판매상인지 확인한다.

   1. 예 : 작업 종료
   2. 아니요 : 그 사람의 이웃사람을 모드 큐에 추가한다.

4. 반복

5. 만약 큐가 비어 있으면 네트워크에는 망고 판매상이 없다.

 
​x
from collections import deque
​
def person_is_seller(name):
    return name[-1] == "m"
  
def search(name):
    search_queue = deque()
    search_queue += graph["you"]
    searched = []
    while search_queue:
        persion = search_queu.popleft()
        if not person in searched:
            if person_is_seller(person):
                print(person + "is a mango seller!!!")
                return True
            else:
                search_queue += graph[person]
                searched.append(person)
       
    return false
​
search("you")

실행시간

---

• 모든 네트워크를 탐색한다는 것은 모든 정점을 따라서 움직인다는 뜻
• 실행 시간은 최소한 (간선의 개수)
• 탐색할 사람을 큐에 저장하는데 걸리는 시간
• 모든 사람에 적용하면 총 (사람의 수)
• 따라서 너비 우선 탐색은 (사람의 수+간선의 수), 보통 라고 표기 (V: 정점의 수, E:간선의 수)