算法分析

• 问题：在爆搜过程中，存在很多搜索深度很深的情况，而答案却在深度很浅的部分，如何避开搜索高深度，找到在浅深度的答案？

• 这里引用的是迭代加深的搜索方法，通过限制搜索深度的方法，提高搜索效率
  具体限制方式:在搜索某一个高深度的过程中，当当前深度u 大于 限制深度depth时，则需要立即停止该方向的搜索

在加成序列中，给定一个数n，通过1、2、4、8、16、32、64、128的方式可知只需要logn层就能搜出答案，
而在另外的搜索顺序顺序中，如1、2、3、4、5…方式中则需要n层搜出答案，因此在所有的搜索顺序中，则出现搜索深度差别巨大的情况，从而可以使用迭代加深的优化方式

• 1、优化搜索顺序：优先枚举较大的数

• 2、排除等效冗余：

  • 在搜索当前层的数时，搜索过的数不会再搜，st集合存储在该层该数是否被搜过

  • 按组合数的方式枚举

参考文献

算法提高课

Java 代码

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main{
    static int N = 110;
    static int n ;
    static int[] path = new int[N];
    static boolean dfs(int u,int depth)
    {
        //超出限制深度，停止
        if(u > depth) return false;
        //找到答案
        if(path[u - 1] == n) return true;
        Set<Integer> st = new HashSet<Integer>();

        for(int i = u - 1;i >= 0;i --)
        {
            for(int j = i;j >= 0;j --)//按组合数的方式枚举
            {
                int s = path[i] + path[j];
                if(s <= path[u - 1] || st.contains(s) || s > n) continue;

                st.add(s);
                path[u] = s;

                if(dfs(u + 1,depth)) return true;
            }
        }
        return false;
    }
    public static void main(String[] args)  {
        Scanner scan = new Scanner(System.in);
        path[0] = 1;
        while(true)
        {
            n = scan.nextInt();
            if(n == 0) break;
            int depth = 1;
            //从第1层开始，最大层是第depth层
            while(!dfs(1,depth)) depth ++;
            for(int i = 0;i < depth;i ++) System.out.print(path[i] + " ");
            System.out.println();
        }
    }
}