算法 | 实验6-1n*n的网格,从左上角开始到右下角结束遍历所有的方块仅一次,总共有多少种不同的遍历路径
前言
思路介绍中省略了关于如何进行回溯搜索的细节,而主要讨论回溯中所使用的剪枝策略。
题
对于如图7×7的网格,从左上角开始到右下角结束遍历所有的方块仅一次,总共有多少种不同的遍历路径?
思路
基本思路:回溯法进行搜索。但纯暴力的搜索时间复杂度太大,需要加上剪枝的优化。
剪枝:可剪掉会导致不连通的走法,每走一步都判断是否联通。例如下图中的第五步,就将网格划分成了两片不连通的区域。
判断联通性,思路1:
for 格子 in 所有网格
if(以该格子作为起点进行搜索,能找到一条到达终点的路径)
该格子与终点联通
if(所有格子都与终点联通)
所有网格之间是联通的
即在一次是否联通的判断中,对应每个空的(没走过的)格子都进行一次回溯搜索。
到这里可能就会疑惑,剪枝的代价这么大,值得吗?答案是值得的,可以自己写有剪枝和纯暴力的程序对比一下。
看似一下只剪掉了一种情况,有时其实剪掉的相连的枝条是非常多的。
剪枝效果:对题中 7 * 7 的网格,程序需要运行 2~3 分钟才能得到结果(毕竟搜索的基数还是太大了)。然而比纯暴力的情况好很多(纯暴力搜索我根本没看到结果)。
判断联通性,思路2:
前面的剪枝虽然有一些效果(至少可以看得见结果),然而每次剪枝代价还是偏大。每次判断联通,都对每个格子应用一次回溯搜索其实是不必要的。
那是一种比较静态的思路,你给我一张网格,告诉我哪些格子走过了(被覆盖),哪些格子没走过(空白),然后我告诉你它是不是联通。
另一种想法,就是考虑怎样走会导致不连通,因为状态从联通到不连通的转变只在某一步。
要把一块区域困死,走的路径就肯定会形成闭环,可以作以下断言:
if(我某一步后,前方是墙壁或走过的格子,且此时我两边都是没走过的格子)
不连通
else
联通
对剪枝进行优化后,仅需 2~3 秒即得到结果。
实现(C )
思路1
#include<iostream>
using namespace std;
const int Len = 7;//迷宫的边长
//--------------------------------------------------
//复制一个二维数组,将在live()中被调用
void copy_mg(int source[][Len], int target[][Len]){
for(int i = 0; i < Len; i ){
for(int j = 0; j < Len; j ){
target[i][j] = source[i][j];
}
}
}
//--------------------------------------------------
//判断位置(y,x)是否仍与终点联通
bool chance(int mg[][Len], int y, int x){
//出来了吗?
if(y == Len-1 && x == Len-1){
return true;
}
//1
if(y < Len - 1) {
mg[y][x] = '#';
y ;
if(mg[y][x] == 0){
if(chance(mg, y, x)){
return true;
}
}
y--;
mg[y][x] = 0;
}
//2
if(y > 0) {
mg[y][x] = '#';
y--;
if(mg[y][x] == 0){
if(chance(mg, y, x)){
return true;
}
}
y ;
mg[y][x] = 0;
}
//3
if(x < Len - 1) {
mg[y][x] = '#';
x ;
if(mg[y][x] == 0){
if(chance(mg, y, x)){
return true;
}
}
x--;
mg[y][x] = 0;
}
//4
if(x > 0) {
mg[y][x] = '#';
x--;
if(mg[y][x] == 0){
if(chance(mg, y, x)){
return true;
}
}
x ;
mg[y][x] = 0;
}
return false;
}
//--------------------------------------------------
//判断是否存在点被困死,未困死返回true
bool live(int maze[][Len]){
for(int i = 0; i < Len; i ){
for(int j = 0; j < Len; j ){
if(maze[i][j] > 0) continue;
int mg[Len][Len] = {};
copy_mg(maze, mg);
bool t = chance(mg, i, j);
if(! t){
return false;
}
}
}
return true;
}
//--------------------------------------------------
//打印迷宫路径
void printMaze(int maze[][Len]){
for(int i = 0; i < Len; i ){
for(int j = 0; j < Len; j ){
printf("(=) ", maze[i][j]);
}
cout<<endl;
}
cout<<endl;
}
//--------------------------------------------------
//参数y为行标,x为列标
void road(int maze[][Len], int y, int x, int & count, int num){
num ;
//不符合继续递归条件的情况:1、走到了墙上2、有点被困死再无法走到
if(maze[y][x] > 0 || live(maze) == 0){
return;
}
//到达终点
if(x == Len-1 && y == Len-1){
maze[y][x] = num;
//判断是否走过了所有的点
if(maze[y][x] == Len * Len){
count ;
if(count % 10000 == 0) {
cout<<"count: "<<count<<" (y,x): "<<y<<" "<<x<<endl;
printMaze(maze);
}
}
maze[y][x] = 0;
return;
}
//上
if(y - 1 >= 0){
maze[y][x] = num;
road(maze, y-1, x, count, num);
maze[y][x] = 0;
}
//下
if(y 1 < Len){
maze[y][x] = num;
road(maze, y 1, x, count, num);
maze[y][x] = 0;
}
//左
if(x - 1 >= 0){
maze[y][x] = num;
road(maze, y, x-1, count, num);
maze[y][x] = 0;
}
//右
if(x 1 < Len){
maze[y][x] = num;
road(maze, y, x 1, count, num);
maze[y][x] = 0;
}
}
//--------------------------------------------------
int main(){
int maze[Len][Len] = {};
int count = 0;//路径的数量
road(maze, 0, 0, count, 0);
cout<<"result:"<<count<<endl;
return 0;
}
思路2
//1.剪枝:不连通
#include<iostream>
using namespace std;
const int Len = 7;//迷宫的边长
//--------------------------------------------------
//判断走当前这一步是否会导致不连通
bool live(int maze[][Len], int y, int x){
//上下堵,左右空
if((y 1 >= Len || maze[y 1][x] != 0) && (y-1 < 0 || maze[y-1][x] != 0)){
if(x-1 >= 0 && maze[y][x-1] == 0 && x 1 < Len && maze[y][x 1] == 0){
return false;
}
}
//左右堵,上下空
else if((x 1 >= Len || maze[y][x 1] != 0) && (x-1 < 0 || maze[y][x-1] != 0)){
if(y-1 >= 0 && maze[y-1][x] == 0 && y 1 < Len && maze[y 1][x] == 0){
return false;
}
}
return true;
}
//--------------------------------------------------
//参数y为行标,x为列标
void road(int maze[][Len], int y, int x, int & count, int num){
//(y,x):当前坐标,count:路径总数,num:当前是第多少步
num ;
//不符合继续递归条件的情况:1、走到了墙上2、有点被困死再无法走到
if(maze[y][x] > 0 || live(maze, y, x) == 0){
return;
}
//到达终点
if(x == Len-1 && y == Len-1){
maze[y][x] = num;
//判断是否走过了所有的点
if(maze[y][x] == Len * Len){
count ;
}
maze[y][x] = 0;
return;
}
//上
if(y - 1 >= 0){
maze[y][x] = num;
road(maze, y-1, x, count, num);
maze[y][x] = 0;
}
//下
if(y 1 < Len){
maze[y][x] = num;
road(maze, y 1, x, count, num);
maze[y][x] = 0;
}
//左
if(x - 1 >= 0){
maze[y][x] = num;
road(maze, y, x-1, count, num);
maze[y][x] = 0;
}
//右
if(x 1 < Len){
maze[y][x] = num;
road(maze, y, x 1, count, num);
maze[y][x] = 0;
}
}
//--------------------------------------------------
int main(){
int maze[Len][Len] = {};
int count = 0;//路径的数量
road(maze, 0, 0, count, 0);
cout<<"result:"<<count<<endl;
return 0;
}
bug记录
在写live()
函数时,我一开始的 if 语句如下。只有当前位置的上方或下方不是空格子,就判断为“碰到墙壁”。
//向上碰壁或向下碰壁
if(y 1 >= Len || maze[y 1][x] != 0 || y-1 < 0 || maze[y-1][x] != 0)
但后面发现,我给live()
这个函数并没有传递“这一步是向哪个方向走达到的”这个方向信息,要判断碰壁应改为下面的代码(碰壁时,来的方向和走向的方向肯定都不是空格)。
if((y 1 >= Len || maze[y 1][x] != 0) && (y-1 < 0 || maze[y-1][x] != 0))
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfckij
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01