Download presentation
Presentation is loading. Please wait.
1
Homework #5 (1/3) Backtracking, Branch-and-Bound 1. n-Queens 문제를 푸는 되추적 알고리즘을 n = 5인 경우 적용시키되, 두 개의 해답을 찾을 때까지 이 알고리즘이 만드는 가지 친 상태공간 트리를 그리시오. 2. m-Coloring 문제를 푸는 되추적 알고리즘을 사용하여, 빨간색, 노란색, 흰색의 세 가지 종류의 색을 가지고 아래 그래프를 색칠하는 가능한 모든 방법을 찾으시오. 실행절차를 단계별로 보이시오. v1 v2 v3 v4 v5
2
Homework #5 (2/3) Backtracking, Branch-and-Bound knapsack 문제의 breadth-first-search 알고리즘을 사용하여, 오른편 사례에 대한 이익을 최대화하시오. 알고리즘 수행 절차를 단계별로 보이시오. (단, W = 13이다.) i pi wi pi/wi 1 $20 2 10 $30 5 6 3 $35 7 4 $12 $3
3
Homework #5 (3/3) Due Date: 6/12(월) – 시험 보는 날
Backtracking, Branch-and-Bound 4. TSP 문제의 best-first-search 해결책을 사용하여, 다음 그래프에 대한 최적 여행경로와 그 경로의 길이를 구하시오. Due Date: 6/12(월) – 시험 보는 날 8 5 4 v1 v2 v3 4 5 1 6 v4 v5 v6 2 8 5
Similar presentations
![[Homework #3] [복습문제, p444~446]에서 다음 문제의 해답제시](/90/14589151/big_thumb.jpg "[Homework #3] [복습문제, p444~446]에서 다음 문제의 해답제시>")
