当前位置： 首页 > article >正文

C++ 算法学习——1.3 双向深度优先搜索

article 2024/10/19 23:16:58

双向深度优先搜索（Bidirectional Depth-First Search）是一种图搜索算法，旨在通过从起始节点和目标节点同时开始，沿着深度优先搜索的路径向前探索，以减少搜索空间并提高搜索效率。

1. 基本原理

  • 双向深度优先搜索同时从起始节点和目标节点开始搜索，通过交替地在两个方向上进行深度优先搜索，直到两个搜索路径相遇。

2. 算法步骤

  1. 初始化两个空的栈，一个用于从起始节点开始的搜索，另一个用于从目标节点开始的搜索。
  2. 将起始节点和目标节点分别推入两个栈。
  3. 从两个栈中分别出栈一个节点，进行如下操作：
    • 标记节点为已访问。
    • 检查当前节点是否在两个搜索方向上相遇，如果相遇则搜索结束。
    • 否则，对当前节点的未访问邻居节点进行处理：
      • 对于起始节点搜索方向，将未访问的邻居节点推入起始栈。
      • 对于目标节点搜索方向，将未访问的邻居节点推入目标栈。
  4. 重复步骤3，直到两个栈中的节点相遇或者两个栈都为空。

3. 优缺点

  • 优点：
    • 相较于单向深度优先搜索，双向深度优先搜索在搜索空间较大时能够更快地找到目标节点。
  • 缺点：
    • 需要额外的内存空间来维护两个搜索方向的栈。
    • 在特定情况下可能会比单向搜索更慢，例如在目标节点附近的情况。

代码示例（邻接表表示的图）：

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>

using namespace std;

// 无权图的邻接表表示
vector<vector<int>> graph;

// 双向深度优先搜索函数
bool bidirectionalDFS(int start, int target) {
    stack<int> startStack, targetStack;
    unordered_set<int> startVisited, targetVisited;

    startStack.push(start);
    targetStack.push(target);

    while (!startStack.empty() && !targetStack.empty()) {
        int currentStart = startStack.top();
        int currentTarget = targetStack.top();

        startStack.pop();
        targetStack.pop();

        startVisited.insert(currentStart);
        targetVisited.insert(currentTarget);

        // 检查是否相遇
        if (startVisited.count(currentTarget) || targetVisited.count(currentStart)) {
            cout << "Nodes met at: " << (startVisited.count(currentTarget) ? currentTarget : currentStart) << endl;
            return true;
        }//对于std::unordered_set和std::unordered_map，count函数会返回1（存在）或0（不存在）。

        // 处理邻居节点
        for (int neighbor : graph[currentStart]) {
            if (!startVisited.count(neighbor)) {
                startStack.push(neighbor);
            }
        }

        for (int neighbor : graph[currentTarget]) {
            if (!targetVisited.count(neighbor)) {
                targetStack.push(neighbor);
            }
        }
    }

    cout << "Nodes did not meet." << endl;
    return false;
}

代码示例（矩阵模样，起点坐标begina,beginb,目标点坐标enda,endb）：

#include <iostream>
#include <stack>
#include <unordered_set>
using namespace std;
int n,m;
char** board;
void showcurboard()
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        cout<<board[i][j];
        cout<<endl;
    }
}
struct PairHash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1, T2> &pair) const {
        auto hash1 = std::hash<T1>{}(pair.first);
        auto hash2 = std::hash<T2>{}(pair.second);
        return hash1 ^ hash2;
    }
};
// 双向深度优先搜索函数
bool bidirectionalDFS(int begina, int beginb, int enda, int endb) {
    stack<pair<int, int>> startStack, targetStack;
    unordered_set<pair<int, int>,PairHash> startVisited;
    unordered_set<pair<int, int>,PairHash> targetVisited;

    startStack.push({begina, beginb});
    targetStack.push({enda, endb});

    while (!startStack.empty() && !targetStack.empty()) {
        auto currentStart = startStack.top();
        auto currentTarget = targetStack.top();

        startStack.pop();
        targetStack.pop();

        startVisited.insert(currentStart);
        targetVisited.insert(currentTarget);

        // 检查是否相遇
        if (startVisited.count(currentTarget) || targetVisited.count(currentStart)) {
            return true;
        }

        // 处理邻居节点
        int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (auto dir : dirs) {
            int nextStartA = currentStart.first + dir[0];
            int nextStartB = currentStart.second + dir[1];
            if (nextStartA >= 0 && nextStartA < n && nextStartB >= 0 && nextStartB < m &&
                !startVisited.count({nextStartA, nextStartB})) {
                startStack.push({nextStartA, nextStartB});
            }

            int nextTargetA = currentTarget.first + dir[0];
            int nextTargetB = currentTarget.second + dir[1];
            if (nextTargetA >= 0 && nextTargetA < n && nextTargetB >= 0 && nextTargetB < m &&
                !targetVisited.count({nextTargetA, nextTargetB})) {
                targetStack.push({nextTargetA, nextTargetB});
            }
        }
    }
    return false;
}

