알고리즘 기초 연습문제 5장 해설

소개

1. 본 파일의 정답 및 해설은 공식 정답이 아닌 직접 풀어서 작성한 것이며 오타, 오답 및 프로그램에 버그가 존재할 수 있으므로 반드시 확인하시길 바랍니다.
2. 간단한 문제는 해설이 생략되었을 수 있습니다.
3. 프로그램의 설명은 주석을 참조하시길 바랍니다.
4. 작성자가 과제로 지정된 문제의 해설만을 작성한것으로 일부 문제가 누락되었을 수 있습니다. 본문내용의 포함된 문제를 반드시 확인하시길 바랍니다.

목차

2. n-여왕말 문제를 푸는 되추적 알고리즘(알고리즘 5.1)을 문제 사례가 n=8인 경우 ... 상태공간트리를 그리시오.
11. 알고리즘 5.3(n-여왕말 문제를 푸는 되추적 알고리즘에 대한 몬테칼로 추정치 구하기)을 구현하는 ... 평균을 구하시오.
13. 부분집합의 합 구하기 문제를 푸는 되추적 알고리즘(알고리즘 5.4)을 ... 모두 찾으시오.
17. 몬테칼로 알고리즘을 사용하여 부분집합의 합 ... 추정하시오.
18. m-색칠하기 문제를 푸는 되추적 알고리즘(알고리즘 5.5)을 사용하여 ... 단계별로 보이시오.
26. 해밀튼 회로 문제를 푸는 되추적 알고리즘(알고리즘 5.6)을 사용하여 ... 찾으시오.
33. 0-1 배낭 채우기 문제를 푸는 되추적 알고리즘(알고리즘 5.7)을 사용하여 ... 보이시오.
34. 0-1 배낭 채우기 문제를 푸는 되추적 알고리즘(알고리즘 5.7)을 ... 실행하시오.

본문내용

알고리즘 기초
5장. 되추적

문제 2.
동작 방식은 해당 위치의 유망성을 점검한 후 유망하지 않다고 판정되면
부모의 마디로 돌아가 다음 후손마디에 대한 검색을 계속한다.
이러한 과정을 반복해서 얻을 수 있는 결과값은 다음과 같다.

문제 11.
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#define TRUE 1
#define FALSE 0
#define MAX 8int col[MAX + 1] = { 0 };
int promising(int i);
int estimate_n_queens(int n);
void main()
{
int node = 0, total = 0;
srand(time(NULL)); //시간을 기준으로 난수를 초기화
for (int i = 0; i < 20; i++) //20회 반복
{
node = estimate_n_queens(MAX);
total += node;
printf("반복횟수 %d - 노드의 수: %d\n", i + 1, node);
}
printf("전체값: %d 평균값: %d\n", total, total / 20); //결과 출력
}
int promising(int i)
{
int k = 1;
int change = TRUE;
while (k < i && change)
{
if (col[i] == col[k] || abs(col[i] - col[k]) == i - k)
change = FALSE;
k++;
}
return change;
}
int estimate_n_queens(int n)
{
int i = 0, j, m = 1;
int numnodes = 1, mprod = 1;
int random;
while (m != 0 && i != n)
{
mprod = mprod * m;
numnodes = numnodes + mprod * n;
i++;
m = 0;......

<중 략>

참고자료

· 없음