遡及法の概要

遡及法の概要
——共通の解題方法、最適化の窮挙法.
一、
質問に対して、その解セットを見つける必要がある場合、またはどの解に答えたときに条件を満たす最適な解を要求する場合.
基本的な方法:検索、または時に組織が整然としていて、検索を必要としない貧挙式検索法(枝切り)を避けることができます.
主な利用:深度遊先検索ポリシー
(1)再帰遡及
(2)反復遡及
(3)サブセットツリーアルゴリズムフレームワーク
(4)配列木アルゴリズムフレームワーク
二、直感的な印象:
(1)「汎用的な解題方法」は,すべての解または最適解を探索することができ,システムのジャンプ性のある探索アルゴリズムである.
(2)深さ優先探索解空間ツリー.まず,ノードに問題の解が含まれているかどうかを判断する.このサブツリーをスキップすることは含まれません.サブツリーの深さに入る優先検索も含まれます.
(3)すべての解,最適解を求める:ルートに遡り,ルートノードのすべてのサブツリーが探索された.任意の解を求めます:1つの解を探し当てるだけでいいです.
タスクの説明:
(1)問題の解空間を明確に定義し,各解を解ベクトルで表すことができる.
(2)解空間のすべての要素が問題の解であるわけではない.

存在性問題:(実行可能解)条件を満たす1つまたはすべてのメタグループを求め、返されないNo

最適化問題:(最適解)条件を満たし、目標関数を最大にするメタグループを求める.

枝切り関数-問題解決に必要なときに生成される状態ノード数を減らします.
①拘束関数:効率を高め、無駄な検索を避ける.
②限界関数:(最適化問題)最適ノードを含むことが不可能なサブツリーを切り取る.
問題の解空間:

解ベクトル:nメタ形式(x 1,x 2,x 3......xn)

明示的拘束:xi値の制限(リュックサックの問題ごとにxi=0/1)

暗黙的拘束:解を満たすために、異なる成分に適用される拘束(wiはリュックサック容量より小さい)

デスペース:明示的な制約を満たすすべてのベクトル.

 
三、問題を生成する基本的な方法:
1.

の3つの概念:

拡張ノード:息子を産んでいるノード

活結点:1つの自身はすでに生成して、息子はまだすべて

を生成していません

死の接点:すべての息子が生まれた接点.

2. 
1.深さ優先の問題状態生成法:
①拡張ノードRは、一度息子Cが生まれると、Cが新しい拡張ノードとなる.Rが活結点となる.
②サブツリーCの探索を窮めると,Cはデッドノードとなり,Rは拡張ノードとなる.Rは次の息子を生成し続ける.
2.幅優先の問題状態生成法:
拡張ノードがデッドノードになるまで、拡張ノードです.
3.遡及:
限界関数は条件を満たさないいくつかの活結点を処死する.
3.スペースツリーを解く:
1.サブセットツリー:解不定長
2.並べ木:長さを解く
 
四、基本思想と手順、コードフレームワーク:
有限離散問題はいつも窮挙法で問題のすべての解を求めることができる.
制約条件Dを満たす部分解(x 1,x 2,......xi)を求め,
①xi+1が存在する場合(x 1,x 2,......xi,xi+1)はDを満足させ、xi+2を追加し続ける.
②すべてのxi+1が満たされず、xiを取り除いて(x 1,x 2,......xi-1)に戻って続行する.
解題手順:
1与えられた問題に対して、問題の解空間を定義する.
2検索しやすい解空間構造を決定する.
3深さ優先で解空間を探索し,探索中に剪断関数で無効な探索を回避する.
複雑性:
h(n)は、ルートノードからリーフノードまでの最長距離である.
一つの解だけ:O(h(n))
すべての解:O(2^h(n))またはO(h(n)!)
コードフレーム:
1.遡及

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))//    &&    
                 backrtrack(t+1);    
        }
}

 2.反復遡及:

/*f(n,t) g(n,t)          ，                 */
void iterativeBacktrack(){
    int t=1;
    while(t>0){
        if(f(n,t)<=g(n,t))//        
            for(int i=f(n,t);i<=g(n,t);i++){//“    ”       
                x[t]=h(i)；
                if(constraint(t)&&bound(t)){//    &&    
                    if(solution(t)) 
                        output(x);//   ，  
                    else 
                        t++;
                }
            }
        else t--;//t      ，  
    }
}

3.サブセットツリーO(2^n)

void backtrack(int t){
    if(t>n) output(x);
    else
        for(int i=0;i<=1;i++){//      
            x[t]=i;
            if(legal(t)) backtrack(t+1);
        }
}

4.並木O(n!)

void backtrack(int t){
    if(t>n) output(x);
    else
        for(int i=t;i<=n;i++){//    i     t    
            swap(x[t],x[i]);
            if(legal(t)) backtrack(t+1)
            swap(x[t],x[i]);
        }
}