dfs検索

貧挙法は,列挙法とも呼ばれ,可能な解の集合から各要素を一つ一つ列挙し,与えられた検査条件でどれが無用で,どれが役に立つかを判定する.命題をすぐに解くことができる.
窮挙法は本質的に検索アルゴリズムに属するが、彼は検索とは異なる.列挙法の解に適用される問題は満たさなければならないからだ.解の数を予め確定することができる.解変数の値範囲を予め決定する.
窮挙アルゴリズムの鍵は,まずループの範囲を決定し,次に判断解の条件を探し出すことである.この2つのキーを解決するには,窮屈なアルゴリズムで問題を解くのは簡単である.
探索アルゴリズムは窮挙法と類似しており,ループで書けない窮挙アルゴリズムに対しては再帰的またはキューを用いて解を実現する.検索のプロセスは検索ツリーを構成し、検索は実際には検索ツリーの遍歴である.
探索の順序は深さ優先探索(DFS)と広さ優先探索(BFS)の2種類に分けられる.ここで、深さ優先探索は、探索ツリーの深さに沿ってツリーのノードを遍歴し、できるだけ深くツリーの枝分かれを探索する.DFSは通常再帰的な方法で実現される.
広さは、拡張可能な各ノードを優先的に検索し、レイヤノードがすべて検索されると、最初の拡張可能なノードが拡張可能なすべてのノードを順次検索します.
検索の順序のほかに、盲目的な検索と啓発的な検索に分けられる検索方法もあります.
イニシアチブ検索は,検索過程に問題に関するイニシアチブ情報を加え,検索が最も有望な方向に進むよう指導し,不要な検索過程を除去し,問題解を加速させ最適解を得る.
啓発的探索の一般的なアルゴリズムはA*アルゴリズム,アナログアニーリングアルゴリズム,遺伝アルゴリズムなどがあり,我々が最もよく用いるのはA*アルゴリズムである.A*アルゴリズムの最も古典的な例は八数コード問題であり、状態関数hは目標位置に到達していない数字の個数に設定される.
再帰dfs n本の木の棒は全部で何個の異なる三角形をつづることができます

#include 
#include 
#include 
using namespace std;

int n,l[15];
//           
//              100 +      
bool h[10000];

//             
//        ，         0 ，           
//       
bool is_triangle(int a,int b,int c){
    return !h[a*100+b]&&a&&b&&c&&a+b>c&&a+c>b&&b+c>a&&(h[a*100+b]=true);   
}

//                
//      
int dfs(int index,int a,int b,int c){
    if(index==n){
        return areturn dfs(index+1,a+l[index],b,c)+dfs(index+1,a,b+l[index],c)+dfs(index+1,a,b,c+l[index]);
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=0;iscanf("%d",&l[i]);
        }
        memset(h,0,sizeof(h));
        printf("%d
",dfs(0,0,0,0));

    }
    return 0;
}

dfs例_コンパクト式0

#include 
using namespace std;
int n; //        N
bool opr[10]; //      bool      n-1   ，   true    "+"， false    "-"。
bool found = false; //          ，              "None"
// dfs  ，      ：deep      ，               ；sum           。
//        sum     0，       。            opr      。
void dfs(int deep, int sum) {
    //                  。
    if (deep == n) {
        if (sum == 0) {
            found = true;
            //            ，          。
            //        。
            for(int i=1;i<=n-1;i++){
                if(opr[i])
                    printf("%d+",i);
                else
                    printf("%d-",i);
            }
            printf("%d
",n);
        }
        return ;
    }
    //                。
    opr[deep] = true;
    dfs( deep+1, sum+deep+1);
    opr[deep] = false;
    dfs(  deep+1 , sum-deep-1  );
}

// main        ，  ~
int main() {
    while(scanf("%d",&n)!=EOF){
        found=false;
        dfs(1,1);
        if(found==false)
            printf("None
");
    }
    return 0;
}