一起学习交流~

迷宫寻路算法-DFS和BFS

算法 laomuji 11个月前 (11-09) 381次浏览 已收录 0个评论

一、场景模拟

假设有一个地图

每行6列,一共5行,左上角为起点,右下角为终点,0为路,1为墙,走过的路标记为6

假如我们寻找的顺序是下,左,右,上(字典顺序,也可以是其它顺序,没有什么特别要求)

二、DFS Deep First Search

深度优先搜索,适用于内存较低的机器,优点是占用内存低

思想是按照指定的顺序一直走,直到遇到死路,进行回溯递归

数据如下

6 5
0 0 0 0 0 1
0 1 1 1 0 1
0 1 0 0 0 1
0 1 0 1 1 0
1 0 0 0 0 0

依次寻找顺序如下

6 0 0 0 0 1
0 1 1 1 0 1
0 1 0 0 0 1
0 1 0 1 1 0
1 0 0 0 0 0

6 0 0 0 0 1
6 1 1 1 0 1
0 1 0 0 0 1
0 1 0 1 1 0
1 0 0 0 0 0

6 0 0 0 0 1
6 1 1 1 0 1
6 1 0 0 0 1
0 1 0 1 1 0
1 0 0 0 0 0

6 0 0 0 0 1
6 1 1 1 0 1
6 1 0 0 0 1
6 1 0 1 1 0
1 0 0 0 0 0

6 6 0 0 0 1
6 1 1 1 0 1
6 1 0 0 0 1
6 1 0 1 1 0
1 0 0 0 0 0

6 6 6 0 0 1
6 1 1 1 0 1
6 1 0 0 0 1
6 1 0 1 1 0
1 0 0 0 0 0

6 6 6 6 0 1
6 1 1 1 0 1
6 1 0 0 0 1
6 1 0 1 1 0
1 0 0 0 0 0

6 6 6 6 6 1
6 1 1 1 0 1
6 1 0 0 0 1
6 1 0 1 1 0
1 0 0 0 0 0

6 6 6 6 6 1
6 1 1 1 6 1
6 1 0 0 0 1
6 1 0 1 1 0
1 0 0 0 0 0

6 6 6 6 6 1
6 1 1 1 6 1
6 1 0 0 6 1
6 1 0 1 1 0
1 0 0 0 0 0

6 6 6 6 6 1
6 1 1 1 6 1
6 1 0 6 6 1
6 1 0 1 1 0
1 0 0 0 0 0

6 6 6 6 6 1
6 1 1 1 6 1
6 1 6 6 6 1
6 1 0 1 1 0
1 0 0 0 0 0

6 6 6 6 6 1
6 1 1 1 6 1
6 1 6 6 6 1
6 1 6 1 1 0
1 0 0 0 0 0

6 6 6 6 6 1
6 1 1 1 6 1
6 1 6 6 6 1
6 1 6 1 1 0
1 0 6 0 0 0

6 6 6 6 6 1
6 1 1 1 6 1
6 1 6 6 6 1
6 1 6 1 1 0
1 6 6 0 0 0

6 6 6 6 6 1
6 1 1 1 6 1
6 1 6 6 6 1
6 1 6 1 1 0
1 6 6 6 0 0

6 6 6 6 6 1
6 1 1 1 6 1
6 1 6 6 6 1
6 1 6 1 1 0
1 6 6 6 6 0

6 6 6 6 6 1
6 1 1 1 6 1
6 1 6 6 6 1
6 1 6 1 1 0
1 6 6 6 6 6

深度搜索极端情况下速度会很慢,但是占用内存较小

三、BFS Breadth  First Search

广度优先搜索,速度快,但是占用内存较高

思想就是用队列,每次取出队列最前面的数据,把这个数据的所有可到达的位置压入队列

这种方法找到的路径是最短的,因为是按照队列的方式,

离起点的距离

先进队列的数据一定小于等于后进队列的数据

数据如下

6 5
0 0 0 0 0 1
0 1 0 1 0 1
0 1 0 0 0 1
0 1 0 1 1 0
0 0 0 0 0 0

依次寻找顺序如下

6 0 0 0 0 1
0 1 0 1 0 1
0 1 0 0 0 1
0 1 0 1 1 0
0 0 0 0 0 0

6 0 0 0 0 1
6 1 0 1 0 1
0 1 0 0 0 1
0 1 0 1 1 0
0 0 0 0 0 0

6 6 0 0 0 1
6 1 0 1 0 1
0 1 0 0 0 1
0 1 0 1 1 0
0 0 0 0 0 0

6 6 0 0 0 1
6 1 0 1 0 1
6 1 0 0 0 1
0 1 0 1 1 0
0 0 0 0 0 0

