Homework #5 (1/3)

(1)

Computer Algorithms by Yang-Sae Moon Page 1

Backtracking, Branch-and-Bound

1. n-Queens 문제를 푸는 되추적 알고리즘을 n = 5 인 경우 적용시키되 , 두 개의 해답을 찾을 때까지 이 알고리즘이 만드는 가지 친 상태공간 트 리를 그리시오 .

2. m-Coloring 문제를 푸는 되추적 알고리즘을 사용하여 , 빨간색 , 노란 색 , 흰색의 세 가지 종류의 색을 가지고 아래 그래프를 색칠하는 가능한 모든 방법을 찾으시오 . 실행절차를 단계별로 보이시오 .

v₁ v₂ v₃

v₄ v₅

(2)

3. 0-1 knapsack 문제의 breadth-first-search 알고리즘을 사용하여 , 오른편 사례에 대한 이익을 최대화하시오 . 알고리즘 수행 절차를 단계별 로 보이시오 . ( 단 , W = 13 이다 .)

i p_i w_i p_i/w_i

1 $20 2 10

2 $30 5 6

3 $35 7 5

4 $12 3 4

5 $3 1 3

(3)

4. TSP 문제의 best-first-search 해결책을 사용하여 , 다음 그래프에 대 한 최적 여행경로와 그 경로의 길이를 구하시오 .

v₁ v₂ v₃

v₄ v₅ v₆

5 4

8

5 4

1

2 8

6 5