遡及法の一つ---アルゴリズムフレームワークと基礎zz

遡及法の一つ---アルゴリズムの枠組みと基礎
遡及法は実は検索アルゴリズムでもあり、解空間を簡単に検索することができます.遡及法の解題は、通常、1、問題に対して、解空間2を定義し、探索しやすい解空間構造を決定する3、深さ優先で解空間を探索し、探索中に剪断遡及法を行うことは、通常、解空間ツリー上で探索し、解空間ツリーには通常、サブセットツリーと配列ツリーがある.この2つの問題に対して、アルゴリズムのフレームワークは基本的に以下の通りである:遡及法でサブセットツリーの一般的なフレームワークを検索する:

void backtrack(int t){
  if(t > n) output(x);
  else{
    for(int i = f(n,t); i <= g(n,t);i++){
          x[t] = h(i);
          if(constraint(t) && bound(t)) backtrack(t+1);
     }
  }
}

ツリーを並べたアルゴリズムフレームワークを遡及法で検索するには、次の手順に従います.

void backtrack(int t){
  if(t > n) output(x);
  else{
    for(int i = f(n,t); i <= g(n,t);i++){
          swap(x[t],x[i]);
          if(constraint(t) && bound(t)) backtrack(t+1);
          swap(x[t],x[i]); 
    }
  }
}

ここで、f(n,t),g(n,t)は、現在の拡張ノードにおいて探索されていないサブツリーの先頭番号と終端番号を表し、h(i)は、現在の拡張ノードにおいて、x[t]のi番目のオプション値を表す.constraint(t)およびbound(t)は、現在の拡張ノードにおける制約関数および限界関数である.constraint(t)がtrueを返すと、現在の拡張ノードx[1:t]の値が制約条件を満たし、そうでなければ制約条件を満たさず、対応するサブツリーを減算することができる.bound(t)が返す値がtrueの場合、現在の拡張ノードx[1:x]で値を取るとターゲット関数が境界を越えず、backtrack(t+1)で対応するサブツリーをさらに検索する必要がある.遡及法を用いることは実質的に解空間を探索する方法を提供し,解空間を探索できる場合,最適または条件を満たす解を見つけることができることは明らかである.これは実行可能性の問題であり,効率は剪断関数によって低減できる.しかし,実際に解空間の構造が決定されると,時間的複雑度も大きく決定されるので,探索しやすい解空間を選択することが重要である.次に、2つの最も簡単な遡及問題を見てみましょう.彼らは2つの検索タイプの問題を代表しています.サブ集合問題と配列問題です.最初の質問:集合sのすべてのサブセット(空のセットを含まない)を求め、最初のフレームワークに従ってコードを書くことができます.

#include
using namespace std;

int s[3] = {1,3,6};
int x[3];
int  N = 3;
void print(){
   for(int j = 0; j < N; j++)
	if(x[j] == 1)
	   cout << s[j] << " ";
   cout << endl;
}

void subset(int i){
 	if(i >= N){
        print();
	    return;
	}

	x[i] = 1;//     
	subset(i+1);
	x[i] = 0;//     
	subset(i+1);
}

int main(){
  subset(0);
  return 0;
}

次に、2番目の問題を見てみましょう.配列の問題は、集合要素の全配列を求めます.2番目のフレームワークに従ってコードを書くことができます.

#include
using namespace std;

int a[4] = {1,2,3,4};
const int N = 4;

void print(){
	for(int i = 0; i < N; i++)
		   cout << a[i] << " ";
    cout << endl;
}

void swap(int *a,int i,int j){
  int temp;
  temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

void backtrack(int i){
	if(i >= N){
		print();
	}
	for(int j = i; j < N; j++){
		swap(a,i,j);
		backtrack(i+1);
		swap(a,i,j);
	}
}

int main(){
  backtrack(0);
  return 0;
}

この2つの問題は代表的で、実際には多くの問題がこの2つの問題から発展してきた.第1の問題は、すべての問題のサブセットを挙げ、これはすべての第1のタイプの基礎であり、第2の問題であり、すべての配列の方法を与え、これはすべての第2のタイプの問題の基礎である.この二つの問題を理解することは、遡及アルゴリズムの基礎である.次に、より簡単な問題を見てみましょう.整数集合sと整数sumは、suの要素の和がsumになるように、集合sのすべてのサブセットsuを求めます.この問題は明らかにサブセットの問題であり、最初のコードをこの問題のコードに簡単に修正することができます.

int sum = 10;
int r = 0;
int s[5] = {1,3,6,4,2};
int x[5];
int  N = 5;

void print(){
   for(int j = 0; j < N; j++)
	if(x[j] == 1)
	   cout << s[j] << " ";
   cout << endl;
}
void sumSet(int i){
	if(i >= N){
		if(sum == r) print();
	    return;
	}
	if(r < sum){//     
	  r += s[i];
	  x[i] = 1;
	  sumSet(i+1);
	  r -= s[i]; 
	}
	x[i] = 0;//     
	sumSet(i+1);
}

int main(){
  sumSet(0);
  return 0;
}