回溯法
回溯的基本原理
在问题的解空间中，按深度优先遍历策略，从根节点出发搜索解空间树。算法搜索至解空间 的任意一个节点时，先判断该节点是否包含问题的解。如果确定不包含，跳过对以该节点为根的 子树的搜索，逐层向其祖先节点回溯，否则进入该子树，继续深度优先搜索。
回溯法解问题的所有解时，必须回溯到根节点，且根节点的所有子树都被搜索后才结束。
回溯法解问题的一个解时，只要搜索到问题的一个解就可结束。
回溯的基本步骤
- 定义问题的解空间(我理解的解空间就是目标问题的内容，或者说是目标问题解的集合。)
- 确定易于搜索的解空间结构
- 以深度优先搜索的策略搜索解空间，并在搜索过程中尽可能避免无效搜索
例题
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了 矩阵的某一格，那么该路径不能再次进入该格子。例如在下面的 3×4 的矩阵中包含一条字符串 “bfce”的路径（路径中的字母用下划线标出）。但矩阵中不包含字符串“abfb”的路径，因为 字符串的第一个字符 b 占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
A B T G
C F C S
J D E H
代码实现
#include<iostream>
using namespace std;
//探测下一个字符是否存在
bool hasPathCore(const char* matirix,int rows,int cols,
int row,int col, const char* str,int& pathLength,bool* visited)
{
//已经到达字符串结束符,说明前面已经判断完成
if (str[pathLength] == '\0')
{
return true;
}
bool haspath = 0;
//判断当前该点是否合法
//在矩阵内 & 是指定内容(内容) & 没被访问过
if (row >= 0 && row < rows && col >= 0
&& col < cols && matirix[row * cols + col ]== str[pathLength]
&& !visited[row * cols + col])
{
//进入到这里说明当前位置的字符串符合目标str的第几个，判断下一个是否也符合
//str索引++
pathLength++;
//当前结点设置被访问过
visited[row * col + col] = 1;
//递归实现
/*
就是说，选择了一个点，如果周围的周围的周围.......符合，
也就是说着条路能走通，会一路到return true(str结尾——str[pathLength] == '\0'),
然后逐层通过return haspath(1)返回到调用处，
最后再return haspath(1),回到一开始调用该函数的位置，即hasPath中的调用处，
成功找到路径。
*/
//向四周判断
//看有没有符合的点
haspath = hasPathCore(matirix, rows, cols, row, col - 1, str, pathLength, visited)
|| hasPathCore(matirix, rows, cols, row - 1, col, str, pathLength, visited)
|| hasPathCore(matirix, rows, cols, row, col + 1, str, pathLength, visited)
|| hasPathCore(matirix, rows, cols, row + 1, col, str, pathLength, visited);
//有一个符合条件即可
if (!haspath)//如果一个符合的点都没有
{
--pathLength;//str索引回退，
visited[row * cols * +col] = 0;//当前结点周围走不通，标记为未访问，判断其他(方向)的点。
}
}
return haspath;
}
//主体实现流程
bool hasPath(const char* matirix,int rows,int cols,const char* str)
{
//参数错误
if (!matirix || rows <= 0 || cols <= 0 || !str)
{
return false;
}
//bool值矩阵，大小同给定的字符矩阵，标记该位置是否走过
bool* visited = new bool[cols * rows];
memset(visited, 0, cols * rows);//初始化为0，未访问过
int pathLength = 0;
//遍历矩阵中的每一个点，分别从该点开始出发，判断路径
for (int row = 0; row < rows; row++)
{
for (int col = 0; col < cols; col++)
{
if (hasPathCore(matirix, rows,cols, row, col, str, pathLength, visited))
{
return true;
}
}
}
delete[] visited;
return false;
}
//通用单元测试代码(便于多种情况测试)
void Test(const char* TestTitle, const char* dest,const char* str,int rows, int cols, bool HopeResult)
{
cout << "预计结果为" << HopeResult << " ";
if (hasPath(dest, rows, cols, str) == HopeResult)
{
cout << TestTitle << "与预计结果相同" << endl;
}
else
{
cout << TestTitle << "与预计结果不同" << endl;
}
}
int main(void)
{
/*
"ABTG
CFCS
JDEH";
*/
const char* TestTitle = "测试1";
const char* dest = "ABTGCFCSJDEH";
const char* str = "BFCEH";
Test(TestTitle, dest, str, 3, 4, 1);
return 0;
}
小结
我理解的回溯法就是深度优先搜索的应用，深度优先搜索就是，一个问题的解决路径有多个岔路口，选择其中的一个一直走到底，找到最终解就return true,不行就回退，判断下一个岔路口，直到找到解，否则一直找不到就return了false。
而广度优先算法就是，同时选择多个岔路口，从一边开始，逐层判断，它们是否能够走通(找到解)。
