9. Coping with NP-completeness

NP-완전이라는 걸 증명했다고 끝이 아니다.

9.1. Intelligent exhaustive search

9.1.1. Backtracking

백트래킹을 통해 NP-완전 문제의 풀이 공간을 효율적으로 탐색할 수 있다.

9.1.2. Branch-and-bound

SAT 외 다른 NP-완전 최적화 문제에도 적용할 수 있따.

9.2. Approximation algorithm

백트래킹을 쓸 수 없는 문제에는 근사 알고리즘을 써야 한다.

9.2.1. Vertex cover

정점 덮개 문제의 경우 다항 시간 2-근사 알고리즘이 존재한다.

9.2.2. Clustering

클러스터링 문제의 경우에도 다항 시간 2-근사 알고리즘이 존재한다.

9.2.3. TSP

여행하는 외판원 문제에도 다항 시간 근사 알고리즘이 존재한다.

General TSP

하지만 거리 함수가 삼각부등식을 만족하지 않는다면 이것도 불가능하다.

9.2.4. Knapsack

이산 배낭 문제에도 다항 시간 2-근사 알고리즘이 존재한다.

9.2.5. The approximability hierarchy

다항 시간 근사 알고리즘이 존재할 수 있고 존재하지 않을 수도 있다. 여러 클래스가 존재한다.

9.3. Local search heuristics

국소적 탐색 휴리스틱을 알아보자.

9.3.1. Traveling salesman, once more

여행하는 외판원 문제에는 거리 함수가 삼각부등식을 만족하면 다항 시간 근사 휴리스틱을 쉽게 생각해낼 수 있다.

9.3.2. Graph partitioning

그래프 분할도 비슷한 휴리스틱이 가능하다.

9.3.3. Dealing with local optima

Randomization and restarts

국소적 해에 대응하는 방법은 무작위로 여러 번 재시작하는 것이다.

Simulated annealing

아니면 시뮬레이트된 담금질 기법을 이용할 수도 있다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중