11장. 조합 탐색 (1/2)

도입

• 완전 탐색 알고리즘은 대개 답을 만드는 과정을 여러 개의 선택으로 나눈 뒤, 재귀 호출을 이용해 각각의 선택지를 채워가는 형태로 구현됨
• 기존 완전 탐색은 모든 답을 다 만들어 보면서 문제를 해결하므로, 완전 탐색의 수행 시간은 탐색 공간의 크기에 직접적으로 비례
• 이는 문제의 규모에 따라 기하급수적으로 크기가 증가
• 조합 탐색: 완전 탐색을 포함해, 이렇게 유한한 크기의 탐색 공간을 뒤지면서 답을 찾아내는 알고리즘
• 모든 조합 탐색은 기본적으로 최적해가 될 가능성이 없는 답들을 탐색하는 것을 방지하여 만들어야 하는 답의 수를 줄이는 것을 목표
• 조합 탐색 최적화 기법
• 가지치기 기법
• 탐색 과정에서 최적해로 연결될 가능성이 없는 부분들을 잘라냄
• 지금까지 찾아낸 최적해보다 부분해가 이미 더 나빠졋다면 상태 마저 탐색하지 않고 종료
• 탐색의 순서를 바꾸거나 탐색 시작전에 탐욕법을 미리 수행하여 적당한 답을 찾는 것도 좋은 방법
• 가지치기와 함께 사용할 경우 탐색 효율이 증대

조합 탐색 기법들

외판원 문제

여러 도시들이 주어져 있고, 모든 도시들에 대한 가중치가 주어졌을때, 단일 시작점부터 시작해서 모든 도시를 단 한번씩만 방문하여 다시 시작점으로 돌아오는데 드는 최단 거리를 구하는 문제(NP-하드 문제)

조합 탐색 뼈대의 구현

/* TSP를 해결하는 완전 탐색의 구현(최적화가 되어 있지 않음)*/
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const double INF = 1e200;
const int MAX = 30;
int n; //도시의 수
double dist[MAX][MAX]; //두 도시간의 거리를 저장하는 배열
//지금까지 찾은 최적해
double best;
//path:지금까지 만든 경로
//visited:각 도시의 방문 여부
//currentLength: 지금까지 만든 경로의 길이
//나머지 도시들을 모두 방문하는 경로들을 만들어 보고 가능하면 최적해를 갱신한다.
void search(vector& path, vector& visited, double currentLength) {
	int here = path.back();
	//기저 사례: 모든 도시를 다 방문했을 때는 0번 도시로 돌아가고 종료한다.
	if (path.size() == n) {
		best = min(best, currentLength + dist[here][0]);
		return;
	}
	//다음 방문할 도시를 전부 시도해 본다.
	for (int next = 0; next < n; ++next) {
		if (visited[next]) continue;
		path.push_back(next);
		visited[next] = true;
		//나머지 경로를 재귀 호출을 통해 완성한다.
		search(path, visited, currentLength + dist[here][next]);
		visited[next] = false;
		path.pop_back();
	}
}
double solve() {
	//best를 매우 큰 값으로 초기화
	best = INF;
	vector visited(n, false);
	vector path(1, 0);
	visited[0] = true;
	search(path, visited, 0);
	return best;
}

찾아야할 경로의 첫 도시는 항상 0으로 고정했기 때문에 search()가 만드는 경로의 수는 (n-1)!개

- 소형 데이터인 경우 빠르지만 대형 데이터의 경우 시간이 기하급수적으로 늘어남

최적해보다 나빠지면 그만두기

가장 기초적인 가지치기 방법은 현재 최적해보다 나빠지는 경우 그만 두어서 시간을 효율적으로 사용하는 것을 말한다.

search() 함수에

if(best <=currentLength) return; 을 추가하여 해당 문제 해결

간단한 휴리스틱을 이용한 가지치기

• 가지치기 중 특정 부분에서 최적해가 나올 수 없다는 것을 일찍 파악하는 것이 매우 중요
• 휴리스틱을 이용한 가지치기
• 남은 조각들을 푸는 최적해를 찾기는 오래 걸리더라도, 이 값을 적당히 어림짐작하기는 훨씬 빠르게 할 수 있음.
• 휴리스틱 반환 값이 항상 정확하지 않을 수 있음(but, 가장 best한 답), 현재 부분 경로의 길이: length
• 길이가 best-length 미만이 경로로 남은 도시들을 모두 방문하도록 함. 이외의 경로는 전부 탐색 중단
• 휴리스틱은 어림짐작이기 때문에 잘못된 답을 도출해낼 수 있음
• 해결방법: 휴리스틱의 반환 값이 항상 남은 최단 경로의 길이 보다 작거나 같게 함.(과소평가 휴리스틱, 낙관적인 휴리스틱)

