검색어 입력폼

알고리즘 연습문제 3장

저작시기 2004.11 |등록일 2006.12.29 워드파일MS 워드 (doc) | 13페이지 | 가격 2,500원

소개글

알고리즘 연습문제 3장입니다

목차

5. 플로이드 알고리즘을 사용하여 행렬 D, 행렬 P를 구축하라.
- 문제 정의 : Adjacent Matrix 를 이용하여 shortest path 알고리즘을 작성하라.

20. 다음 아이템에 대하여 최적 이진검색 트리를 구축하여라.
CASE(0.05), ELSE(0.15), END(0.05), IF(0.35), OF(0.05), THEN(0.35). 괄호 안의 수는 각 단어가 나올 확률을 나타낸다.

26. 다음과 같이 행렬 W로 표현되어 있는 가중치포함 방향그래프에서 최적 회로를 구하라. 수행되는 절차를 단계별로 보여라.

본문내용

26. 다음과 같이 행렬 W로 표현되어 있는 가중치포함 방향그래프에서 최적 회로를 구하라. 수행되는 절차를 단계별로 보여라.

- vertice를 거치지 않을 때
D[V2][Ǿ] = 3
D[V3][Ǿ] = 4
D[V4][Ǿ] = 6
D[V5][Ǿ] = 10

- 한 개의 vertice를 거칠 때
D[V2][{V3}] = 7 + 4 = 11
D[V2][{V4}] = 8 + 6 = 14
D[V2][{V5}] = 10 + 10 = 20
D[V3][{V2}] = 11 + 3 = 14
D[V3][{V4}] = 10 + 6 = 16
D[V3][{V5}] = 7 + 10 = 17
D[V4][{V2}] = 6 + 3 = 9
D[V4][{V3}] = 7 + 4 = 11
D[V4][{V5}] = 11 + 10 = 21
D[V5][{V2}] = 6 + 3 = 9
D[V5][{V3}] = 2 + 4 = 6
D[V5][{V4}] = 1 + 6 = 7

- 두 개의 vertice를 거칠 때
D[V2][{V3.V4}] = (7+16, 8+11) = 19
D[V2][{V4.V5}] = (8+21, 10+7) = 17
D[V2][{V3.V5}] = (7+17, 10+6) = 16
D[V3][{V2.V4}] = (11+14, 10+9) = 19
D[V3][{V2.V5}] = (11+20, 7+9) = 16
D[V3][{V4.V5}] = (10+21, 7+7) = 14
D[V4][{V2.V3}] = (6+11, 7+14) = 17
D[V4][{V2.V5}] = (6+20, 11+9) = 20
D[V4][{V3.V5}] = (7+17, 11+6) = 17
D[V5][{V2.V3}] = (6+11, 2+14) = 16
D[V5][{V2.V4}] = (6+14, 1+9) = 10
D[V5][{V3.V4}] = (2+16, 1+11) = 12

참고 자료

Foundations of ALGORITHMS using c++ pseudocode
다운로드 맨위로