알고리즘 기초 (Foundation of Algorithms) 5판, 5장 연습문제(2)

목차

없음

본문내용

18) m-색칠하기 문제를 푸는 되추적 알고리즘(알고리즘 5.5)을 사용하여 빨간색, 녹색, 흰색의 3가지 종류의 색을 가지고 아래 그래프를 색칠하는 모든 방법을 찾으시오. 실행절차를 단계별로 보이시오.

수준 1에서 정점 에 가능한 모든 색을 시도하고, 수준 2에서 정점 에 가능한 모든 색을 시도하고, 수준 6까지 반복 후 연결되는 정점을 확인하면서 가능한 것만을 남기고 나머지는 지운다.
A : 빨간색
B : 녹색
C : 흰색

26) 해밀튼 회로 문제를 푸는 되추적 알고리즘(알고리즘 5.6)을 사용하여 다음 그래프의 해밀튼 회로를 모두 찾으시오.

실행절차를 단계별로 보이시오.

경로 상의 i번째 정점은 그 경로 상의 i-1번째 정점과 이웃해야 하고, n-1번째 정점은 출발점과 이웃해야 한다.
을 출발 정점으로 지정한 후 유망한 가지들을 찾아가며 경로를 찾는다.

참고 자료

없음