深度优先搜索 - 最短路径

news/2025/2/4 11:48:36/

深度优先搜索 - 最短路径

在这里插入图片描述

迷宫由 n 行 m 列的单元格组成 (n 和 m 都小于等于 50)，每个单元格要么是空地，要么是障碍物。障碍物是不能通行的，要求从迷宫起点开始找到一条通往迷宫中目标位置的最短路径。

使用一个二维数组来存储迷宫，刚开始假设从迷宫入口处 (1, 1) 开始，目标位置在 (ph, qw)，找到从 (1, 1) 到 (ph, qw) 的最短路径。如果刚开始在入口的点 (1, 1)，那么下一步只能是往右走或者往下走。如果是到了迷宫中间的某个点，那么可能是往上、下、左和右四个方向走，只能一个个去尝试。这里定义一个顺序，按照顺时针的方向逐个尝试 (即按照右、下、左、上的顺序)。

在这里插入图片描述

从迷宫入口处 (1, 1) 开始，一步之内可以达到的点只有 (1, 2) 和 (2, 1)。根据刚才的策略，我们先往右边走，来到 (1, 2) 这个点。来到 (1, 2) 之后只能到达 (2, 2) 这个点。因为 (1, 3) 是障碍物无法到达，(1, 1) 是刚才来的路径中已经走过的点，也不能走，所以只能到 (2, 2) 这个点。但是目标位置并不在 (2, 2) 这个点上，所以还得继续往下走，直至无路可走或者找到目标位置为止。请注意，并不是找到目标位置就结束了。刚才仅仅尝试了一条路，而这条路并不一定是最短的。刚才很多地方在选择方向的时候都有多种选择，因此我们需要返回到这些地方继续尝试往别的方向走，直到把所有可能都尝试一遍，最后输出最短的一条路径。下图就是一种可行的搜索路径。

在这里插入图片描述

现在尝试用深度优先搜索来解决这个问题，dfs() 函数的功能是解决当前应该怎么办。到达某个点的时候需要处理的是：先检查是否已经到达目标位置，如果没有到达则找出下一步可以走的地方。为了解决这个问题，此处 dfs() 函数需要维护 4 个参数，分别是地图，当前这个点的 yh 坐标、xw 坐标以及当前已经走过的步数 step。

void dfs(int map_data[50][50], int yh, int xw, int step)
{return;
}

判断是否已经到达目标位置很好实现，只需要判断当前的坐标和目标位置的坐标是否相等就可以了，如果相等则表明已经到达目标位置。

void dfs(int map_data[50][50], int yh, int xw, int step)
{// 判断是否到达目标位置if ((yh == end_yh) && (xw == end_xw)){if (step < min_step) {min_step = step; // 更新最少步骤}return; // 返回}return;
}

如果没有到达目标位置，则找出下一步可以走的地方。因为有四个方向可以走，根据我们之前的约定，按照顺时针的方向来尝试 (即按照右、下、左、上的顺序)。为了编程方便，定义了一个方向数组 next。

	// right, down, left, up - (height, width)int next[4][2] = { { 0, 1 },{ 1, 0 },{ 0, -1 },{ -1, 0 } };

在这里插入图片描述

通过这个方向数组，使用循环就很容易获得下一步的坐标。这里将下一步的横坐标用 txw 存储，纵坐标用 tyh 存储。

// 枚举 4 种走法
for (int k = 0; k < 4; k++)
{// 计算下一个点的坐标tyh = yh + next[k][0];txw = xw + next[k][1];
}

接下来我们就要对下一个点 (tyh, txw) 进行判断，包括是否越界，是否为障碍物，以及这个点是否已经在路径中 (即避免重复访问一个点)。需要用 book[tyh][txw] 来记录格子 (tyh, txw) 是否已经在路径中。

