回溯法

回溯的基本原理

在问题的解空间中，按深度优先遍历策略，从根节点出发搜索解空间树。算法搜索至解空间 的任意一个节点时，先判断该节点是否包含问题的解。如果确定不包含，跳过对以该节点为根的 子树的搜索，逐层向其祖先节点回溯，否则进入该子树，继续深度优先搜索。

回溯法解问题的所有解时，必须回溯到根节点，且根节点的所有子树都被搜索后才结束。

回溯法解问题的一个解时，只要搜索到问题的一个解就可结束。

回溯的基本步骤

  1. 定义问题的解空间(我理解的解空间就是目标问题的内容，或者说是目标问题解的集合。)
  2. 确定易于搜索的解空间结构
  3. 以深度优先搜索的策略搜索解空间，并在搜索过程中尽可能避免无效搜索

例题

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了 矩阵的某一格，那么该路径不能再次进入该格子。例如在下面的 3×4 的矩阵中包含一条字符串 “bfce”的路径（路径中的字母用下划线标出）。但矩阵中不包含字符串“abfb”的路径，因为 字符串的第一个字符 b 占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

A B T G

C F C S

J D E H

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#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。

而广度优先算法就是，同时选择多个岔路口，从一边开始，逐层判断，它们是否能够走通(找到解)。

以起点开始辐射式的开始遍历(逐层)。感谢这位up主的分享——相关视频。