Ch 07. NP-완전 문제 (2)

7.3 NP-완전 문제 종류

1) SAT(충족 가능성 문제)

• 논리식 여러 개 -> 논리식 모두 만족하는 부울 변수 값 찾기

2) 부분 집합의 합

• 정수 집합 S 원소 합이 K가 되는 S의 부분 집합 찾는 문제
  • S = {20, 30, 40, 80, 90}, 합 200 되는 부분 집합?
  • {30, 80, 90}

3) 분할

• 정수 집합 S 분할해서 원소 합 같은 부분 집합 찾기
  • S = {20, 30, 40, 80, 90}, 합 같은 부분 집합?
  • {20, 30, 80} / {40, 90}

4) 0-1 배낭문제

• 배낭 용량 C, 배낭에 담을 수 잇는 물건의 최대 가치 찾기
• 물건 쪼갤 수 없다!
• 무조건 큰 무게부터 담기 X, 가치 비교

5) 정점 커버

• 간선 양 끝점 중에서 적어도 1개 점 포함하는 점 집합
• 모든 선분 커버 가능한 최소 정점 찾기

6) 독립 집합

• 그래프에서 서로 연결하는 간선이 없는 점들의 집합
• 최대 크기의 독립 집합 찾기

7) 클리크

• 모든 점들 사이를 연결하는 간선 있는 부분 그래프

8) 그래프 색칠하기

• 인접한 점들을 서로 다른 색으로 색칠
• 가장 적은 수의 색 사용

9) 집합 커버

• 부분집합 합집합하여 S와 같게 되는 부분 집합들
• 최소 부분집합 커버 찾기

10) 최장 경로

• 가장 긴 경로 찾기
• 반복되는 점 없어야

11) 여행자 문제

• 출발점에서 다른 모든 점 1번씩만 방문, 다시 출발점으로 복귀
• 최단 경로 찾는 문제
• 시작점으로 돌아오지 않고 끝나더라고 계산 복잡도는 달라지지 않는다.
• 해밀턴 순환과 유사

12) 해밀턴 사이클

• 간선 가중치 모두 같거나 가중치 없을 때의 여행자 문제

13) 통 채우기

• n개의 물건, 통 용량 모두 C
• 최소 개수의 통 사용하여 n개 물건 채우기

14) 작업 스케줄링

• 모든 작업이 가장 빨리 종료되도록 작업을 기계에 배정하는 문제

변환 가능!

• 부분집합 합 문제 -> 분할 문제
• 0-1 배낭 -> 부분 집합의 합
• 정점 커버 -> 독립 집합
• 정점 커버 -> 집합 커버
• 독립 집합 -> 클리크
• 그래프 색칠하기 -> 클리크

7.4 NP-완전 문제 활용

• 강의자료 및 교재 참조(중요하지 않은 부분 같음)