알고리즘 - 완전탐색(2)

pa324·2019년 12월 14일
0

다양한 형태의 완전 탐색

현실의 상황과 그래프의 탐색 순서를 어떻게 연결할까?

  • 그래프로 변환할 수 없는 상황에 탐색을 적용할 수는 없다. 하지만, 대부분의 상황은 그래프로 변환할 수 있다.
    • 체스
      - 체스를 시작할 때 말의 배치를 정점으로 만든다.
      - 말이 이동할 수 있는 모든 방법을 변으로 만든다.
      - 각 변의 방법으로 말을 옮겼을 때 발생하는 다음 말의 배치를 새로운 정점으로 만든다.
      - 각 상태에서 말이 이동할 수 있는 모든 방법을 다시 변으로 만든다.
      - 이를 반복하면 말의 배치 상태를 그래프의 정점으로, 말을 이동하는 방법을 변으로 하는 유방향 그래프를 만들 수 있다.
  • 그래프로 표현하고 나면 어떤 탐색이 효율적인지 판단해야 한다.

다익스트라 알고리즘

  • 루프가 존재하므로 트리구조가 아니다.
  • 일반적인 탐색을 수행하면 무한 루프에 빠져 검색이 종료 되지 않는다.
  • "한 번 탐색했던 정점은 더 이상 탐색하지 않느나는 규칙" 을 통해 탐색 종료 시점을 정해야 한다.

백트래킹 과 가지치기

  • 기본적으로 백트래킹은 가능한 모든 방법은 탐색한다.
  • 대표적인 방식은 DFS가 있는데, 무한히 깊은곳을 찾아야할때 효율적이지만, 비효율적인 경로를 차단하고 목표지점에 갈수있는 가능성이 있는 루트를 검사하는 방식이 백트래킹 알고리즘이다.
  • DFS에 가지치기를 통해 가지 않아도 되는 루트는 고려하지 않는 완전탐색 기법

위의 그림과 같은 그래프를 깊이를 우선으로 해서 탐색하는 방식이다.

먼저 탐색은 정점 A부터 시작한다. 그리고 A부터 아래로 갈 수 있는 곳이 있는지 찾는다. 왼쪽부터 발견해서 정점 B를 발견한다.

깊이 우선 탐색 규칙에 따라 정점 B 아래에 있는 정점을 또 탐색해야 한다. 하지만 가장 끝까지 탐색을 한 후 최초의 정점 A로 돌아와야 오른쪽 영역도 탐색할 수 있다. 이때 필요한 자료구조가 스택(stack)이다.

정점 H까지 탐색을 완료하고, H 아래에 연결된 정점이 있는지 확인을 하면 정점이 더 이상 없는 것을 알 수 있다. 이제 이전 정점으로 다시 타고 올라가야한다. 스택에는 a,b,d,h순으로 정점이 push되어 있는데, h를 pop시키면 d정점으로 돌아가게 된다. d정점으로 돌아간 후 하위 정점이 있는지 확인을 하는데 I가 발견되고 I를 스택에 넣어서 탐색한다. 이와 같은방식으로 모든 정점을 깊이 순서대로 탐색하는 방식이 DFS이다.

  • 너비 우선 탐색은 깊이 우선 탐색과 다르게 한 획으로 탐색할 수 없다. 대신 가까운 순서로 띄엄띄엄 탐색을 실시한다. 기본적인 방식은 깊이 우선 탐색과 유사하다. 차근차근 탐색하면서 메모리에 정점을 저장하며 돌아다니면 된다.

  • 이전 정점으로 돌아올 필요가 없다.

  • 가까운 순서로 탐색을 하기 때문에 나중에 발견한 정점은 나중에 탐색

정점 A부터 탐색을 시작한다. 정점 A에서는 정점 B와 정점 C가 연결되어 있다. 이들을 다음에 탐색할 것이므로 메모리에 저장한다.
BFS는 한번 탐색한 정점으로 다시 돌아올 필요가 없으므로 A는무시해도 된다. (메모리에서 제외)

다음은 정점 B를 탐색한다. 정점 B에는 정점 D가 연결되어 있으므로 D를 메모리에 추가한다. 이어서 정점 C를 살펴본다. C에는 E,F,G가 연결되어 있으므로 이를 메모리에 추가한다.

위와 같은 탐색을 계속 반복하면 모든 정점을 가까운 순서대로 탐색할 수 있다. 너비우선 탐색은 최단 경로 문제 등에 자주 사용되는 알고리즘이다.

깊이 우선 탐색과 너비 우선 탐색의 차이점

  • 깊이 우선 탐색을 사용하면 좋은 경우
    • 모든 경로를 탐색하고 결과를 확인해야 하는 경우
      • 문자열 등을 탐색할 때 "사전 순서로 앞에 오는 것"처럼 앞부터 검색해서 찾는 것이 빠를 경우
  • 너비 우선 탐색을 사용하면 좋은 경우
    • 시작 지점에서 가장 가까운 것을 구하고 싶은 경우
      • 탐색 범위 자체는 넓지만 어느 정도 근처에 구하고 싶은 해가 존재하는 것을 알고 있는 경우
      • 탐색 범위가 굉장히 넓으며 깊이 우선 탐색을 사용할 때는 스택이 대량으로 사용되는 경우
profile
안녕하세요

0개의 댓글