되추적

알고리즘 5 되추적

어떤 노드의 유망성 점검후, 유망하지 않으면 그 노드의 부모노드로 되돌아간 후 다른 자손노드를 검색.

깊이우선탐색 함.

-nQueens문제

cols[i] = i번째줄.

i = i번째 위치

상태공간트리 사용

유망성 확인. : 전혀 해답이 나올 가능성이 없는 노드는 유망하지 않음.

정확한 분석은, 확률적알고리즘 사용

-부분집합의 합 구하기 문제

원소들의 합이 W가 되는걸 구함.

집합의 원소들을 오름차순으로 정렬.

위에서부터 트리를 그린다.

좌로 내려갈땐, 해당 원소의 값을 더함.

우로 내려갈땐, 해당 원소의 값을 더하지 않음.

더하면, SumOfSubset(i+1,weight+w[i+1],total-w[i+1]);

안더하면, SumOfSubset(i+1,weight,total-w[i+1])

-m-색칠하기문제

인접한색이 되지 않도록 m가지 색으로 그래프 칠하기

트리를 그린다. 색에 번호를 매기고 색의 번호들이 트리를 따라 내려간다. 트리를 내려갈수록 v1,v2,v3에 그 색이 입혀짐.

-해밀토니안 회로

연결된 비방향성 그래프에서 한 노드를 출발해 모두 한번씩 경유해 다시 돌아오는 경로.

유망판단 : i번째노드는 i-1과 이웃해야함.

n-1노드는 0노드와 이웃해야함.

i번째 노드는 이전의 i-1개의 노드중 하나가 될 수 없음.

TSP는 경로들중 가장 짧은 경로.

해밀토니안 회로는 그냥 경로.