알고리즘 5장 되추적 연습문제

소개글

"알고리즘 5장 되추적 연습문제"에 대한 내용입니다.

목차

없음

본문내용

2. n-여왕말 문제를 푸는 되추적 알고리즘(알고리즘 5.1)을 문제 사례가 n=8인 경우 적용시켜 보고, 그 실행과정을 단계별로 보이시오. 첫째 해답을 찾을 때까지 이 알고리즘이 만드는 가지친 상태 공간 트리를 그리시오.

이를 트리로 그리면 아래와 같다.

11. 알고리즘 5.3(n-여왕말 문제를 푸는 되추적 알고리즘에 대한 몬테칼로 추정치 구하기)을 구현하는 프로그램을 작성하고, n=8인 문제 사례에 20번 실행시켜서 20개 추정치의 평균을 구하시오.

위의 코드를 실행하면 아래와 같은 결과로 20개 추정치의 평균을 구할 수 있다.

<중 략>

17. 몬테칼로 알고리즘을 사용하여 부분집합의 합 구하기 문제를 푸는 되추적 알고리즘(알고리즘 5.4)의 효율을 추정하시오.

부분집합의 합 구하기 알고리즘이 검색하는 상태 공간트리에서 마디의 개수는 1+ 2+ 2^2 + 2^3 + ... + 2^n = 2^(n+1) -1 이다. 이를 몬테칼로 추정치 구하기 알고리즘을 사용하여 되추적 알고리즘의 효율을 추정하면 위의 코드와 같다.

참고 자료

없음