[1. 개요]
dfs 와 달리 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘
가중치가 없는 그래프에서, 어떤 시작 정점에서 다른 모든 정점까지의 최단 경로를 계산 할 수 있다.
탐색 중, 처음 방문하는 정점이 있다면
- 방문 예정이라고 체크하고, (발견 여부라고 보는 것이 좀 더 정확?)
- Queue 에 푸쉬한다.
dfs 와 비교하여 bfs 에서 모든 정점은 3가지 상태를 갖는다.
- 아직 발견되지 않은 상태
- 발견되었지만, 아직 방문하지 않은 상태
=> 정점의 큐에 저장 된 상태 - 방문된 상태
[2. bfs 와 최단 거리]
bfs 는 보통 딱 하나의 용도로 사용되는데, 두 정점 간의 최단 경로 문제이다.
- 가중치가 없는 그래프에서 사용 가능
- 어떤 시작 상태에서 타겟으로 하는 상태까지 가장 빨리 도달하는데 걸리는 시간 등.
- 이 외에는 거의 dfs 로 푼다고 보면 된다.
그래프에서 bfs 를 수행하면, dfs 와 같이 bfs 스패닝 트리를 얻을 수 있다.
- 시작점으로부터 다른 모든 정점까지의 최단 경로를 이 스패닝 트리 위에서 찾을 수 있다.
[3. 양방향 탐색]
시작 정점에서 시작하는 정방향 탐색과
목표 정점에서 시작하여 거슬러 올라가는 역방향 탐색을 동시에 진행하여,
이 둘이 가운데서 만나면 종료한다.
정방향 탐색과 역방향 탐색에서 방문 할 정점들을 모두 같은 큐에 넣되,
최단 거리를 저장할 때 아래와 같이 저장한다.
- 정뱡향은 양수
- 역방향은 음수
인접한 상태를 검사했는데, 서로 부호가 다르면 가운데서 만났다고 볼 수 있다.
양방향 탐색은 보통 정방향 탐색으로만 진행했을 때 보다
탐색 공간을 상당히 많이 줄여서 성능 개선 효과를 볼 수 있다.
다만, 항상 사용 할 수 있는 것은 아니다.
- 역방향 간선을 쉽게 찾기 어렵거나,
- 역방향 탐색의 분기수가 지나치게 많거나
- 위와 같은 경우에서는 양방향 탐색을 적용 할 수 없다.
보통, 현실적인 edge 개수를 갖는 양방향 그래프(무방향 그래프) 에서 적용이 가능하다 볼 수 있다.
- 무방향 그래프라면 a -> b 이면, b -> a 도 연결되어 있기 때문에, 역방향 간선을 쉽게 구할 수 있다.
[4. 점점 깊어지는 탐색]
양방향 탐색을 사용 할 수 없는 경우거나,
목표 정점까지 최단 거리가 너무 길어서 양방향 탐색으로도 최단 경로를 찾을 수 없는 경우
=> 양방향 탐색으로도 탐색 공간이 너무 커진다고 볼 수 있다.
이 경우 적용 해볼 만 한 기법이
- 점점 깊어지는 탐색 (Iteratively Deepening Search, IDS)
bfs 에서는 앞으로 방문 할 정점 목록을 저장하는 큐가 필요하며,
이를 저장하기 위한 메모리 공간이 필요하다.
- dfs 에서는 발견 즉시 방문하므로, 이러한 메모리 공간이 필요하지 않다.
- 그리고, 방문 여부를 기록하지 않으면 메모리를 거의 사용하지 않고 탐색 할 수 있다.
그러나, 이런 구조라면, 최단 경로를 찾기 힘들다.
- 방문 여부를 저장하지 않으면 사이클에 빠질 수 있고
- 목표 정점에 도달하였더라도, dfs 특성 상, 지금까지 경로가 최단 경로임을 보장 할 수 없기 때문이다.
여기서 IDS 는
- 임의의 깊이 제한 L 을 정하고,
=> 사용 할 수 있는 간선 개수라고 보는 편이 맞을 듯, - 이 제한 보다 짧은 경로가 존재하는지 확인한다.
- 짧은 경로가 없다면, L 을 늘려서 다시 시도 한다.
- 탐색 중, 지금 까지 찾아낸 최단 경로 길이를 전역 변수(=best) 등에 저장하고,
- 탐색 중, 현재 경로 길이가 best 이상이면 탐색을 종료한다.
=> best 보다 더 이상 짧아질 수 없기 때문이다. - best 를 {깊이 한계 값 (L) + 1} 로 설정하고
- 탐색 후, 결과 값이 깊이 한계 값 (L) 이하로 내려왔는지 확인하면 된다.