如果这个点符合所有的要求，就对这个点进行下一步的扩展，即 dfs(map_data, tyh, txw, step + 1);，注意这里是 step + 1，因为一旦你从这个点开始继续往下尝试，就意味着你的步数已经增加了 1。

	// 枚举 4 种走法for (int k = 0; k < 4; k++){// 计算下一个点的坐标tyh = yh + next[k][0];txw = xw + next[k][1];// 判断是否越界if ((tyh < 0) || (tyh >= YH) || (txw < 0) || (txw >= XW)) {continue;}// 0 表示空地，1 表示障碍物if ((0 == map_data[tyh][txw]) && (0 == book[tyh][txw])){book[tyh][txw] = 1; // 标记这个点已经走过dfs(map_data, tyh, txw, step + 1); // 开始尝试下一个点book[tyh][txw] = 0; // 尝试结束，取消这个点的标记}}

1. D:\visual_studio_workspace\yongqiangcheng\yongqiangcheng\input.txt

input.txt 第一行是测试用例个数 2，后续依次为具体测试用例数据。
测试用例第一行有两个数 YH 和 XW，YH = 5 表示迷宫的行数，XW = 4 表示迷宫的列数。
紧接着一行表示起始点坐标 (start_yh, start_xw) 和目标位置坐标 (end_yh, end_xw)，注意起始点为 (0, 0)。
接下来 YH = 5 行 XW = 4 列为迷宫地图，0 表示空地，1 表示障碍物。

2
5 4
0 0 3 2
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
5 4
0 0 3 2
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1

在这里插入图片描述

2. yongqiang.cpp

/*
============================================================================
Name        : yongqiang.cpp
Author      : Yongqiang Cheng
Version     : Version 1.0.0
Copyright   : Copyright (c) 2020 Yongqiang Cheng
Description : Hello World in C++, Ansi-style
============================================================================
*/#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <time.h>using namespace std;int YH = 0, XW = 0;
int end_yh = 0, end_xw = 0;
int book[50][50] = { 0 };
int min_step = INT_MAX;void dfs(int map_data[50][50], int yh, int xw, int step)
{// right, down, left, up - (height, width)int next[4][2] = { { 0, 1 },{ 1, 0 },{ 0, -1 },{ -1, 0 } };int tyh = 0, txw = 0;// 判断是否到达目标位置if ((yh == end_yh) && (xw == end_xw)){if (step < min_step) {min_step = step; // 更新最少步骤}return; // 返回}// 枚举 4 种走法for (int k = 0; k < 4; k++){// 计算下一个点的坐标tyh = yh + next[k][0];txw = xw + next[k][1];// 判断是否越界if ((tyh < 0) || (tyh >= YH) || (txw < 0) || (txw >= XW)) {continue;}// 0 表示空地，1 表示障碍物if ((0 == map_data[tyh][txw]) && (0 == book[tyh][txw])){book[tyh][txw] = 1; // 标记这个点已经走过dfs(map_data, tyh, txw, step + 1); // 开始尝试下一个点book[tyh][txw] = 0; // 尝试结束，取消这个点的标记}}return;
}int inference(int map_data[50][50], int start_yh, int start_xw)
{int ret = 0;// 从起点开始搜索book[start_yh][start_xw] = 1; // 标记起点已经在路径中，防止后面重复走// 第 4 个参数是初始步数 0dfs(map_data, start_yh, start_xw, 0);book[start_yh][start_xw] = 0;ret = min_step;return ret;
}int main()
{clock_t start = 0, end = 0;double cpu_time_used = 0;const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";freopen(input_txt, "r", stdin);// freopen(output_txt, "w", stdout);start = clock();printf("Start of the program, start = %ld\n", start);printf("Start of the program, start = %ld\n\n", start);int case_num = 0;cin >> case_num;cout << case_num << endl;for (int idx = 1; idx <= case_num; idx++){int start_yh = 0, start_xw = 0;// (height, weight)int map_data[50][50] = { 0 };cin >> YH >> XW; // initializationcin >> start_yh >> start_xw >> end_yh >> end_xw; // initializationcout << YH << XW << endl;cout << start_yh << start_xw << end_yh << end_xw << endl;min_step = INT_MAX; // initializationfor (int h = 0; h < YH; h++){for (int w = 0; w < XW; w++){cin >> map_data[h][w];}}for (int h = 0; h < YH; h++){for (int w = 0; w < XW; w++){cout << map_data[h][w];}cout << endl;}inference(map_data, start_yh, start_xw);cout << "CASE #" << idx << " = " << min_step << endl;}end = clock();printf("\nEnd of the program, end = %ld\n", end);printf("End of the program, end = %ld\n", end);cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;printf("Total time taken by CPU: %f\n", cpu_time_used);printf("Exiting of the program...\n");fclose(stdin);// fclose(stdout);return 0;
}

