문제 목표 n개의 도시로 판매 출장을 계획하고 있는 외판원이 각 도시를 한 번씩 방문하고, 다시 출발한 도시로 돌아오는 가장 짧은 여행길을 찾는 것. --> 최단 경로 문제 --> 출발한 도시로 다시 돌아오는 부분에서 해밀턴 회로와 동일한 개념. 이 문제는 weighted, directed graph이다. 각 도시에서 도시로 가는 비용이 있고, 방향이 정해져 있다.(여기서 비용은 음이 아닌 정수로 가정한다) 만약 v1을 출발점으로 잡는다면 가능한 경로와 그에 비용은 아래와 같다. [v1->v2->v3->v4->v1] = 22 [v1->v3->v2->v4->v1] = 26 [v1->v3->v4->v2->v1] = 21 v1에서 출발할때의 최적의 경로는 [v1->v3->v4->v2->v1]이고 그 비용은 2..
되추적 알고리즘을 이용한 0-1 배낭 채우기를 앞에서 해보았다. 이번에는 분기한정을 이용한 0-1 배낭 채우기를 해보겠다. 되추적 알고리즘과 어떤 차이가 있는지를 중점으로 보면 될 것이다. -앞선 문제와 동일하게 n= 보석의 개수 W= 배낭의 용량 n=4, W=13 p(profit)=[40,30,50,10], w(weight)=[2,5,10,5], p/w(단위 무게별 이익)=[20,6,5,2] 1. 앞선 0-1 배낭 채우기 문제와 같이 무게별 이익이 큰 순서대로 재 정렬한다. 2. 되추적 알고리즘과 상태 공간 트리를 구성한다. 3. 트리는 (profit, totweight, bound)로 이루어진다. profit은 내가 가방에 담은 이익 totweight은 내가 가방에 담은 무게 bound는 내가 탐색한..
Branch & Bound(분기 한정) 알고리즘은 Backtracking(되추적) 알고리즘을 개선한 알고리즘이다. 차이점 트리횡단방법에 구애받지 않음. 최적화 문제를 푸는데 만 쓰인다. 분기 한정 알고리즘은 어떤 마디가 유망한 지를 결정하기 위해서 그 마디에서 한계값을 계산한다. 이 한계값은 그 마디 아래로 확장하여 구할 수 있는 해답 값의 한계(Bound)를 나타낸다. 그 한계값이 찾은 최고 해답 값보다 더 좋지 않으면 그 마디는 유망하지 않다.(nonpromisin), 그 한계값이 찾은 최고 해답 값보다 더 좋으면 유망하다.(promising) 분기 한정 알고리즘은 마디들의 한계값을 비교하여 그중에서 가장 좋은 한계값을 가진 마디의 자식 마디를 방문한다.(유망도가 높은 자식을 방문함). --> 되추적..
문제 n * m 체스보드에서 기사의 여행 문제를 해결하는 백트래킹 알고리즘을 구현하시오. Knight's Tour 문제는 해밀턴 경로(path)와 해밀턴 회로(circuit, cycle)를 찾는 문제로 구분할 수 있다. 해밀턴 회로는 출발 정점과 무관하게 회로의 수를 구할 수 있고, 해밀턴 경로는 출발 정점에 따라 가능한 경로의 수가 달라짐에 유의하시오. 입력 첫 번째 줄에 체스보드의 크기 n(행의 크기)과 m(열의 크기)이 주어진다. 두 번째 줄에 출발 정점의 개수 T가 주어진다. 이후로 T개의 출발정점이 i(row), j(col)의 쌍으로 주어진다. 출력 첫 번째 줄에 해밀턴 회로의 개수를 출력한다. 두 번째 줄부터 입력에서 주어진 출발정점 각각에 대해 해밀턴 경로의 수를 한 줄에 하나씩 출력한다. ..
문제 교재와 강의자료를 참고하여 0-1 배낭 문제를 해결하는 Algorithm 5.7을 완성하시오. 단, 문제의 입력은 단위무게당 이익순으로 정렬되어 있지 않음에 유의하시오. 또한, 알고리즘의 출력은 알고리즘의 실행 단계별로 상태 공간 트리의 각 노드에서의 상태를 출력해야 함에 주의하시오. 입력 첫번째 줄에 아이템의 개수 n과 배낭의 무게 W가 주어진다. 두 번째 줄에 n개의 아이템 무게 w [i]가 주어진다. 세 번째 줄에 n개의 아이템 이익 p [i]가 주어진다. 출력 첫 번째 줄부터 한 줄에 하나씩 상태공간트리를 방문하는 노드의 상태를 출력하시오. 노드 상태는 다음과 같은 순서로 출력한다. i weight profit bound maxprofit 상태를 출력하는 순서는 Algorithm 5.7의 노..
문제 교재의 내용과 강의자료를 참고하여 0-1 배낭 문제를 해결하는 알고리즘의 구현을 완성하시오. 강의자료에서 knapsack2() 또는 knapsack3()를 참조할 것. 단, 입력값은 단위 무게당 이익의 순서로 정렬되어 있지 않음에 유의하시오. 또한, 알고리즘 실행 결과의 출력은 알고리즘의 실행 과정에서 결과 테이블 P에 저장한 무게(i) 또는 이익(j)이 0이 아닌 모든 항목 P[i][j]를 (i, j)의 오름차순으로 모두 출력한다는 것에 주의하시오. 입력 첫 번째 줄에 아이템의 개수 n이 주어진다. 두 번째 줄에 n개의 무게 w[i]가 주어진다. 세 번째 줄에 n개의 이익 p[i]가 주어진다. 네 번째 줄에 배낭 무게의 개수 T가 주어진다. 이후로 T개의 줄에 한 줄에 하나씩 배낭 무게 W가 주어..
문제 주어진 무방향 무가 중치 그래프 G = (V, E)에서 해밀턴 회로의 개수를 출력하시오. Algorithm 5.6을 구현할 때, 출발 정점은 1로 간주한다는 것을 주의하시오. 입력 첫째 줄에 정점의 개수 n과 간선의 개수 m이 주어진다. 둘째 줄부터 m개의 간선이 주어진다. 출력 첫째 줄에 해밀턴 회로의 개수를 출력한다. 문제 해석 이 문제를 풀기 위해서는 해밀턴 회로와 해밀턴 경로의 차이를 알아야 한다. 해밀턴 회로 VS 해밀턴 경로 해밀턴 회로 한 정점에서 출발을 해 모든 정점을 딱 한 번씩 방문하고 다시 출발 정점으로 돌아와야 한다. 출발 정점과 해밀턴 회로는 무관하다. 해밀턴 경로 해밀턴 경로는 해밀턴 회로와 다르게 출발 정점에 따라 값이 다르다. 한 정점에서 출발해서 모든 정점을 한 번씩 ..
문제 주어진 평면 그래프 G = (V, E)에 대해서 인접한 지역을 서로 다른 색으로 색칠하기 위해 필요한 최소 색의 수 m의 값과 해당하는 m의 값으로 색칠할 수 있는 경우의 수를 출력하시오. 단, 그래프의 입력은 간선의 집합으로 주어지고, 주어진 그래프는 평면 그래프라고 가정해도 된다. 입력 첫 줄에 정점의 수 n과 간선의 수 k가 주어진다. 둘째 줄부터 k개의 간선이 주어진다. 출력 첫째 줄에 색칠 가능한 최소의 m값을 출력한다. 둘째 줄에 해당 m값으로 색칠할 수 있는 경우의 수를 출력한다. 문제 해석 그림과 같이 인접해 있는 영역끼리는 서로 다른 색을 칠해야 한다. 여기서 인접한다의 의미는 영역들끼리 가로 세로중 하나라도 맞닿아있어야 한다. v1과 v3, v2는 가로 세로 중 한 영역이 맞닿아있..
문제 n개의 원소를 가진 정수의 집합 S가 주어지고, 임의의 정수 W가 주어졌을 때, 합이 W가 되는 부분집합의 개수와 각 부분집합을 출력하도록 하시오. 입력 첫 줄에 원소의 개수 n과 임의의 정수 W가 주어진다. 둘째 줄에 n개의 정수가 주어진다. 출력 첫 줄에 원소의 합이 W가 되는 부분집합의 개수를 출력한다. 둘째 줄부터 원소의 합이 W가 되는 모든 부분집합을 한 줄에 하나씩 출력한다. 단, 부분집합에서의 원소 출력 순서는 주어진 S의 원소 순서와 동일해야 한다. (백트래킹 순서대로) ※처음 문제를 보고 떠오른 생각 주어진 집합 S의 원소들을 더해서 W를 만들어야 한다. Backtracking을 이용해서 모든 경우의 수를 구한다. 유망성검사를 통해서 가지치기를 함. 만약 뽑은 원소들의 합이 W면 종..