휴리스틱 함수 작성하기

• 휴리스틱의 값이 큰 경우 더 많은 가지를 칠 수 있음
• 방법
• 문제의 제약 조건을 일부 없앤 더 단순한 형태의 문제를 푸는 것
• TSP 변형
• 남은 도시를 모두 방문할 필요 없이, 가장 멀리 있는 도시 하나만 방문했다가 시작점으로 돌아가도 됨
• 남은 도시들을 방문하는 방법이 꼭 일렬로 연결된 형태가 아니어도 됨

단순한 휴리스틱 함수의 구현

solve()에서 각 도시마다 가장 가까운 도시까지의 거리를 미리 계산함.

/* 단순한 휴리스틱을 이용한 가지치기 구현*/

//각 도시에 인접한 간선 중 가장 짧은 것을 미리 찾아 둔다.
double minEdge[MAX];
//가장 단순한 형태의 휴리스틱
double simpleHeuristic(vector& visited) {
	double ret = minEdge[0]; // 마지막에 시작점으로 돌아갈 때 사용할 간선
	for (int i = 0; i < n; ++i)
		if (!visited[i])
			ret += minEdge[i];
	return ret;
}
void search(vector& path, vector& visited, double currentLength) {
	//단순한 휴리스틱을 이용한 가지치기
	if (best <= currentLength + simpleHeuristic(visited)) return;

	int here = path.back();
	//기저 사례: 모든 도시를 다 방문했을 때는 0번 도시로 돌아가고 종료한다.
	if (path.size() == n) {
		best = min(best, currentLength + dist[here][0]);
		return;
	}
	//다음 방문할 도시를 전부 시도해 본다.
	for (int next = 0; next < n; ++next) {
		if (visited[next]) continue;
		path.push_back(next);
		visited[next] = true;
		//나머지 경로를 재귀 호출을 통해 완성한다.
		search(path, visited, currentLength + dist[here][next]);
		visited[next] = false;
		path.pop_back();
	}
}

double solve() {
	//simpleHeuristic을 위한 초기화
	for (int i = 0; i < n; ++i) {
		minEdge[i] = INF;
		for (int j = 0; j < n; ++j)
			if (i != j) minEdge[i] = min(minEdge[i], dist[i][j]);
	}

	//best를 매우 큰 값으로 초기화
	best = INF;
	vector visited(n, false);
	vector path(1, 0);
	visited[0] = true;
	search(path, visited, 0);
	return best;
}

가까운 도시부터 방문하기

• TSP에서 도시들이 몇 개씩 뭉쳐있는 경우 멀리 있는 도시보다 가까운 도시를 먼저 방문하는 경우가 유리한 경우가 많음
• 도시들을 미리 정렬해서 저장한 후 계산

/*가까운 정점부터 방문하는 최적화 구현*/
//각 도시마다 다른 도시들을 가가운 순서대로 정렬해 둔다.
vectornearest[MAX];
void search(vector& path, vector& visited, double currentLength) {
	//단순한 휴리스틱을 이용한 가지치기
	if (best <= currentLength + simpleHeuristic(visited)) return;

	int here = path.back();
	//기저 사례: 모든 도시를 다 방문했을 때는 0번 도시로 돌아가고 종료한다.
	if (path.size() == n) {
		best = min(best, currentLength + dist[here][0]);
		return;
	}
	//다음 방문할 도시를 전부 시도해 본다.
	for (int i = 0; i < nearest[here].size(); ++i) {
		int next = nearest[here][i];

		if (visited[next]) continue;
		path.push_back(next);
		visited[next] = true;
		//나머지 경로를 재귀 호출을 통해 완성한다.
		search(path, visited, currentLength + dist[here][next]);
		visited[next] = false;
		path.pop_back();
	}
}

double solve() {
	//nearest 최기화
	for (int i = 0; i < n; ++i) {
		vector> order;
		for (int j = 0; j < n; ++j) {
			if (i != j)
				order.push_back(make_pair(dist[i][j], j));
		}
		sort(order.begin(), order.end());
		nearest[i].clear();
		for (int j = 0; j < n - 1; ++j)
			nearest[i].push_back(order[j].second);
	}

	//best를 매우 큰 값으로 초기화
	best = INF;
	vector visited(n, false);
	vector path(1, 0);
	visited[0] = true;
	search(path, visited, 0);
	return best;
}

