搜索-迭代加深搜索、IDA*算法

😀 Powerd By HeartFireY | 📕建议学习的前置知识：A* | ⛓关联的算法：DFS | 🔰参考自OIWIKI

一、迭代加深搜索 1.迭代加深搜索 简介

迭代加深是一种 每次限制搜索深度的 深度优先搜索(DFS)。

它的本质还是深度优先搜索，只不过在搜索的同时带上了一个深度 d d d，当 d d d 达到设定的深度时就返回，一般用于找最优解。如果一次搜索没有找到合法的解，就让设定的深度加一，重新从根开始。

这里不妨回想一下BFS搜索算法：这里我们要达到的目的都是寻求最优解，那么迭代加深搜索与BFS分别应用于什么样的场景呢？

我们知道 BFS 的基础是一个队列，队列的空间复杂度很大，当状态比较多或者单个状态比较大时，使用队列的 BFS 就显出了劣势。事实上，迭代加深就类似于用 DFS 方式实现的 BFS，它的空间复杂度相对较小。

当搜索树的分支比较多时，每增加一层的搜索复杂度会出现指数级爆炸式增长，这时前面重复进行的部分所带来的复杂度几乎可以忽略，这也就是为什么迭代加深是可以近似看成 BFS 的。

2.迭代加深搜索的基本步骤

一般我们会确定一个较小的深度放在全局变量上作为DFS深度限制并进行DFS。每进入一次DFS，就将当前的 d e e p + 1 deep + 1 deep+1，当大于全局设定的 l i m i t limit limit就返回。如果在搜索途中发现答案就可以进行回溯，同时再回溯的过程中可以记录路径。如果没有发现答案则返回到函数入口，增加深度限制 l i m i t limit limit，继续搜索。

3. 伪代码描述

IDDFS(u, d)
    if d > limit 
        return
    else for each edge (u, v)
            IDDFS(v, d + 1)
  	return

4.适用场景

在大多数的题目中，广度优先搜索还是比较方便的，而且容易判重。当发现广度优先搜索在空间上不够优秀，而且要找最优解的问题时，就应该考虑迭代加深搜索。

二、IDA*搜索 1.IDA*搜索 简介

建议先学习A*算法：

在A*算法中，我们介绍过A*是基于BFS进行优化的搜索算法，而IDA*则是基于DFS进行优化的搜索算法。但实际上，IDA*是基于A*算法实现的一种采用迭代加深搜索的算法。由于 IDA*改成了深度优先的方式，所以 IDA*更实用：

1. 不需要判重，不需要排序；
2. 空间需求减少。

2.伪代码

Procedure IDA_STAR(StartState)
Begin
  PathLimit := H(StartState) - 1;
  Succes := False;
  Repeat
    inc(PathLimit);
    StartState.g = 0;
    Push(OpenStack, StartState);
    Repeat
      CurrentState := Pop(OpenStack);
      If Solution(CurrentState) then
        Success = True
      Elseif PathLimit >= CurrentState.g + H(CurrentState) then
        For each Child(CurrentState) do
          Push(OpenStack, Child(CurrentState));
    until Success or empty(OpenStack);
  until Success or ResourceLimtsReached;
end;

3.优点/缺点 1).优点

1. 空间开销小，每个深度下实际上是一个深度优先搜索，不过深度有限制，而 DFS 的空间消耗小是众所周知的；
2. 利于深度剪枝。

2).缺点

重复搜索：回溯过程中每次 depth 变大都要再次从头搜索(其实，前一次搜索跟后一次相差是微不足道的)。

三、例题 1.DNA Sequence

Problem Description

The twenty-first century is a biology-technology developing century. We know that a gene is made of DNA. The nucleotide bases from which DNA is built are A(adenine), C(cytosine), G(guanine), and T(thymine). Finding the longest common subsequence between DNA/Protein sequences is one of the basic problems in modern computational molecular biology. But this problem is a little different. Given several DNA sequences, you are asked to make a shortest sequence from them so that each of the given sequence is the subsequence of it.

ACAGTGCTACGTATGCCGTTCAGT

For example, given “ACGT”,“ATGC”,“CGTT” and “CAGT”, you can make a sequence in the following way. It is the shortest but may be not the only one.

Input

The first line is the test case number t. Then t test cases follow. In each case, the first line is an integer n ( 1