婚庆网站建设的需求分析,免费网页软件,wordpress内涵主题,学做网站设计文章目录0. 回溯模板1. 走楼梯2. 机器走格子#xff0c;但限定方向3. 中国象棋#xff0c;马走日字4. 走迷宫5. 积木覆盖0. 回溯模板
搜索算法中的回溯策略#xff0c;也是深度优先搜索的一种策略#xff0c;比较接近早期的人工智能。毕竟#xff0c;搜索是人工智能技术中…
文章目录0. 回溯模板1. 走楼梯2. 机器走格子但限定方向3. 中国象棋马走日字4. 走迷宫5. 积木覆盖0. 回溯模板
搜索算法中的回溯策略也是深度优先搜索的一种策略比较接近早期的人工智能。毕竟搜索是人工智能技术中进行问题求解的基本技术很多问题都可以归结到某种搜索。
下面给出回溯算法的模板很多题目其实可以套用该模板快速解决。但是请注意深度优先搜索一般不能应用于求解最优解的问题上。
// node: 当前在回溯树中的结点
void trace (int node){if (当前结点 目标结点)输出方案;else{尝试所有满足条件的结点if (新结点符合条件){记录新结点;设置占位标志;trace(i1); // 进行下一结点的试探删除新结点;恢复占位标志;}}
}接下来的例子将带领大家由浅入深、循序渐进走入回溯法的世界。
1. 走楼梯
【描述】楼梯有 n 级台阶n ≤ 20可以一步走 1 级也可以一步走 2 级。输入一个正整数 n请输出所有上楼梯的方案。
【输入和输出样例】
5
方案1 1 1 1 1
方案1 1 1 2
方案1 1 2 1
方案1 2 1 1
方案1 2 2
方案2 1 1 1
方案2 1 2
方案2 2 1【简要算法描述】
设置一个数组 record 记录每一次的走法走一级台阶还是两级台阶设置一个变量 passed 记录走过的台阶数
// 第node步的试探我该走一级台阶还是两级台阶
void trace (int node){if (passed 目标台阶数)输出方案;else{尝试走step级台阶step1,2if (可以走step级台阶){record[node] step; // 记录passed passed step; // 占位trace(node1); // 试探下一步record[node] 0; // 清除记录passed passed - step; // 复位}}
}【题解】
#include cstdio
#include cstring
using namespace std;// goal:目标台阶数, node:当前在回溯树中的结点/第node步, passed:记录走过的台阶数, record:记录走法方案
void trace (int goal, int node, int passed, int record[]){if (passed goal){ // 若正好走到目标台阶 node--; // 则需修正当前结点printf(方案);for (int i 1; i node; i)printf(%d , record[i]);printf(\n);}else{for (int step 1; step 2; step){ // 尝试走一个台阶或两个台阶 if (passed step goal){ // 如果没有超出目标台阶数 record[node] step; // 则记录该走法passed step; // 并记录走过的台阶数相当于占位 trace(goal, node1, passed, record); // 继续探索下一种走法试探下一步该怎么走 record[node] 0; // 回溯删除该走法非必要操作 passed - step; // 回溯回到没有走这一步之前的台阶上为尝试下一种走法做准备相当于恢复占位标志} }}
}int main(){int n;int A[100];while (scanf(%d, n) ! EOF){memset(A, 0, sizeof(A));trace(n, 1, 0, A); // 当前处在回溯树的初始结点走过的台阶数为0 }return 0;
}通过该题想必可以了解到回溯算法的套路了比较关键的无非就是五个步骤。下面的几题跟寻找路径有关难度比第一题稍小。
2. 机器走格子但限定方向
【描述】现有一个 4x4 的格子给定一个起始坐标mn只允许机器人向上或向右到达目标坐标点4,4请输出所有的机器人走法方案。
注4x4 格子的横坐标范围为 1 ~ 4纵坐标范围为 1 ~ 4因此 mn 值只能为 1 ~ 4。
【输入和输出样例 1】
2 3
方案
0 0 0 0
0 0 1 0
0 0 1 0
0 0 1 1
方案
0 0 0 0
0 0 1 0
0 0 1 1
0 0 0 1
方案
0 0 0 0
0 0 1 1
0 0 0 1
0 0 0 1【输入和输出样例 2】
3 2
方案
0 0 0 0
0 0 0 0
0 1 0 0
0 1 1 1
方案
0 0 0 0
0 0 0 0
0 1 1 0
0 0 1 1
方案
0 0 0 0
0 0 0 0
0 1 1 1
0 0 0 1【简要算法描述】
设置一个数组 record 记录每一次的走法
// 当前机器人在坐标point处
void trace (point){if (point 目标坐标)输出方案;else{尝试向上或向右if (可以向上或向右){record[point向上或向右] 1;trace(point向上或向右); // 试探下一步record[point向上或向右] 0;}}
}【题解】
#include cstdio
#include cstring
using namespace std;struct Pos{ // 横坐标x和纵坐标y封装为一个 坐标点 结构体 int x;int y;Pos(int _x, int _y): x(_x), y(_y) {}// 重载运算符 bool operator (const struct Pos p){return p.x x p.y y; }// 重载运算符bool operator (const struct Pos p){return x p.x y p.y; } // 重载运算符用于坐标点之间的运算 struct Pos operator (const struct Pos p){return Pos(xp.x, yp.y);}
};#define MAX 4
int A[MAX1][MAX1] {0}; // 记录走法方案也兼具占位功能1表示走过0表示没走过
struct Pos delta[2] {Pos(1, 0), Pos(0, 1)}; // 只能向右走或向上走用于改变 // goal:目标坐标, point:当前坐标, record:记录走法方案
void trace (struct Pos goal, struct Pos point, int record[][MAX1]){if (point goal){ // 若正好走到目标点则输出方案 printf(方案\n);for (int i 1; i MAX; i){for (int j 1; j MAX; j)printf(%d , record[i][j]);printf(\n);}}else{for (int i 0; i 1; i){ // 尝试向上或向右走 if (point delta[i] Pos(MAX, MAX)){ // 如果没有走出范围以外 struct Pos pointDelta point delta[i];record[pointDelta.x][pointDelta.y] 1; // 则记录该走法或标记占位标志 trace(goal, pointDelta, record); // 继续探索下一种走法遍历过的结点数加1 record[pointDelta.x][pointDelta.y] 0; // 回溯为尝试下一种走法做准备或恢复占位标志 } }}
}int main(){int m, n;while (scanf(%d%d, m, n) ! EOF){struct Pos init(m, n);struct Pos goal(MAX, MAX);memset(A, 0, sizeof(A));A[init.x][init.y] 1; // 起始点标记为走过 trace(goal, init, A); // 当前处在回溯树的初始结点走过的台阶数为0 printf(\n);}return 0;
}3. 中国象棋马走日字
【描述】中国棋盘大小为 8x9假设马的初始位置在0,0处现给定象棋棋盘中的一个点mn请输出跳到mn的总步数小于十步之内的方案需要标出第几步走到了棋盘的哪个位置。
注意由于遍历所有方案所用的时间已超出了可接受范围因此请每输出一个方案使用system(“pause”)暂停程序运行。
【输入和输出示例】
3 3
方案1 0 0 0 3 0 7 0 50 0 2 0 8 0 4 0 00 0 0 0 0 0 0 6 00 0 0 9 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0
请按任意键继续. . .
方案1 0 0 0 3 0 7 0 50 0 2 0 0 0 4 0 00 0 0 0 0 8 0 6 00 0 0 9 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0
请按任意键继续. . .
方案1 0 0 0 3 0 0 0 50 0 2 0 8 0 4 0 00 0 0 0 0 0 0 6 00 0 0 9 0 7 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0
请按任意键继续. . .【简要算法描述】
设置一个数组 record 记录每一次的走法
// 当前马走到坐标point处为第step步
void trace (point, step){if (point 目标坐标)输出方案;else{从point开始尝试下一步日字得到新坐标if (新坐标可以走){record[新坐标] step;trace(新坐标, step1); // 试探下一步record[新坐标] 0;}}
}【题解】
#include cstdio
#include cstring
#include stdlib.h
using namespace std;struct Pos{ // 横坐标x和纵坐标y封装为一个 坐标点 结构体 int x;int y;Pos(int _x, int _y): x(_x), y(_y) {}// 重载运算符 bool operator (const struct Pos p){return p.x x p.y y; }// 重载运算符bool operator (const struct Pos p){return x p.x y p.y; } // 重载运算符用于坐标点之间的运算 struct Pos operator (const struct Pos p){return Pos(xp.x, yp.y);}
};#define MAX_X 8
#define MAX_Y 9
int A[MAX_X][MAX_Y]; // 记录走法方案也兼具占位功能非0表示走过0表示没走过
struct Pos delta[8] { Pos(-2, 1), Pos(-1, 2), Pos(1, 2), Pos(2, 1),Pos(-2, -1), Pos(-1, -2), Pos(1, -2), Pos(2, -1)}; // goal:目标坐标, point:当前坐标, record:记录走法方案, step:记录走了多少步
void trace (struct Pos goal, struct Pos point, int record[][MAX_Y], int step){if (step 11)return;if (point goal step 11){ // 若正好走到目标点则输出方案 printf(方案\n);for (int i 0; i MAX_X; i){for (int j 0; j MAX_Y; j)printf(%3d, record[i][j]);printf(\n);}system(pause); // 不可能遍历所有方案因此每输出一个方案暂停一下}else{for (int i 0; i 8; i){ struct Pos pointDelta point delta[i]; // 尝试不同的走法 if (Pos(0, 0) pointDelta pointDelta Pos(MAX_X-1, MAX_Y-1) record[pointDelta.x][pointDelta.y] 0){ // 如果没有走出范围以外以及该点未走过 record[pointDelta.x][pointDelta.y] step; // 则记录该走法或标记占位标志 trace(goal, pointDelta, record, step1); // 继续探索下一种走法遍历过的结点数加1 record[pointDelta.x][pointDelta.y] 0; // 回溯为尝试下一种走法做准备或恢复占位标志 } }}
}int main(){int m, n;while (scanf(%d%d, m, n) ! EOF){struct Pos init(0, 0);struct Pos goal(m, n);memset(A, 0, sizeof(A));A[0][0] 1; // 起始点标记为第一步 trace(goal, init, A, 2); // 从第二步开始走printf(\n);}return 0;
}4. 走迷宫
【描述】给一张 6x6 迷宫地图用“.”表示可以走的路用“#”表示障碍物以左上角0,0为起点左下角5,5为终点输出所有路径方案用“Y”标记已经走过的路径。
【输入示例】
.#..#.
.##.#.
..#...
#...#.
.#.#..
#.....【输出示例】
方案
Y # . . # .
Y # # . # .
Y Y # . . .
# Y Y . # .
. # Y # . .
# . Y Y Y Y方案
Y # . . # .
Y # # . # .
Y Y # . . .
# Y Y . # .
. # Y # Y Y
# . Y Y Y Y方案
Y # . . # .
Y # # . # .
Y Y # Y Y Y
# Y Y Y # Y
. # . # . Y
# . . . . Y方案
Y # . . # .
Y # # . # .
Y Y # Y Y Y
# Y Y Y # Y
. # . # Y Y
# . . . Y Y【简要算法描述】
将迷宫地图当做可以标记占位的数组注意如果将迷宫地图定义为由 6 个字符串组成则每个字符串最后的“\0”也要占位所以申请数组时请申请 6x7 的大小
// 当前走到坐标point处
void trace (point){if (point 目标坐标)输出方案;else{从point开始尝试下一步得到新坐标if (新坐标没有超出范围且不是障碍){record[新坐标] Y;trace(新坐标, step1); // 试探下一步record[新坐标] 0;}}
}【题解】
#include cstdio
#include cstring
using namespace std;struct Pos{ // 横坐标x和纵坐标y封装为一个 坐标点 结构体 int x;int y;Pos(int _x, int _y): x(_x), y(_y) {}// 重载运算符 bool operator (const struct Pos p){return p.x x p.y y; }// 重载运算符bool operator (const struct Pos p){return x p.x y p.y; } // 重载运算符用于坐标点之间的运算 struct Pos operator (const struct Pos p){return Pos(xp.x, yp.y);}
};#define MAX_X 6
#define MAX_Y 6
char A[MAX_X][MAX_Y1] {.#..#.,.##.#.,..#...,#...#.,.#.#..,#.....}; struct Pos delta[4] {Pos(1, 0), Pos(0, 1), Pos(-1, 0), Pos(0, -1)}; // goal:目标坐标, point:当前坐标, record:记录走法方案
void trace (struct Pos goal, struct Pos point, char record[][MAX_Y1]){if (point goal){ // 若正好走到目标点则输出方案 printf(方案\n);for (int i 0; i MAX_X; i){for (int j 0; j MAX_Y; j)printf(%c , record[i][j]);printf(\n);}printf(\n);}else{for (int i 0; i 4; i){ struct Pos pointDelta point delta[i]; // 尝试不同的走法 if (Pos(0, 0) pointDelta pointDelta Pos(MAX_X-1, MAX_Y) record[pointDelta.x][pointDelta.y] .){ // 如果没有走出范围以外以及该点未走过或不是障碍 record[pointDelta.x][pointDelta.y] Y; // 则记录该走法或标记占位标志 trace(goal, pointDelta, record); // 继续探索下一种走法record[pointDelta.x][pointDelta.y] .; // 回溯为尝试下一种走法做准备或恢复占位标志 } }}
}int main(){int m, n;struct Pos init(0, 0);struct Pos goal(5, 5);A[0][0] Y; // 起始点标记为走过 trace(goal, init, A); printf(\n);return 0;
}5. 积木覆盖
【描述】给定一个 6x6 的网格用“#”表示被某块积木占用用“.”表示没有被积木占用请求出网格中一共有多少块积木并输出每块积木的坐标。
【输入样例 1】
.#..#.
.#.##.
.#....
#...#.
.#.###
#....#【输出样例 1】
第1块积木坐标(1,1) (2,1) (0,1)
第2块积木坐标(1,4) (0,4) (1,3)
第3块积木坐标(3,0)
第4块积木坐标(4,4) (4,5) (5,5) (3,4) (4,3)
第5块积木坐标(4,1)
第6块积木坐标(5,0)
共有6块积木【输入样例 2】
.#..#.
.####.
.#....
#...#.
.#.###
#....#【输出样例 2】
第1块积木坐标(1,1) (2,1) (1,2) (1,3) (1,4) (0,4) (0,1)
第2块积木坐标(3,0)
第3块积木坐标(4,4) (4,5) (5,5) (3,4) (4,3)
第4块积木坐标(4,1)
第5块积木坐标(5,0)
共有5块积木【分析】该题比“走迷宫”较简单但相较于“走迷宫”本题没有明显的递归回溯终止目标因为这个目标是隐含的当一块积木的所有格子都走完后就代表回溯完毕。本题可以模仿“走迷宫”先找出被积木占用的格子即先找到“#”的坐标相当于迷宫的入口或某块积木的“入口”然后开始寻找其他与之相邻的“#”把“.”视为障碍物把找到的“#”改为“Y”。
然而这里有个问题。如果回溯时把已走过的“Y”改回“#”则下一次找到另一个“#”的坐标相当于某块积木的“入口”你如何保证是不是之前我们遍历过的同一块积木所以我们不能把已走过的“Y”改回“#”而是要改成别的符号比如“V”这样才能区分出哪块积木已经遍历过了下一次就不用遍历了。
【简要算法描述】
// 当前走到坐标point处
void trace (point, map){从point开始尝试下一步得到新坐标if (新坐标没有超出范围且新坐标“#”或“V”){map[新坐标] Y;输出坐标;trace(新坐标, step1); // 试探下一步map[新坐标] V;}}
}【题解】
#include cstdio
#include cstring
using namespace std;struct Pos{ // 横坐标x和纵坐标y封装为一个 坐标点 结构体 int x;int y;Pos(int _x 0, int _y 0): x(_x), y(_y) {}// 重载运算符 bool operator (const struct Pos p){return p.x x p.y y; }// 重载运算符bool operator (const struct Pos p){return x p.x y p.y; } // 重载运算符用于坐标点之间的运算 struct Pos operator (const struct Pos p){return Pos(xp.x, yp.y);}
};#define MAX_X 6
#define MAX_Y 6
// 积木地图
char A[MAX_X][MAX_Y1] {.#..#.,.#.##.,.#....,#...#.,.#.###,#....#}; // 记录一块积木的每个坐标
struct Pos record[MAX_X * MAX_Y]; // 方向变化数组
struct Pos delta[4] {Pos(1, 0), Pos(0, 1), Pos(-1, 0), Pos(0, -1)}; // point:当前坐标, map:标记了占位的地图, isOther:标记该积木除了占有该格子外没有别的格子
void trace (struct Pos point, char map[][MAX_Y1], bool isOther){for (int i 0; i 4; i){ struct Pos pointDelta point delta[i]; // 尝试不同的走法if (Pos(0, 0) pointDelta pointDelta Pos(MAX_X-1, MAX_Y) map[pointDelta.x][pointDelta.y] # || map[pointDelta.x][pointDelta.y] V){ // 如果没有走出范围以外以及该点未走过 map[pointDelta.x][pointDelta.y] Y; // 则标记占位标志 isOther true; // 这块积木原来还占有别的格子 printf((%d,%d) , pointDelta.x, pointDelta.y); // 输出该格子的坐标 trace(pointDelta, map, isOther); // 继续探索下一块积木map[pointDelta.x][pointDelta.y] V; // 回溯恢复占位标志} }
}int main(){int cnt 0;bool isOther;for (int i 0; i MAX_X; i){for (int j 0; j MAX_Y; j){if (A[i][j] #){ // 找到积木的入口 cnt;isOther false;printf(第%d块积木坐标, cnt);trace(Pos(i, j), A, isOther); // 开始寻找该积木的其他格子 if (!isOther) // 如果该积木只占有一个格子则只输出该格子的坐标 printf((%d,%d), i, j);printf(\n);} }} printf(共有%d块积木\n, cnt);return 0;
}从下一篇开始是有关数学智力题的回溯算法应用。