지나온 경로를 이용한 가지치기

• 이제까지 만든 경로가 최적의 경로가 아닌 경우 남은 조각들에서 아무리 선택을 잘해봐야 최적해를 찾지 못하고 계속 탐색을 할 이유가 없음.

• 왼쪽에 있는 그림에서 3번째로 방문하는 도시와 4번째로 방문하는 도시의 순서를 바꾸면 오른쪽 그림처럼 된다.
  
• 오른쪽의 그림은 왼쪽의 그림보다 경로가 더 짧다.
• 따라서 탐색시 왼쪽 그림의 경로대로 따라가면 아무리 효율적으로 완성해 봐야 최적해가 될 수 없기 때문에 이 경우에는 탐색을 준단해도 된다.
• TSP에서는 이런 원리를 구현하기 위해 인접한 둘의 순서를 바꾸어 본 뒤 경로가 더 짧아지면 탐색을 중단하는 가지치기를 구현하는 것이 가능
• 기존 구간(p,a,b,q, here) -> 변경 구간(p,b,a,q,here)
• 이 때 p-q 구간의 거리가 더 짧아진다면 이 경로에서 최적해를 찾을 가능성이 없으니 탐색 중단

/*지나온 경로를 이용하는 두 가지 가지치기 전략의 구현 */
//path의 마지막 네 개의 도시 중 가운데 있는 두 도시의 순서를 바꿧을 때
//경로가 더 짧아지는지 여부를 반환한다.
bool pathSwapPruning(const vector& path){
  if(path.size() < 4) return false;
  int p = path[path.size() -4];
  int a = path[path.size() -3];
  int b = path[path.size() -2];
  int q = path[path.size() -1];
  return dist[p][a] + dist[b][q] > dist[p][b] + dist[a][q];
}
//시작 도시와 현재 도시를 제외한 path의 부분 경로를
//뒤집어보고 더 짧아지는지 확인한다.
bool pathReversePruning(const vector& path){
  if(path.size() < 4) return false;
  int b = path[path.size() -2];
  int q = path[path.size() -1];
  for(int i = 0; i + 3 < path.size(); ++i){
    int p = path[i];
    int a = path[i+1];
    //[.., p, a, b, q]를 [p, b, a, q]로 바꾸어 본다.
    if(dist[p][a] + dist[b][q] > dist [q][b] + dist[a][q])
      return true;
  }
  return false;
}

• pathSwapPruning()
• search() 함수 처음에 pathSwapPruning()을 수행 후 참이 들어오면 탐색 종료(이 때 모든 도시가 아닌 현재 도시 이전의 두 도시만 체크)
• 한 도시 뒤에 경로가 추가될 때마다 pathSwapPruning이 수행
• pathReversePruning()
• 전체 경로의 일부분을 통째로 뒤집는 것으로 일반화 가능
• (p,a,b,c,d,e,q,here) -> 길이가 5인 부분 경로(a,b,c,d,e)를 뒤집기 -> (p,e,d,c,b,a,q,here)
• 경로 자체의 길이는 똑같기 때문에 달라지는 것은 p와 q에 인접한 도시일 뿐
• q=here인 경우 현재 이전 도시에서 끝나는 경로들을 뒤집는 경우만을 고려

• 왼쪽 그림은 path가 서로 교차하는 것을 보여줌
  
• 오른쪽 그림은 교차된 선을 일직선으로 바꾸엇을 때를 보여줌
• 교차했을 때보다 더 짧아짐.
• pathReversePrunning은 모든 길이의 부분 경로를 뒤집어보기 때문에 이전 방법보다 더 많은 경우를 가지치기할 수 있음

MST 휴리스틱을 이용한 가지치기의 구현

• 추가적인 제약
• 한 간선은 최대 한 번만 선택 가능
• 선택하지 않은 간선을 모두 지웠을 때 그래프가 둘 이상으로 쪼개지면 안된다.
• 모든 정점들이 간선들로 이어져 있어야 한다.
• 최소 스패닝 트리(MST)
• 현재 위치에서 시작해서 아직 방문하지 않은 정점들을 모두 방문하고 시작점으로 돌아오는 최단 경로들도 스패닝 트리
• 최소 스패닝 트리의 가중치의 합은 항상 최단 경로보다 작음