在这里插入图片描述

/*
============================================================================
Name        : yongqiang.cpp
Author      : Yongqiang Cheng
Version     : Version 1.0.0
Copyright   : Copyright (c) 2020 Yongqiang Cheng
Description : Hello World in C++, Ansi-style
============================================================================
*/#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <time.h>using namespace std;int YH = 0, XW = 0;
int end_yh = 0, end_xw = 0;
int book[50][50] = { 0 };
int min_step = INT_MAX;void dfs(int map_data[50][50], int yh, int xw, int step)
{// right, down, left, up - (height, width)int next[4][2] = { { 0, 1 },{ 1, 0 },{ 0, -1 },{ -1, 0 } };int tyh = 0, txw = 0;// 判断是否到达目标位置if ((yh == end_yh) && (xw == end_xw)){if (step < min_step) {min_step = step; // 更新最少步骤}return; // 返回}// 枚举 4 种走法for (int k = 0; k < 4; k++){// 计算下一个点的坐标tyh = yh + next[k][0];txw = xw + next[k][1];// 判断是否越界if ((tyh < 0) || (tyh >= YH) || (txw < 0) || (txw >= XW)) {continue;}// 0 表示空地，1 表示障碍物if ((0 == map_data[tyh][txw]) && (0 == book[tyh][txw])){book[tyh][txw] = 1; // 标记这个点已经走过dfs(map_data, tyh, txw, step + 1); // 开始尝试下一个点book[tyh][txw] = 0; // 尝试结束，取消这个点的标记}}return;
}int inference(int map_data[50][50], int start_yh, int start_xw)
{int ret = 0;// 从起点开始搜索book[start_yh][start_xw] = 1; // 标记起点已经在路径中，防止后面重复走// 第 4 个参数是初始步数 0dfs(map_data, start_yh, start_xw, 0);book[start_yh][start_xw] = 0;ret = min_step;return ret;
}int main()
{clock_t start = 0, end = 0;double cpu_time_used = 0;const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";freopen(input_txt, "r", stdin);freopen(output_txt, "w", stdout);start = clock();printf("Start of the program, start = %ld\n", start);printf("Start of the program, start = %ld\n\n", start);int case_num = 0;cin >> case_num;cout << case_num << endl;for (int idx = 1; idx <= case_num; idx++){int start_yh = 0, start_xw = 0;// (height, weight)int map_data[50][50] = { 0 };cin >> YH >> XW; // initializationcin >> start_yh >> start_xw >> end_yh >> end_xw; // initializationcout << YH << XW << endl;cout << start_yh << start_xw << end_yh << end_xw << endl;min_step = INT_MAX; // initializationfor (int h = 0; h < YH; h++){for (int w = 0; w < XW; w++){cin >> map_data[h][w];}}for (int h = 0; h < YH; h++){for (int w = 0; w < XW; w++){cout << map_data[h][w];}cout << endl;}inference(map_data, start_yh, start_xw);cout << "CASE #" << idx << " = " << min_step << endl;}end = clock();printf("\nEnd of the program, end = %ld\n", end);printf("End of the program, end = %ld\n", end);cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;printf("Total time taken by CPU: %f\n", cpu_time_used);printf("Exiting of the program...\n");fclose(stdin);fclose(stdout);return 0;
}

2.1 D:\visual_studio_workspace\yongqiangcheng\yongqiangcheng\output.txt

Start of the program, start = 0
Start of the program, start = 02
54
0032
0010
0000
0010
0100
0001
CASE #1 = 7
54
0032
0010
0000
0010
0100
0001
CASE #2 = 7End of the program, end = 1
End of the program, end = 1
Total time taken by CPU: 0.001000
Exiting of the program...

在这里插入图片描述

