제 14강 해 탐색 알고리즘 (되추적, 저울문제, 0/1 배날 문제)

학습 목표 

1. 되추적 알고리즘의 개념을 이해할 수 있다.

2. 분기한정 알고리즘의 개념을 이해할 수 있다.

3. 유전 알고리즘의 개념을 이해할 수 있다.

 

주요용어

상태 공간 트리, 되추적 알고리즘, 분기한정 알고리즘, 한정값, 탐색공간, 유전알고리즘, 염색체, 개체군, 세대, 선택, 교차, 변이

 

8.1 되추적 알고리즘 

 

8.1.1 되추적 (backtracking) 기법의 원리

상태 공간 트리에서 해를 찾아다니다가 앞쪽에 더 이상 해가 없으면 왔던 길을 되돌아가서 다른 길을 찾아보는 방법

 

> 상태 공간 트리 state space tree 

 - 문제의 해를 만들어 가는 공간을 트리 형태로 나타낸 것

- 주어진 입력으로 만들어 낼 수 있는 모든 후보해를 리프 노드로 갖는 트리

  -> 루트 노드는 출발점, 각 리프 노드는 각 후보해, 내부 노드는 각 후보해를 만들어가는 부분 후보해

- 루트 노드로부터 리프 노드까지의 경로는 하나의 후보해를 만들어 가는 과정

 

> 출발점에서부터 깊이 우선 탐색으로 트리를 순회

  - 앞쪽 ( 자식 노드 )으로 갈 때에는 항상 해의 존재 가능성을 확인

        -> 해가 있을 수 없다면 더 이상 나아가지 않고 다른 자식 노드로 방향을 바꿈

 

(과정1) 루트 노드를 현위치 노드로 지정

(과정2) 현위치 노드의 각 자식 노드에 대해 과정을 반복

  a. 자식 노드 방향으로 해가 있을 수 없다면 ( 과정 2 )로 돌아가서 다음 자식 노드에 대해서 진행

  b. 자식 노드에 해가 있는 지 확인한 후 있다면 해를 출력

  c. 자식 노드를 현 위치 노드로 지정한 후 ( 과정2 )로 간다. (깊이 우선 탐색 )

(과정3) 부모 노드를 현위치 노드로 지정한 후 (과정 2 )로 돌아가서 다음 자식 노드에 대해서 진행

 

 

 

8.1.2 저울 문제

(1) 개념과 원리

> 양팔 저울과 1번부터 n번까지 n개의 추가 있고

각 추 i 의 무게를 Wi라고 가정할 때, 무게 M인 물체가

주어지면 이를 양팔 저울로 달 수 있는 지 판정하는 문제

 - n개의 추 중에서 추의 무게의 합이 M이 되도록

   선택할 수 있는 지 판정

  - 추는 한쪽 팔에만 올릴 수 있다.

 

> 자식 노드 방향으로 해가 있을 수 있는 지 확인하기 위한 정보

 

 - Ssum -> 현재까지 선탁한 추들의 무게의 합

 - Rsum -> 앞으로 고려할 추들의 무게의 합

 

   - 자식 노드의 Ssum >M

      → 이미 너무 많은 추를 선택한 것으로 그 방향으로의 더 이상의 탐색은 불필요

   - 자식 노드의 Ssum +자식 노드의 Rsum < M

      → 나머지 추를 모두 선택해도 M이 될 수 없으므로 그 방향으로의 더 이상의 탐색은 불필요

 

> 추의 무게가 7,8,5,3 인 경우의 상태 트리 공간의 Ssum과 Rsum

(3) 성능 분석 -> O (2^n)

- 탐색하는 노드의 수에 비례

- 상태 공간 트리는 높이 (n+1)인 포화 이진 트리 -> 노드의 개수 2^(n+1)-1

 

(4) 특징 

- 추와 물체의 무게에 아무런 제한이 없다.

   - 동적 프로그래밍 -> 추와 물체의 무게가 정수이면서 물체의 무게가 크지 않은 경우

- 실제 수행에서 해가 존재할 때에는 많은 경우 빠른 시간에 종료, 그러나 이를 보장하지는 못함

 

 

 

 

8.1.3 0/1 배낭 문제

(1) 개념과 원리 

> 물체를 쪼개서 넣을 수 없다는 가정하에 배낭의 용량을 초과하지 않는 범위 내에서

 배낭에 들어 있는 물체의 이익의 합이 최대가 되도록 물체를 넣는 방법을 찾는 문제

 

 - 최대 용량 M인 하나의 배낭,n개의 물체,물체 i의 무게 wi와 이익 pi

 - 최대가 물체의 이익의 합만 구하는 경우라고 가정

 

> 상태 공간 트리 

 - 각 레벨는 각 물체,각 노드의 자식 노드는 다음 물체의 선택 혹은 비선택 

 

- Ssum → 현재까지 선택한 물체의 무게의 합
- Psum → 현재까지 선택한 물체의 이익의 합 

- Rsum → 앞으로 고려할 물체의 이익의 합  

 

- Max → 현재까지 찾은 해

 - 최적화 문제이므로 별도의 해를 판정하기 위한 조건이 필요

   - Ssum ≤ M and Max < Psum

   - 하나의 해를 찾았더라도 더 좋은 해를 찾기 위한 탐색을 계속 진행

   - 자식 노드의 Ssum >M 또는 Psum + Rsum < Max  → 해당 자식 노드로의 탐색은 불필요

(3) 성능 분석

-  탐색하는 노드의 수는 되추적이 발생하지 않는 최악의 경우 O(2^n)

 

(4) 특징

- 오른쪽 자식 노드가 해인지 확인하는 과정은 생략 

  - 오른쪽 자식 노드의 Psum은 현재 노드의 Psum과 동일 

     → 오른쪽 자식 노드의 Psum이 Max보다 클 수가 없음

- 실제 수행에서는 탐색을 하지 않는 노드 수만큼 빠른 시간에 종료 

  - n이 커진다면 되추적 알고리즘도 느려짐