/* MST 휴리스틱 구현 */
//상호 배타적 집합 자료 구조를 구현한다.
struct DisjointSet{
  //n개의 원소로 구성된 집합 자료 구조를 만든다.
 DisjointSet(int n);
  //here가 포함된 집합의 대표를 반환한다.
  int find(int here);
  //a가 포함된 집합과 b가 포함된 집합을 합친다.
  bool merge(int a, int b);
};
//모든 도시 간의 도로를 길이 순으로 정렬해 저장해 둔다.
vector>> edges;
//here와 시작점, 아직 방문하지 않은 도시들을 모두 연결하는 MST를 찾는다.
double mstHeuristic(int here, const vector& visited){
  //KnusKal;s MST
  DisjointSet sets(n);
double taken = 0;
for(int i = 0; i  visited(n, false);
	vector path(1, 0);
	visited[0] = true;
	search(path, visited, 0);
	return best;
}

마지막 단계 메모이제이션하기

• 조합 탐색 과정에서 같은 상태를 두 번 이상 맞닥뜨리는 것은 흔한 일
• 이런 비효율을 메모이제이션으로 제거한다면 더욱 효율적
• TSP의 경우 남은 도시가 5개 이하일때만 메모이제이션 실시(이유: 남은 도시가 20개이면 2천만개 이상의 상태를 저장해야함, 5개만 할경우 약 44만개)

/* 부분적으로 메모이제이션을 사용하는 최적화의 구현*/
//남은 도시의 수가 CACHED_DEPTH 이하면 동적 계획법으로 바꾼다.
const int CACHED_DEPTH = 5;
//dp(here, visited) = cache[here][남은 도시의 수][visited]
map cache[MAX][CACHED_DEPTH+1];
//here: 현재 위치
//visited: 각 도시의 방문 여부
//나머지 도시를 모두 방문 후 시작점으로 돌아가는 최단 경로의 길이를 반환
double dp(int here, int visited) {
  //기저 사례: 더 방문할 도시가 없으면 시작점으로 돌아간다.
  if(visited ==(1< 0) return ret;
  ret = INF;
  //다음 도시를 하나씩 시도한다.
  for(int next = 0; next < n; ++next) {
    if(visited & (1<^ path, int visited, double currentLength){
  //생략
  //기저 사례: 남은 도시 수가 CACHED_DEPTH 이하면 동적 계획법으로 바꾼다.
  if(path.size() + CACHED_DEPTH >= n) {
    best = min(best, currentLength + dp(path.back(), visited));
    return;
  }
  //생략
}
double solve() {
//생략
//cache 초기화
  for(int i = 0 ; i 

최종 비교

최적화	소형(n=12)	중형(n=16)	대형(n=20)	초대형(n=24)
동적 계획법	0.03초	0.58초	26.45초	768.21초
없음	89.74초	시간초과	시간초과	시간초과
최적해보다 나빠지면 그만두기	2.58초	981.53초	시간초과	시간초과
단순한 휴리스틱	0.85초	84.18초	시간초과	시간초과
가까운 도시부터 방문하기	00.52초	31.03초	시간초과	시간초과
인접한 두 도시 순서 바꾸는 가지치기	0.15초	4.64초	233.52초	시간초과
부분 경로 뒤집는 가지치기	0.07초	1.13초	33.29초	1160.81초
휴리스틱을 MST로 교체	0.06초	0.37초	14.77초	836.43초
메모이제이션	0.06초	0.28초	2.91초	25.24초

게임판 덮기 2 (난이도: 하)

• 문제 링크: https://algospot.com/judge/problem/read/BOARDCOVER2
• 문제 풀이
• 가능한 많은 흰 칸을 덮는 것이 목적
• 최적화 문제
• 아직 빈 칸 중에서 가장 윗 줄에 있는 칸을 찾아 이 칸을 어떻게 덮을지를 결정하고 게임판의 나머지 부분을 재귀 호출로 덮어 나감
• 같은 상태를 여러번 방문하는 것을 방지해 수행 속도를 빠르게 해야 함.
• 블록의 형태가 미리 정해져 있지 않기 때문에 입력받은 블록을 회전하고 각 칸의 상태 좌표를 계산하는 작업을 미리 수행해야 함.

/* 블록의 회전된 형태를 계산하고 상대좌표의 목록으로 변환하기 */
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

int boardH, boardW;
int covered[50][50];
vector board;
int blockSize;

// 블록의 각 회전된 형태를 상대 좌표의 목록으로 저장해 둔다
vector > > rotations;

// 2차원 배열 arr 을 시계방향으로 90도 돌린 결과를 반환한다
vector rotate(const vector& arr) {
	vector ret(arr[0].size(), string(arr.size(), ' '));
	for(int i = 0; i < arr.size(); i++)
		for(int j = 0; j < arr[0].size(); j++)
			ret[j][arr.size()-i-1] = arr[i][j];
	return ret;
}

// block 의 4가지 회전 형태를 만들고 이들을 상대 좌표의 목록으로 변환한다.
void generateRotations(vector block) {
	rotations.clear();
	rotations.resize(4);
	for(int rot = 0; rot < 4; rot++) {
		int originY = -1, originX = -1;
		for(int i = 0; i < block.size(); i++)
			for(int j = 0; j < block[i].size(); j++)
				if(block[i][j] == '#') {
					if(originY == -1) {
						originY = i;
						originX = j;
					}
					rotations[rot].push_back(make_pair(i - originY, j - originX));
				}
		// 블록을 시계 방향으로 90도 회전한다
		block = rotate(block);
	}
	// 4가지 회전 형태 중 중복이 있을 경우 이를 제거한다
	sort(rotations.begin(), rotations.end());
	rotations.erase(unique(rotations.begin(), rotations.end()), rotations.end());
	blockSize = rotations[0].size();
}

// (y,x) 를 (0,0) 으로 해서 cells 로 표현된 블록을 내려놓거나, 들어올린다.
// delta 가 1 이면 내려놓고, -1 이면 들어올린다.
// 블록이 검은 칸이나 다른 블록과 겹치거나 게임판 밖으로 나가면 false 를 반환한다.
bool set(int y, int x, const vector >& cells, int delta) {
	bool ok = true;
	for(int i = 0; i < cells.size(); i++) {
		int cy = y + cells[i].first, cx = x + cells[i].second;
		if(cy < 0 || cx < 0 || cy >= boardH || cx >= boardW)
			ok = false;
		else {
			covered[cy][cx] += delta;
			if(covered[cy][cx] > 1) ok = false;
		}
	}
	return ok;
}

int best;

// placed: 지금까지 놓은 블록의 수
// blanks: 남은 빈칸의 수
void search(int placed, int blanks) {
	// 빈칸 중 가장 윗줄 왼쪽에 있는
	int y = -1, x = -1;
	for(int i = 0; i < boardH; i++) {
		for(int j = 0; j < boardW; j++)
			if(covered[i][j] == 0) {
				y = i;
				x = j;
				break;
			}
		if(y != -1) break;
	}
	// 기저 사례: 게임판의 모든 칸을 처리한 경우
	if(y == -1) {
		best = max(best, placed);
		return;
	}

	// 가지치기
	int upperBound = blanks / blockSize + placed;
	if(upperBound <= best) return;

	// 이 칸을 덮는다
	for(int i = 0; i < rotations.size(); i++) {
		if(set(y, x, rotations[i], 1))
			search(placed+1, blanks - blockSize);
		set(y, x, rotations[i], -1);
	}

	// 이 칸을 덮지 않고 막아 둔다
	covered[y][x]++;
	search(placed, blanks - 1);
	covered[y][x]--;
}

int solve() {
	int blanks = 0;
	for(int i = 0; i < boardH; i++)
		for(int j = 0; j < boardW; j++)
			if(board[i][j] == '.')
				++blanks;
	best = 0;
	for(int i = 0; i < boardH; i++) {
		for(int j = 0; j < boardW; j++)
			covered[i][j] = (board[i][j] == '#' ? 1 : 0);
	}

	//clock_t begin = clock();
	search(0, blanks);
	//double elapsed = (clock() - begin) * 1.0 / CLOCKS_PER_SEC;
	//fprintf(stderr, "%d,%d,%.4lf\n", blanks, blockSize, elapsed);
	return best;
}

int main() {
	/*
	   ifstream inp("samples.txt");
	   int s;
	   set samples;
	   while(inp >> s) samples.insert(s);
	   */

	int cases;
	cin >> cases;
	for(int cc = 0; cc < cases; ++cc) {
		int blockH, blockW;
		cin >> boardH >> boardW >> blockH >> blockW;
		board.resize(boardH);
		vector block(blockH);

		for(int i = 0; i < boardH; i++)
			cin >> board[i];
		for(int i = 0; i < blockH; i++)
			cin >> block[i];
		/*
		   if(samples.count(cc)) {
		   fprintf(stderr, "%d %d %d %d\n", boardH, boardW, blockH, blockW);
		   for(int i = 0; i < boardH; i++)
		   fprintf(stderr, "%s\n", board[i].c_str());
		   for(int i = 0; i < blockH; i++)
		   fprintf(stderr, "%s\n", block[i].c_str());
		   }*/

		generateRotations(block);
		cout << solve() << endl;
	}
}