6 6 6 0 0 1
6 1 0 1 0 1
6 1 0 0 0 1
0 1 0 1 1 0
0 0 0 0 0 0

6 6 6 0 0 1
6 1 0 1 0 1
6 1 0 0 0 1
6 1 0 1 1 0
0 0 0 0 0 0

6 6 6 0 0 1
6 1 6 1 0 1
6 1 0 0 0 1
6 1 0 1 1 0
0 0 0 0 0 0

6 6 6 6 0 1
6 1 6 1 0 1
6 1 0 0 0 1
6 1 0 1 1 0
0 0 0 0 0 0

6 6 6 6 0 1
6 1 6 1 0 1
6 1 0 0 0 1
6 1 0 1 1 0
6 0 0 0 0 0

6 6 6 6 0 1
6 1 6 1 0 1
6 1 6 0 0 1
6 1 0 1 1 0
6 0 0 0 0 0

6 6 6 6 6 1
6 1 6 1 0 1
6 1 6 0 0 1
6 1 0 1 1 0
6 0 0 0 0 0

6 6 6 6 6 1
6 1 6 1 0 1
6 1 6 0 0 1
6 1 0 1 1 0
6 6 0 0 0 0

6 6 6 6 6 1
6 1 6 1 0 1
6 1 6 0 0 1
6 1 6 1 1 0
6 6 0 0 0 0

6 6 6 6 6 1
6 1 6 1 0 1
6 1 6 6 0 1
6 1 6 1 1 0
6 6 0 0 0 0

6 6 6 6 6 1
6 1 6 1 6 1
6 1 6 6 0 1
6 1 6 1 1 0
6 6 0 0 0 0

6 6 6 6 6 1
6 1 6 1 6 1
6 1 6 6 0 1
6 1 6 1 1 0
6 6 6 0 0 0

6 6 6 6 6 1
6 1 6 1 6 1
6 1 6 6 0 1
6 1 6 1 1 0
6 6 6 0 0 0

6 6 6 6 6 1
6 1 6 1 6 1
6 1 6 6 6 1
6 1 6 1 1 0
6 6 6 0 0 0

6 6 6 6 6 1
6 1 6 1 6 1
6 1 6 6 6 1
6 1 6 1 1 0
6 6 6 0 0 0

6 6 6 6 6 1
6 1 6 1 6 1
6 1 6 6 6 1
6 1 6 1 1 0
6 6 6 6 0 0

6 6 6 6 6 1
6 1 6 1 6 1
6 1 6 6 6 1
6 1 6 1 1 0
6 6 6 6 0 0

6 6 6 6 6 1
6 1 6 1 6 1
6 1 6 6 6 1
6 1 6 1 1 0
6 6 6 6 6 0

6 6 6 6 6 1
6 1 6 1 6 1
6 1 6 6 6 1
6 1 6 1 1 0
6 6 6 6 6 0

6 6 6 6 6 1
6 1 6 1 6 1
6 1 6 6 6 1
6 1 6 1 1 0
6 6 6 6 6 6

四、代码

#include<iostream>
#include<string>
#include<queue>

//测速
#include<Windows.h>
template<typename F>
double getTime(F func)
{
    LARGE_INTEGER freq_;
    QueryPerformanceFrequency(&freq_);
    LARGE_INTEGER begin_time;
    LARGE_INTEGER end_time;
    QueryPerformanceCounter(&begin_time);
    func();
    QueryPerformanceCounter(&end_time);
    double ns_time = (end_time.QuadPart - begin_time.QuadPart) * 1000000.0 / freq_.QuadPart;
    return ns_time;
}

using namespace std;
//棋盘
int nums[100][100] = {0};

class MapData
{
public:
    int x;
    int y;
    int step;
    string path;
    MapData(int x, int y, int step, const string& path, char ch = 0)
    {
        this->x = x;
        this->y = y;
        this->step = step;//拷贝步数
        this->path = path;//拷贝路径
        if(ch)this->path.push_back(ch);//把方向放进去
    }

};

