Search Algorithm

常见的搜索算法：记忆化搜索，迭代加深，meet in the middle，A* 和 IDA*

记忆化搜索

思想可以用来进行搜索到DP的优化

建一个备忘录memo[N][S] memo[i][j]表示在第i个点，状态为j时搜索结果。

或者memo[N] memo[i]表示第i个点，搜索结果。

上述备忘录初值memo[i]为0，说明该状态未被搜索。

P1278 单词游戏

他们轮流说出一个仅包含元音字母的单词，并且后一个单词的第一个字母必须与前一个单词的最后一个字母一致。

游戏可以从任何一个单词开始。任何单词禁止说两遍，游戏中只能使用给定词典中含有的单词。

游戏的复杂度定义为游戏中所使用的单词长度总和。

编写程序，求出使用一本给定的词典来玩这个游戏所能达到的游戏最大可能复杂度。

static int vis; //初始为0..0000(二进制表示下16个0) 说明任何字母都没有访问
static int[] memo[] = new int[N][1<<N]; //N=16 只有16个状态 用二进制表示
static int dfs(int c){
    if (memo[c][vis] != 0) return memo[c][vis];
    vis |= 1<<c; //开始访问第c个单词 把vis二进制第c位置1
    char next = s[c].charAt(s[c].length()-1);
    int res = 0;
    for (int i = 0;i < n;i++){
        //判断i有没有访问过 即看第i位是不是1 (不能写成 (vis&1<<i) == 1 )
        if ((vis>>i&1)==1 || s[i].charAt(0)!=next) continue;
        res = max(dfs(i), res);
    }
    vis &= ~(1<<c);//访问结束 把vis二进制第c位置0
    return memo[c][vis] = res+s[c].length();//记得更新备忘录
}

迭代加深

从小到大枚举答案所需步数，
然后在搜索时一旦超出这个步数就不再搜索。
根据搜索空间的一般规律，搜索的状态空间随着步数指数级增长。
这样我们的时间主要取决于最后一次搜索的时间，
DFS的缺点得到了一定程度的弥补。

迭代加深搜索使用范围:
1.在有一定的限制条件时使用（例如“如果能在1515步以内（包括1515步）到达目标状态，则输出步数“）。
2.题目中说输出所以解中的任何一组解。

static int[] res = new int[N];
public static void main(String[] args) throws Exception {
    res[1] = 1;
    if (n == 1) out.println(1); //特殊
    else{
        int deep = 2;//dfs深度从二开始递增
        while (!dfs(2, deep)) deep++; //不行的话就一直增
        for (int i = 1;i <= deep;i++) out.print(res[i]+" ");
        out.println();
    }
}
static boolean dfs(int c, int max){
    if (c==max+1) return res[c-1]==n;
    int pre = res[c-1];
    boolean s = false;
    for (int i = c-1;i >= 1 && !s;i--){
        int y = pre+res[i];
        if (y>pre && y<=n){
           res[c] = y;
           s |= dfs(c+1, max);
        }else break;
    }
    return s;
}

Addition Chains

meet in the middle

折半搜索，又称为meet-in-the-middle。其做法为将整个搜索的过程分为两部分，然后每部分分别进行搜索，最后将得到两个答案序列，再将答案序列进行合并，即可得到最终的答案。

我们知道，搜索的时间复杂度往往是指数级别的。

比如，在每一层搜索时，假如都有两种选择，那么其时间复杂度为 O(2ⁿ) 。当 n 较大时，往往会导致超时。此时，如果使用折半搜索，其时间复杂度将缩小为 O(2^n/2) + 合并时间复杂度) 。

所以当搜索范围n > 40以上时，可优先考虑。

合并常用策略：哈希表、排序加二分

世界冰球锦标赛

给出预算和每场比赛的票价，试求：如果总票价不超过预算，有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同。

static long money, ans;
static int len1, len2, len;
static long[] p = new long[N], sub1 = new long[1<<21], sub2 = new long[1<<21];
public static void main(String[] args) throws Exception {
    dfs(1, n/2, 0, sub1); //搜索前一半 把符合的结果存入 sub1[]
    len1 = len; len = 0;  //len就是前一半搜索结果的数量（记得清0）
    dfs(n/2+1, n, 0, sub2);//搜索后一半 把符合的结果存入 sub2[]
    len2 = len;
    Arrays.sort(sub1, 0, len1); 
    for (int i = 0;i < len2;i++){
        int l = 0, r = len1-1;
        long t = money-sub2[i];
        while (l <= r){
           int mid = l+r>>1;
           if (sub1[mid]>t) r = mid-1;
           else l = mid+1;
        }
        ans += l;
    }
    println(ans);
}
static void dfs(int cur, int max, long sum, long[] sub){
    if (sum > money) return;
    if (cur > max){ // 所有数都遍历完 存入sub[]数组
        sub[len++] = sum; return;
    }
    dfs(cur+1, max, sum+p[cur], sub); //每个数选和不选两种情况
    dfs(cur+1, max, sum, sub);
}

Balanced Cow Subsets G

A*

用啥A^*，IDA^*不香吗

IDA*

IDA^* = A^* + 迭代加深

IDA^* 是对结合迭代加深的DFS的优化。

本质上只是在BFS和DFS上加上了一个估价函数。 ```