AL - BackTracking

void dfs(node v){
	node u;
	visit v;
	for(each child u of v)
		dfs(u)
}

Promising

Non-Promising

• node that cannot lead a solution

void checknode(node v){
	node u;
	if(promising(v))
		if(there is a solution at v)
			write the solution;

		else
			for(each child u of v)
				checknode(v);
}

//Better Altorithm
void expand(node v){
	node u;
	for(each child u of v)
		if(promising(u))
			if(solution at u)
				write the solution;
		else
			expand(u);
}

차이점

• 유망한지 먼저 확인 후 방문한다

N-Queen

• n개의 퀸이 같은 가로(row), 세로(column), 대각선(diagonal)에 있지 않도록 위치시키는 문제.
• $n^2$의 위치 경우 중 n개를 특정해야 한다.
• 퀸 위치: (i,col[i])

bool promising(index i){
	index k;
	bool switch;
	
	k = 1; 
	switch=true;

	while(k<i && switch){
		// 같은 row에 있거나 대각선에 있는지 확인
		if (col[i]==col[k] || abs(col[i]-col[k]) == i-k)
			switch = false;
		k++;
	}
	return swtich;
}

void queens(index i){
	index j;
	if(promissing(i))
		if(i==n)
			cout<<col[1] through col[n];
		else
			for(j=1; j<=n; j++){
				col[i+1] = j;
				queen(i+1);
			}
}

**Monte Carlo Algorithms**

Sum-of Subsets

• 합이 W가 되는 부분 집합 구하기

• non-promising

  • $weight + w_{i+1} \gt W$
  • $weight + total \lt W$
    • $total = w_{i+1}+...+w_n$

bool promising(index i){
	return (weight+total >=W) && (weight==W || weight+w[i+1] <= W);
}

Graph Coloring

• 무방향그래프에서 인접하는 정점을 같은 색으로 칠하지 않으면서 m개의 색을 사용하여 칠하는 방법 찾기.

bool promising(index i){
	index j;
	bool switch;
	switch = true;
	j=1;
	
	while(j<i && switch){
		if(W[i][j] && vcolor[i] == vcolor[j]) //i j 가 연결되어 있고 가은 색일 때
			switch = false;
		j++;
	}
	return switch
}

0/1 KSP

Prunning

weight : level i 까지 weights의 합

profit : 그 node 까지 profits의 합

totweight = $weight + \sum_{j=i+!}^{k-1} w_j \le W \le totweight+w_k$

• 지금까지 weight에 미래 가능한 w를 더한다.

bound (upper, 가능한 최대 profit) = $(profit + \sum_{j=i+1}^{k-1} p_j) + (W- totweight)*\frac{p_k}{w_k}$

• 앞 : 지금까지 profit
• 뒤 : 남은 무게(Wk를 완전히 담지는 못하지만 가능한)만큼 k의 profit 추가

void knapsack(index i, int profit, int weight){
	if(weight <=W && profit > maxprofit){
		maxprofit = profit;
		numbest = i;
		bestset = include;
	}

	if(promising(i)){
		include[i+1] = "yes";
		knapsack(i+1, profit+p[i+1], weight + w[i+1]);
		include[i+1] "no";
		knapsack(i+1, profit, weight);
}

non-promising

• bound ≤ maxprofit
• weight ≥ W

bool promising(index i){
	index j,k; int totweight; float bound;	
	
	if(weight >= W)
		return false;
	else {
		j= i+1; bound = profit; totweight= weight;

		while(j<=n && totweight+w[j] <= W){
			totweight = totweight + w[j];
			bound = bound + p[j]; 
			j++;	
		}
		k = j;
		if(k<=n)
			bound = bound + (W-totweight)* p[k]/w[k];
		
		return bound>maxprofit;
	}
}