发明深度优先算法的是 John E.Hopcroft 和 Robert E.Tarjan。1971 ~ 1972 年，他们在斯坦福大学研究图的连通性 (任意两点是否可以相互到达) 和平面性 (图中所有的边相互不交叉。在电路板上设计布线的时候，要求线与线不能交叉，这就是平面性的一个实际应用)，发明了这个算法。他们也因此获得了1986年的图灵奖。

当我们遇到这种需要分身，需要不断尝试完成的事情时，可以尝试使用深度优先搜索算法，要借助计算机的运算速度优势，完成一些生活中比较繁琐重复的事情。

3. 注意全局变量初始化

上面 2. 的代码用了太多全局变量是不合适，在运行多个测试用例时，切记不可忘记对全局变量的初始化。

/*
============================================================================
Name        : yongqiang.cpp
Author      : Yongqiang Cheng
Version     : Version 1.0.0
Copyright   : Copyright (c) 2020 Yongqiang Cheng
Description : Hello World in C++, Ansi-style
============================================================================
*/#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <time.h>using namespace std;int end_yh = 0, end_xw = 0;void dfs(int map_data[50][50], int yh, int xw, int step, int book[50][50], int YH, int XW, int *min_step)
{// right, down, left, up - (height, width)int next[4][2] = { { 0, 1 },{ 1, 0 },{ 0, -1 },{ -1, 0 } };int tyh = 0, txw = 0;// 判断是否到达目标位置if ((yh == end_yh) && (xw == end_xw)){if (step < *min_step) {*min_step = step; // 更新最少步骤}return; // 返回}// 枚举 4 种走法for (int k = 0; k < 4; k++){// 计算下一个点的坐标tyh = yh + next[k][0];txw = xw + next[k][1];// 判断是否越界if ((tyh < 0) || (tyh >= YH) || (txw < 0) || (txw >= XW)) {continue;}// 0 表示空地，1 表示障碍物if ((0 == map_data[tyh][txw]) && (0 == book[tyh][txw])){book[tyh][txw] = 1; // 标记这个点已经走过dfs(map_data, tyh, txw, step + 1, book, YH, XW, min_step); // 开始尝试下一个点book[tyh][txw] = 0; // 尝试结束，取消这个点的标记}}return;
}int inference(int map_data[50][50], int start_yh, int start_xw, int YH, int XW)
{int ret = 0;int book[50][50] = { 0 };int min_step = INT_MAX;// 从起点开始搜索book[start_yh][start_xw] = 1; // 标记起点已经在路径中，防止后面重复走// 第 4 个参数是初始步数 0dfs(map_data, start_yh, start_xw, 0, book, YH, XW, &min_step);book[start_yh][start_xw] = 0;ret = min_step;return ret;
}int main()
{clock_t start = 0, end = 0;double cpu_time_used = 0;const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";freopen(input_txt, "r", stdin);freopen(output_txt, "w", stdout);start = clock();printf("Start of the program, start = %ld\n", start);printf("Start of the program, start = %ld\n\n", start);int case_num = 0;cin >> case_num;cout << case_num << endl;for (int idx = 1; idx <= case_num; idx++){int start_yh = 0, start_xw = 0;int YH = 0, XW = 0;int ret = 0;// (height, weight)int map_data[50][50] = { 0 };cin >> YH >> XW; // initializationcin >> start_yh >> start_xw >> end_yh >> end_xw; // initializationcout << YH << XW << endl;cout << start_yh << start_xw << end_yh << end_xw << endl;for (int h = 0; h < YH; h++){for (int w = 0; w < XW; w++){cin >> map_data[h][w];}}for (int h = 0; h < YH; h++){for (int w = 0; w < XW; w++){cout << map_data[h][w];}cout << endl;}ret = inference(map_data, start_yh, start_xw, YH, XW);cout << "CASE #" << idx << " = " << ret << endl;}end = clock();printf("\nEnd of the program, end = %ld\n", end);printf("End of the program, end = %ld\n", end);cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;printf("Total time taken by CPU: %f\n", cpu_time_used);printf("Exiting of the program...\n");fclose(stdin);fclose(stdout);return 0;
}