int main()
{
    cin>>n>>m;
    board=new char*[n];
    for(int i=0;i<n;i++)
    {
        board[i]=new char[m];
        for(int j=0;j<m;j++) cin>>board[i][j];
    }
    showcurboard();
    return 0;
}

P1. b3625迷宫寻路 

#include <iostream>
#include <stack>
#include <unordered_set>
using namespace std;
int n,m;
char** board;
void showcurboard()
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        cout<<board[i][j];
        cout<<endl;
    }
}
struct PairHash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1, T2> &pair) const {
        auto hash1 = std::hash<T1>{}(pair.first);
        auto hash2 = std::hash<T2>{}(pair.second);
        return hash1 ^ hash2;
    }
};
// 双向深度优先搜索函数
bool bidirectionalDFS(int begina, int beginb, int enda, int endb) {
    stack<pair<int, int>> startStack, targetStack;
    unordered_set<pair<int, int>,PairHash> startVisited;
    unordered_set<pair<int, int>,PairHash> targetVisited;

    startStack.push({begina, beginb});
    targetStack.push({enda, endb});

    while (!startStack.empty() && !targetStack.empty()) {
        auto currentStart = startStack.top();
        auto currentTarget = targetStack.top();

        startStack.pop();
        targetStack.pop();

        startVisited.insert(currentStart);
        targetVisited.insert(currentTarget);

        // 检查是否相遇
        if (startVisited.count(currentTarget) || targetVisited.count(currentStart)) {
            return true;
        }

        // 处理邻居节点
        int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (auto dir : dirs) {
            int nextStartA = currentStart.first + dir[0];
            int nextStartB = currentStart.second + dir[1];
            if (nextStartA >= 0 && nextStartA < n && nextStartB >= 0 && nextStartB < m &&
                !startVisited.count({nextStartA, nextStartB})&&board[nextStartA][nextStartB]=='.') {
                startStack.push({nextStartA, nextStartB});
            }

            int nextTargetA = currentTarget.first + dir[0];
            int nextTargetB = currentTarget.second + dir[1];
            if (nextTargetA >= 0 && nextTargetA < n && nextTargetB >= 0 && nextTargetB < m &&
                !targetVisited.count({nextTargetA, nextTargetB})&&board[nextTargetA][nextTargetB]=='.') {
                targetStack.push({nextTargetA, nextTargetB});
            }
        }
    }
    return false;
}

int main()
{
    cin>>n>>m;
    board=new char*[n];
    for(int i=0;i<n;i++)
    {
        board[i]=new char[m];
        for(int j=0;j<m;j++) cin>>board[i][j];
    }
    //showcurboard();
    bool ans=bidirectionalDFS(0,0,n-1,m-1);
    if(ans) cout<<"Yes";
    else cout<<"No";
    return 0;
}


http://www.kler.cn/news/356490.html

相关文章：

  • 将一个单向链表插入到一个循环链表尾部
  • vue element upload取消上传后终止请求
  • 滑铁卢大学大模型公开课资料来了，大模型入门到精通，非常详细收藏我这一篇就够了
  • OpenCV之换脸技术：一场面部识别的奇妙之旅
  • PHP 函数 func_num_args() 的作用
  • spring boot 集成 dynamic-datasource-spring-boot-starter
  • 如何通过AI情侣头像项目日入1000+：详细教程揭秘
  • 推荐？还是踩雷？3款中英互译软件大盘点，你真的选对了吗？
  • 时装购物|基于springBoot的时装购物系统设计与实现(附项目源码+论文+数据库）
  • 【计网笔记】数据链路层
  • Java实现简单的5阶m序列密钥生成
  • 《Linux服务与安全管理》| 磁盘与文件系统管理
  • linux jdk环境变量变量新配置方式
  • 哔​哩​哔​哩​一​面
  • CVTE Android面试题及参考答案（100道题）
  • python-django-mysql原生sql增删改查搭建搭建web项目
  • 在 WPF 中使用 OpenTK：从入门到进阶
  • GS-SLAM论文阅读--GSORB-SLAM
  • Debug-029-el-table实现自动滚动分批请求数据
  • R语言从多波段tif数据中逐个提取单波段数据