首页 书籍 深入浅出程序设计竞赛(进阶篇) 进阶搜索

# 迭代加深搜索

迭代加深搜索（Iterative Deepening Depth-First Search, IDDFS）是一种结合了深度优先搜索（DFS）和广度优先搜索（BFS）的优势的搜索算法。它通过逐步增加搜索深度的方式，实现了在保持空间效率的同时找到最短路径的目的。这种方法特别适合于解决状态空间巨大，但目标深度未知的搜索问题。

# 例子

假设有一个简单的树形结构，我们要找到从根节点到目标节点的最短路径。树的结构如下：

       A
     / | \
    B  C  D
   /|  |
  E F  G

目标是找到从 A 到 G 的最短路径。

# 迭代加深搜索步骤

  1. 深度限制为 1：首先，搜索深度设为 1，此时只搜索 A 的直接子节点 B、C、D。G 不在这个深度中，因此增加深度限制。
  2. 深度限制为 2：然后，搜索深度设为 2，这次会搜索到 E、F 和 G。当找到 G 时，搜索停止。

这个过程中，我们首先检查深度为 1 的所有节点，然后是深度为 2 的所有节点，直到找到目标。这样，我们即保证了找到最短路径，又避免了一次性加载整个状态空间，节省了内存。

# C++ 代码实现

下面是使用 C++ 实现迭代加深搜索的简单示例代码。我们将上述例子中的树形结构简化为图的搜索问题。

#include <iostream>
#include <vector>
#include <map>
using namespace std;
// 使用邻接表表示图
map<char, vector<char>> graph = {
    {'A', {'B', 'C', 'D'}},
    {'B', {'E', 'F'}},
    {'C', {'G'}},
    {'D', {}},
    {'E', {}},
    {'F', {}},
    {'G', {}}
};
bool DLS(char node, char goal, int limit) {
    if (node == goal) { // 检查当前节点是否是目标节点
        cout << node << " ";
        return true;
    }
    if (limit <= 0) return false; // 如果达到深度限制，则停止搜索
    
    for (auto child : graph[node]) { // 遍历节点的所有子节点
        if (DLS(child, goal, limit - 1)) {
            cout << node << " ";
            return true;
        }
    }
    return false;
}
bool IDDFS(char root, char goal, int maxDepth) {
    for (int depth = 0; depth <= maxDepth; depth++) {
        if (DLS(root, goal, depth)) {
            return true;
        }
    }
    return false;
}
int main() {
    char start = 'A', end = 'G';
    int maxDepth = 3;
    cout << "Searching from " << start << " to " << end << " within depth " << maxDepth << endl;
    if (!IDDFS(start, end, maxDepth)) {
        cout << "Path not found." << endl;
    } else {
        cout << "Path found." << endl;
    }
    return 0;
}
在这段代码中， IDDFS  函数尝试从起始节点到目标节点进行搜索，深度从 0 开始逐渐增加，直到最大深度 maxDepth 。 DLS （Depth-Limited Search，有深度限制的搜索）函数是实际执行搜索的函数，它会检查是否达到了目标节点或者深度限制。


# 双向搜索


双向搜索（Bidirectional Search）是一种在搜索空间中同时从初始状态和目标状态出发进行搜索的策略，直到两边的搜索相遇。这种方法通常用于图搜索算法中，尤其是在确定最短路径问题上，比单向搜索更为高效。其基本思想是，由于从起点到终点的搜索路径可能非常长，而从起点和终点同时开始搜索直到它们相遇，则可能大大减少需要探索的节点数。


# 基本原理


双向搜索的基本原理是同时进行两个搜索：一个从初始状态向目标状态搜索（正向搜索），另一个从目标状态向初始状态搜索（反向搜索）。这两个搜索交替进行，每次都扩展一层状态。当两个搜索 “相遇” 时，即发现了一个共同的状态，搜索停止。此时，从初始状态到共同状态的路径和从共同状态到目标状态的路径合并，形成了从初始状态到目标状态的完整路径。


# 优点


    

  • 效率高：在最理想的情况下，双向搜索的时间复杂度可以从单向搜索的 (O (bd)) 降低到 (O (b))，其中 (b) 是分支因子，(d) 是深度。
    • 

  • 空间节省：与单向搜索相比，双向搜索可能会使用更少的内存。
    • 



# 缺点


    

  • 实现复杂：需要同时维护两个搜索队列，并正确处理它们的相遇条件。
    • 

  • 路径重构困难：在搜索相遇时，需要额外的逻辑来正确地重构完整路径。
    • 



# 例子


假设有一个简化的迷宫问题，我们要找到从起点 S 到终点 T 的最短路径。迷宫可以用图的形式表示，每个节点代表一个位置，节点之间的边代表可以移动的路径。


为了简化问题，我们假设有一个图：


    S---A---B
         |   |
         C---D---T



我们的目标是找到从 S 到 T 的最短路径。


# 代码


#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <unordered_set>
using namespace std;
// 图的简单表示
map<char, list<char>> graph = {
    {'S', {'A'}},
    {'A', {'S', 'B', 'C'}},
    {'B', {'A', 'D'}},
    {'C', {'A', 'D'}},
    {'D', {'B', 'C', 'T'}},
    {'T', {'D'}}
};
// 执行单步 BFS
bool bfsStep(queue<char>& queue, unordered_set<char>& visited, map<char, char>& parents, char goal) {
    if (queue.empty()) return false;
    
    char current = queue.front(); queue.pop();
    
    for (char neighbor : graph[current]) {
        if (visited.find(neighbor) == visited.end()) {
            parents[neighbor] = current; // 记录父节点
            if (neighbor == goal) return true; // 如果找到目标，返回 true
            visited.insert(neighbor);
            queue.push(neighbor);
        }
    }
    return false;
}
// 双向 BFS
bool bidirectionalSearch(char start, char goal) {
    queue<char> qStart, qGoal;
    unordered_set<char> visitedStart, visitedGoal;
    map<char, char> parentsStart, parentsGoal;
    
    qStart.push(start); visitedStart.insert(start);
    qGoal.push(goal); visitedGoal.insert(goal);
    
    while (!qStart.empty() && !qGoal.empty()) {
        // 正向搜索
        if (bfsStep(qStart, visitedStart, parentsStart, goal)) return true;
        // 反向搜索
        if (bfsStep(qGoal, visitedGoal, parentsGoal, start)) return true;
        
        // 检查是否相遇
        for (char s : visitedStart) {
            if (visitedGoal.find(s) != visitedGoal.end()) {
                cout << "Path found: " << s << endl;
                return true;
            }
        }
    }
    
    return false;
}
int main() {
    char start = 'S', goal = 'T';
    if (!bidirectionalSearch(start, goal)) {
        cout << "Path not found." << endl;
    }
    return 0;
}
这段代码实现了一个简单的双向搜索。 bfsStep  函数执行单步广度优先搜索（BFS）， bidirectionalSearch  函数则管理双向搜索过程。注意，这里的实现主要关注双向搜索的基本思想，并没有包含完整路径重构的逻辑，这需要额外的步骤来根据 parentsStart  和 parentsGoal  映射重建完整路径。


请记住，虽然双向搜索在很多情况下都能提高效率，但它的实际性能还取决于具体问题的结构和数据。