遡及アルゴリズムの理解

一、アルゴリズムの意味
遡及アルゴリズムはプローブ法とも呼ばれ,問題の解を系統的に探索する方法である.遡及アルゴリズムの基本構想は、暴力アルゴリズムの改善は、すべての経路を遍歴した上で、遡及(遡及)によって不可能な経路をスクリーニングし、効率を高めることである.
二、問題を解く手順:
1.問題の解を含む解空間を決定する.2.検索に適した方法で解空間を組織する.3.深さ優先法を利用して解空間を探索する.4.枝切り(拘束関数、限界関数)を使用して、解を生成できないサブ空間への移動を回避します.
三、アルゴリズムフレームワーク
 

bool constraint(int t){};//    
bool bound(int t){};//    

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); } 
　　　　}
 } 

 
四、例題
7-1サブセットと問題(50点)
集合S={x 1,x 2,...,xn}は正の整数集合であり、cは正の整数であり、サブセットと問題はSのサブセットS 1が存在するか否かを判定し、S 1中の要素の和をcとする.サブセットと問題を解く遡及法を設計してみる.
入力形式:
入力データの1行目には2つの正の整数nとcがあり、nはSのサイズを表し、cはサブセット和の目標値である.次の1行には、集合Sの要素を表すn個の正の整数がある.は、サブセット和のターゲット値です.次の1行には、集合Sの要素を表すn個の正の整数がある.
出力フォーマット:
出力サブセットと問題の解は、スペースで区切られ、最後の出力の後ろにスペースがあります.問題が解決しない場合は、「No Solution!」と出力します.
サンプルを入力:

5 10
2 2 6 5 4

出力サンプル:

2 2 6 

コード:

#include 
using namespace std;
int flag =0;
int s[100000];
int selec[100000];
int fin_selec[100000];

void backTrack(int target,int t,int sum ,int n){
    if(flag==1)return;
    if (t>=n) {
        if (sum == target) {
            for (int i=0; i) {
                fin_selec[i] = selec[i];
            }
            flag = 1;
            return;
        }
        return;
    }
    
    if (sum+s[t]<=target) {
        selec[t]=1;
        sum +=s[t];
        backTrack(target, t+1, sum, n);
        selec[t]=0;
        sum -= s[t];
    }
    selec[t] =0;
    backTrack(target, t+1, sum, n);
}

int main(){
    int n,target;
    cin>>n>>target;
    for (int i=0; i) {
        cin>>s[i];
        selec[i]=0;
        fin_selec[i]=0;
    }
    int sum=0;
    for (int i=0; i) {
        sum+=s[i];
        }
    if (sum<target) {
        cout<<"No Solution!"<<endl;
        exit(0);
    }
    backTrack(target, 0, 0, n);
    if (flag==1) {
        for (int i=0; i) {
//            cout<
            if (fin_selec[i]==1) {
                cout<" ";
            }
        }
    }else cout<<"No Solution!"<<endl;
    return 0;
}

 
五、まとめ
アルゴリズムに対する熟知が足りないため、細部に問題が発生し、思考が発散していないため、テンプレートが使いやすく、制約関数の限界関数の完備が問題全体の明確な構想である.