在这里插入图片描述

3.1 D:\visual_studio_workspace\yongqiangcheng\yongqiangcheng\output.txt

Start of the program, start = 113
Start of the program, start = 1132
54
0032
0010
0000
0010
0100
0001
CASE #1 = 7
54
0032
0010
0000
0010
0100
0001
CASE #2 = 7End of the program, end = 114
End of the program, end = 114
Total time taken by CPU: 0.001000
Exiting of the program...

在这里插入图片描述

References

《啊哈！算法》 - 啊哈磊


http://www.ppmy.cn/news/528844.html

相关文章

windows 文件路径太深无法删除解决方案

windows 文件路径太深无法删除解决方案

在cmd命令行窗口中输入 robocopy empty_dir will_delete_dir /purge ps&#xff1a; empty_dir 新建的空白目录 will_delete_dir 要删除的目录 注意中间的空格
阅读更多...
windows下文件路径太深，删除解决方案

windows下文件路径太深，删除解决方案

在要删除文件夹&#xff08;destination&#xff09;同目录创建一个空文件夹(empty_dir)&#xff1b;打开cmd.exe ,切换至要删除的文件的目录 cd destination&#xff1b;执行 robocopy destination dest_dir /purge; 指令的意思是拷贝空文件夹到目标文件夹&#xff0c;同时删…
阅读更多...
windows下文件路径太深，无法删除解决办法

windows下文件路径太深，无法删除解决办法

windows下npm开发时&#xff0c;有时候node_modules/下的目录嵌套太深&#xff0c;导致无法删除项目。 npm社区贡献了一个工具windows-node-deps-deleter可供删除这样的目录。 E:\vscode>npm install -g windows-node-deps-deleter C:\Users\xx\AppData\Roaming\npm\wndde…
阅读更多...
[Pytorch]Broadcasting广播机制

[Pytorch]Broadcasting广播机制

文章目录 Broadcasting广播机制BroadcastableBroadcasting Broadcasting广播机制 Broadcasting机制用于在不同维度的张量进行运算时进行维度的自动增加与扩展&#xff0c;Broadcasting机制使用的前提是两个参与运算的张量是可broadcastable的。 Broadcastable 怎样的两个向量…
阅读更多...
英特尔hd630驱动_HD 630和驱动程序的兼容性问题

英特尔hd630驱动_HD 630和驱动程序的兼容性问题

我的英语不是很好。 所以我用翻译google ...哈哈 我买了DESKMINI 110 细节 H110芯片组STX主板 英特尔g4600 CPU 三星ddr4 12800 4GB x 2ea 8GB 三星850 Evo SSD 500GB Windows 10 Home 64bit 我第一次安装LOL(英雄联盟)&#xff0c;但我不能玩..因为fps 10~11(在游戏图形模式下…
阅读更多...
32 x 8段液晶驱动HT1622 程序

32 x 8段液晶驱动HT1622 程序

软件平台IAR for STM8 V1.30 #include #define uchar unsigned char #define uint unsigned int #define LCD_ON 0x03 //启动偏压发生器 #define LCD_OFF 0x02 //关闭偏压发生器 #define SYS_DIS 0x00 …
阅读更多...
hdoj2660

hdoj2660

感觉这道题更像dp&#xff0c;但数据范围小&#xff0c;可以用dfs做 # include <iostream> # include <cstring> using namespace std; int n,k,m,a[25],b[25],ma,tmp,qian,sum,zl,mark[25];void dfs(int x,int y,int zhi,int w) {int i;if(yk&&w<m){i…
阅读更多...
（ SSD ； HHD ； HDD ）

（ SSD ； HHD ； HDD ）

硬盘三大种类&#xff08;SSD&#xff1b;HHD&#xff1b;HDD&#xff09; 固态硬盘&#xff08;Solid State Drive&#xff09;: 用固态电子存储芯片阵列而制成的硬盘&#xff0c;由控制单元和存储单元&#xff08;FLASH芯片、DRAM芯片&#xff09;组成。固态硬盘在接口的规范…
阅读更多...
最新文章

Copyright @ 2022~2023