C++ 算法学习——1.7 迭代加深搜索

迭代加深搜索（Iterative Deepening Search）是一种搜索算法，优化了深度优先搜索（DFS），用于在树或图结构中找到目标节点。这种搜索算法通常用于具有较大搜索空间的问题，其中搜索树的分支非常多，而问题的答案在某个较浅的节点上。为尽量减少在无用分支上浪费的时间，可以使用迭代加深搜索。

工作原理

1. 逐层增加深度：迭代加深搜索从深度为1的节点开始，逐渐增加搜索深度，每次在上一次搜索深度的基础上再加深一层。

2. 深度优先搜索：在每一次增加深度的阶段，使用深度优先搜索来探索新的节点，直到达到当前设定的深度限制或者找到目标节点。

优点

• 节省内存: 与传统深度优先搜索不同，迭代加深搜索在每一次搜索时只需要保存当前搜索路径，而不需要保存整棵搜索树，因此可以节省内存空间。

• 完备性: 迭代加深搜索能够确保找到最优解（如果存在）并避免陷入无限深度的分支，因此具有一定的完备性。

缺点

• 重复搜索: 由于每次搜索都是从头开始，可能会导致一些节点被重复搜索，降低了搜索效率。

伪代码如下：

function IterativeDeepeningSearch(root):
    depth = 0
    found = false
    
    while not found:
        found = DepthLimitedSearch(root, depth)
        depth = depth + 1

function DepthLimitedSearch(node, depth):
    if depth == 0:
        if IsGoal(node):
            return true
        else:
            return false
    
    if depth > 0:
        if IsGoal(node):
            return true
        else if depth > 0:
            for each child of node:
                if DepthLimitedSearch(child, depth-1):
                    return true
    
    return false

C++代码实现：

#include <iostream>
#include <vector>

using namespace std;

bool isGoal(vector<int> node, int target) {
    // 检查节点是否为目标节点
    for (int value : node) {
        if (value == target) {
            return true;
        }
    }
    return false;
}

bool depthLimitedSearch(vector<int> node, int depth, int target) {
    if (depth == 0) {
        return isGoal(node, target);
    }

    if (depth > 0) {
        if (isGoal(node, target)) {
            return true;
        } else {
            // 这里假设每个节点的子节点为当前节点值加一
            for (int i = 0; i < node.size(); i++) {
                vector<int> child = node;
                child[i]++;
                if (depthLimitedSearch(child, depth - 1, target)) {
                    return true;
                }
            }
        }
    }

    return false;
}

void iterativeDeepeningSearch(vector<int> root, int target) {
    int depth = 0;
    bool found = false;

    while (!found) {
        found = depthLimitedSearch(root, depth, target);
        depth++;
    }

    if (found) {
        cout << "Target " << target << " found within depth " << depth - 1 << endl;
    } else {
        cout << "Target " << target << " not found within depth limit" << endl;
    }
}

 

 

原文地址：https://blog.csdn.net/William_Edmund/article/details/142919906

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！