MIT - Introduction to Algorithms
- Lecture 13. Breadth-First Search (BFS)
너비 우선 탐색 Review
Copyright to MIT & Srini Devadas & Erik Demaine
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-notes/
code, data, note pdf : https://courses.csail.mit.edu/6.006/fall11/notes.shtml
한글 번역과 슬라이드를 보고싶은 분은 Edwith - 파이썬을 이용한 알고리즘의 이해 항목 강의를 참조하세요.
URL : https://www.edwith.org/introalgorithm/
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-notes/
code, data, note pdf : https://courses.csail.mit.edu/6.006/fall11/notes.shtml
한글 번역과 슬라이드를 보고싶은 분은 Edwith - 파이썬을 이용한 알고리즘의 이해 항목 강의를 참조하세요.
URL : https://www.edwith.org/introalgorithm/
Graph Search : explore a graph
길을 찾는 것
E = set of edges
All the edges directed : e=(v,w) ordered paris : 방향이 있다
All the edges undirected : e=(v,w) unordered paris : 방향이 없다
UNDIR(undirected)의 경우 각 간선의 끝 점을 안다.
만약 a에 근접한 edges를 알고싶다면 모든 간선의 배열을 다 돌아야함 : 선형 시간
adjacent list 인접 리스트를 통한 더 나은 방식을 사용할 것임
vertex 1. 꼭짓점 2. 정점(頂點)
강의에서는 Figure 1 Directed에서 b->a 방향임
- Web Crawling : 구글에서 웹에 있는 모든 페이지를 찾고 싶을 때 계속 새로운 링크를 따라가야하는 예전 문제
이 문제는 동적으로 생성되는 페이지들로 인해 무한히 반복해서 링크가 연결되는 문제가 발생
해결을 위해 BFS 사용 : 이미 있는 페이지에서 도달할 수 있는 모든 것들을 본다.
- Social Networking : 2 단계에 걸쳐진 친구들을 찾기 위한 Searching, 단서를 찾기 위한 반복
- network broadcast : 인터넷에서 메시지를 탐색하고 싶다면 그래프 탐색 문제
- garbage collection : 도달할 수 없는 없는 데이터 정리
어떤 데이터 구조에 더 이상 도달할 수 없게되면 그 데이터를 버리고 새로운 메모리를 다시 얻을 수 있음 -> BFS
- model checking
- check mathematical conjunction : 모든 입력 값을 확인하는 전형적인 BFS
일반적인 추측의 유한한 경우를 테스트하고 반례를 발견
- solving puzzles & games : 2x2x2 루빅 큐브를 최적으로 풀기위해 BFS 사용
Pocket Cube : 2x2x2 Rubic's Cube : 10:30 ~
configuration 1. 배열, 배치; 배열 형태 2. 환경 설정
# vertices = $8!\cdot 3^8 = 264,539,520$
작은 1x1x1 cube에서 꼭지점 8, 보이는 면 3개
Undirected : 양방향으로 edge 간선들이 작동
우리는 전체 Nodes에 관심 : Diameter of the graph(God's Number)
2x2x2 : 11
3x3x3 : 20
계산 법은 끝날 때까지 그래프를 한 번에 한 레이어씩 만드는 것 -> 지름을 구할 수 있음
문제 : 기하급수적으로 증가하다 어느 시점에 줄어든다.
nxnxn : $\theta(n^2)$이 표준 답처럼 보이지만 $\theta({n^2 \over log_2(n)})$, 수백만에 해당하는 constant number가 붙긴함
인접 리스트 Array Adj of V linked lists
강의에서는 Figure 2 Directed에서 a->b 방향이 아니라 b->a 방향이기 때문에 b가 c와 a 방향으로 갈 수 있다라는 식의 linked list를 생각해야함
v.neighbors = Adj[v] : 더 객체지향적인 방법
Implicit Representation 26:00 ~
function & method
7x7x7 루빅 큐브의 경우 상태를 나타내는 것은 간단하지만 전체는 우주의 원자의 개수 10의 83승보다 많다 10의 200승?
공간을 아낄 수 있을 뿐 시간을 절약하는 것은 아님
Adjacency list는 얼마나 많은 공간을 차지할까? $\theta(V+E)$
Breath First Search (BFS) : 31:06~
어떤 정점에서 시작해 갈 수 있는 모든 정점edge 들을 찾는다 - 반복 : 모든 정점 탐색
- Visit all nodes reachable from given $s \in V$
- O(V+E) time
- look at nodes reachable in 0 move {s}, 1 move,Adj[s] $\cdots$
- careful to avoid duplicates 중복 회피
dict : level, parent
- v : parent[v]
: parent[parent[v]]
: $\cdots$
:
parent node가 최단 경로를 제공함
그래프 전부를 기억한다면 최적의 전략을 가지게됨 : 모든 구성에 대한 신의 알고리즘
정점을 계속해서 검사하기 때문에 시간적인 소모가 있지만...
frontier를 얻으면 level state를 얻게되는 것
$\sum_{v \in V} |Adj[v]| = 2 |E|$ : Handshaking Lemma
간선의 2배의 시간
|E| directed
s에서 도달할 수 있는 것만 고려하는 것이 아니라 모든 정점을 방문해야하는 다른 루프가 필요
