数据结构:回溯法

回溯法的定义

一个问题解决的可能性都可以抽象为一个树状结构,在某一步含有n个可能的选项,那么这一步即可形象的表示为树中的一个节点,这个节点有n个子节点。遍历这个树,叶节点包含答案,则顺着叶节点的子节点寻找下去,否则,回溯到该叶节点的上一个节点去尝试其他节点,直至寻找到答案为止。

如何使用回溯法

eg:给定一个数组[1,2,3,4],求可能的排列顺序的可能性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func backTrack(nums:[Int], tempList: inout Array<Int>, resultList: inout Array<Array<Int>>) {
if (tempList.count == nums.count) {
//终结条件,满足一个条件时
let newTemplist : Array<Int> = tempList;
resultList.append(newTemplist);
} else {
for i in 0..<nums.count {
if (tempList.contains(nums[i])) {
//如果已经包含了,就不添加
continue;
}
tempList.append(nums[i]);
//递归调用,此时的tempList一直在变化,直到满足终结条件才结束
backTrack(nums: nums, tempList: &tempList, resultList: &resultList);
//它移除tempList最后一个元素的作用就是返回上一次调用时的数据,也就是希望返回之前的节点再去重新搜索满足条件。这样才能实现回溯
tempList.remove(at: (tempList.count - 1));
}
}
}
1
2
3
var resultList : Array<Array<Int>> = Array<Array<Int>>(); var tempList : Array<Int> = Array<Int>();
backTrack(nums: nums, tempList: &tempList, resultList: &resultList);
print(resultList);

矩阵寻找路径

一个非常经典的在矩阵中寻找路径的问题。在一个M*N的字符矩阵中,寻找是否存在指定路径。要求路径单步只能上下左右移动,不能重复移动某一个格子。
如果在矩阵中寻找bfce路径,判断是否包含该路径
avatar

这里思路可以抽象为树形结构
avatar

代码实现如下:

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
func hasPathCore(rows:Int, columns:Int, row:Int, col:Int, isVisited:inout [Int], pathList:[String], pathLength:inout Int, origList:[String]) ->Bool {
if (pathList.count <= pathLength) {
return true;
}
var hasPath = false;
//nowIndex代表矩阵中当前的位置
let nowIndex = row * columns + col;
if (row >= 0 && row < rows && col >= 0 && col < columns && origList[nowIndex] == pathList[pathLength] && isVisited[nowIndex] == 0) {
//保证遍历还在矩阵范围内进行,将矩阵当前位置的元素和目标路径中节点元素对比,相等且没进走过的格子算为有效格子。
//pathLength++,开始寻找目标路径下一个节点
pathLength += 1;
//将矩阵中当前格子作为有效格子放入isVisited
isVisited[nowIndex] = 1;
//递归:访问上下左右四个元素是否满足有效格子
hasPath = hasPathCore(rows: rows, columns: columns, row: row, col: (col - 1), isVisited: &isVisited, pathList: pathList, pathLength: &pathLength, origList: origList)
|| hasPathCore(rows: rows, columns: columns, row: row, col: (col + 1), isVisited: &isVisited, pathList: pathList, pathLength: &pathLength, origList: origList)
|| hasPathCore(rows: rows, columns: columns, row: (row - 1), col: col, isVisited: &isVisited, pathList: pathList, pathLength: &pathLength, origList: origList)
|| hasPathCore(rows: rows, columns: columns, row: (row + 1), col: col, isVisited: &isVisited, pathList: pathList, pathLength: &pathLength, origList: origList);
if (!hasPath) {
//当前元素之后的路径没有找到合适的,回到上一个元素。这里可以形象的理解为树形结构中节点,当前节点下面的子节点不包含问题,那么放弃当前节点,返回上一个节点进行深度寻找。
pathLength -= 1;
isVisited[nowIndex] = 0;
}
}
return hasPath;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//判断是否含有路径
func isHasPath(rows:Int, columns: Int, pathList: inout [String], origList:[String]) -> Bool {
if (rows < 1 || columns < 1) {
return false;
}

//因为不能重复统计格子,visitedListot用来代表有没有进入过格子。
var visitedList : Array<Int> = Array<Int>();
for _ in 0..<(rows * columns) {
visitedList.append(0);
}

var pathLength = 0;
//这里遍历所有元素来寻找路径,当一个点找不到符合条件的路径时,就需要重新开始一个起点
for row in 0..<rows {
for col in 0..<columns {
if (hasPathCore(rows: rows, columns: columns, row: row, col: col, isVisited: &visitedList, pathList: pathList, pathLength: &pathLength, origList: origList)) {
return true;
}
}
}
return false;
}

main函数中调用如下:

1
2
3
4
let strList = ["a","b","t","g","c","f","c","s","j","d","e","h"];
var path = ["b","f","c","e"];
let haspath = isHasPath(rows: 3, columns: 4, pathList: &path, origList: strList);
print(haspath);

矩阵中求起点到终点的路径条数

在一个3*4矩阵中寻找起点a到终点h的路径条数。要求单步只能向下和向右移动。这题和上题有点类似,解题如下:

1
2
3
4
5
6
7
8
9
10
11
func findPath(rows:Int, columns: Int, origList:[String], target:String) -> Int {
if (rows < 1 || columns < 1) {
return 0;
}

//路径条数
var pathCount = 0;
//从[0,0]开始计算
isArriveTheLastPoint(rows: rows, columns: columns, row: 0, col: 0, target: target, origList: origList,pathCount: &pathCount);
return pathCount;
}

递归算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func isArriveTheLastPoint(rows:Int, columns:Int, row: Int, col: Int, target:String, origList:[String], pathCount:inout Int) {
var isEnd = false;
//nowIndex代表矩阵中当前的位置
let nowIndex = row * columns + col;
if (row >= 0 && row < rows && col >= 0 && col < columns) {
if (origList[nowIndex] == target) {
//已经到达终点,算作一个完整路径。那么路径条数+1
isEnd = true;
pathCount += 1;
}

if (!isEnd) {
//递归,分别向右和向下访问两个元素是否到达指定终点
let nextCol = col + 1;
let nextRow = row + 1;
isArriveTheLastPoint(rows: rows, columns: columns, row: row, col: nextCol, target: target,origList:origList,pathCount: &pathCount);
isArriveTheLastPoint(rows: rows, columns: columns, row: nextRow, col: col, target: target,origList:origList,pathCount: &pathCount);
}
}
}

main函数调用

1
2
3
4
let strList = ["a","b","t","g","c","f","c","s","j","d","e","h"];
let target = "h";
let count = findPath(rows: 3, columns: 4, origList: strList, target:target);
print(count);