//breadth  first search 广度搜索优先,遍地开花,占用内存较高,速度快
string BFS(int w, int h, int beginX, int beginY, int endX, int endY)
{
    string path;//存放最短路径
    queue<MapData>que;
    que.push(MapData(beginX, beginY, 0, ""));
    while (que.size())
    {

        MapData tempData = que.front();
        que.pop();
        //标记当前位置,避免重复
        if (nums[tempData.y][tempData.x] == 0)nums[tempData.y][tempData.x] = 6;

        //如果到了终点,停止
        if ((tempData.x == endX) && (tempData.y == endY))
        {
            cout << "最短步数:" << tempData.step << endl;
            cout << "最短路径:" << tempData.path << endl;
            path = tempData.path;
            break;
        }
        //按照字典顺序
        if ((tempData.x < w && tempData.y + 1 < h) && (nums[tempData.y + 1][tempData.x] == 0))
            que.push(MapData(tempData.x, tempData.y + 1, tempData.step + 1, tempData.path, 'D'));

        if ((tempData.x - 1 >= 0 && tempData.y < h) && (nums[tempData.y][tempData.x - 1] == 0))
            que.push(MapData(tempData.x - 1, tempData.y, tempData.step + 1, tempData.path, 'L'));

        if ((tempData.x + 1 < w && tempData.y < h) && (nums[tempData.y][tempData.x + 1] == 0))
            que.push(MapData(tempData.x + 1, tempData.y, tempData.step + 1, tempData.path, 'R'));

        if ((tempData.x < w && tempData.y - 1 >= 0) && (nums[tempData.y - 1][tempData.x] == 0))
            que.push(MapData(tempData.x, tempData.y - 1, tempData.step + 1, tempData.path, 'U'));
    }
    return path;
}

//depth first search 深度搜索优先,朝着一个方向递归回溯,占用内存较低,速度慢
int DFS(int w, int h, MapData tempData, int endX, int endY)
{
    int isFind = 0;
    nums[tempData.y][tempData.x] = 6;//防止回头路

    //如果到达终点直接返回
    if (tempData.x == endX && tempData.y == endY)
    {
        cout << "深搜路径:" << tempData.path << endl;
        return 1;
    }

    //按照字典排序 如果不需要排序无所谓
    if (isFind == 0 && (tempData.x < w && tempData.y + 1 < h) && (nums[tempData.y + 1][tempData.x] == 0))
        isFind = DFS(w, h, MapData(tempData.x, tempData.y + 1, tempData.step + 1, tempData.path, 'D'), endX, endY);

    if (isFind == 0 && (tempData.x - 1 >= 0 && tempData.y < h) && (nums[tempData.y][tempData.x - 1] == 0))
        isFind = DFS(w, h, MapData(tempData.x - 1, tempData.y, tempData.step + 1, tempData.path, 'L'), endX, endY);

    if (isFind == 0 && (tempData.x + 1 < w && tempData.y < h) && (nums[tempData.y][tempData.x + 1] == 0))
        isFind = DFS(w, h, MapData(tempData.x + 1, tempData.y, tempData.step + 1, tempData.path, 'R'), endX, endY);

    if (isFind == 0 && (tempData.x < w && tempData.y - 1 >= 0) && (nums[tempData.y - 1][tempData.x] == 0))
        isFind = DFS(w, h, MapData(tempData.x, tempData.y - 1, tempData.step + 1, tempData.path, 'U'), endX, endY);

    return isFind;
}

int main() 
{
/*
6 5
0 0 0 0 0 1
0 1 0 1 0 1
0 1 0 0 0 1
0 1 0 1 1 0
0 0 0 0 0 0

6 5
0 0 0 0 0 1
0 1 1 1 0 1
0 1 0 0 0 1
0 1 0 1 1 0
1 0 0 0 0 0

50 30
0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 1 0
0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1 0 1 0 0 1 0 1
0 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1
0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0
1 1 0 0 1 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1
0 0 0 1 1 0 1 1 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0
0 0 1 1 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 0 1
1 1 0 0 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0 0
0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1
1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 1
1 0 1 0 1 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 1 1 0 1 0 0 0 0 1 0 0 0
1 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 0 0 1
1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0
1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 1 0 0 1
0 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 1 0 1 0 1 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1 0 1
1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0
0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1
1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 1 0 1 0 0 0 0 1
0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1
1 0 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 0 1 0
0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0
1 1 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 1 1 1 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 1 0 1 0 0 0
0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 1 0 0 1 1
1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0
1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 0 0
0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1
1 0 0 0 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 0 0 0
*/
    int w, h;

    cin >> w >> h;
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            cin >> nums[i][j];
        }
    }
    cout << endl;
    //cout << getTime([&]() {BFS(w, h, 0, 0, w - 1, h - 1); }) << endl;
    //cout << getTime([&]() {DFS(w, h, MapData(0, 0, 0, ""), w - 1, h - 1); }) << endl;
    BFS(w, h, 0, 0, w - 1, h - 1);
    //DFS(w, h, MapData(0, 0, 0, ""), w - 1, h - 1);
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            cout<< nums[i][j]<<" ";
        }
        cout << endl;
    }
    cout << endl;
    return 0;
}
喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论