回溯
2019-08-25 本文已影响0人
OOM_Killer
如何理解回溯
回溯可以理解成一个人在前进的过程中有无数个岔路口，经过一个岔路口，又有一个岔路口。每在一个岔路口选择一个道都会影响这个人之后的人生。
有的人在每一个岔路口都能做出十分正确的选择，所以这个人的生活和事业都达到了人生巅峰。而有的人一步，步步错，可能就是它最初的选择的那个岔路口就是错的，导致这个人就一致生活坎坷。
经典的回溯算法解决的问题很多，如八皇后、0-1背包问题、图的着色、旅行商问题、全排列问题。
下面挑几个例子来
八皇后问题
-
问题：
假设有一个 8x8 的棋盘，希望往整个棋盘放入8个棋子（皇后Q），每个棋子所在的行，列，对角线都不能有其他的棋子，下面的图，第一幅图就是符合条件的，而第二幅图就是不符合条件的，八皇后问题就是希望找到所有期望满足的放置棋子的方法。
八皇后问题
那么这个问题按照刚才的理解就可以变成这样。
- 问题抽象
一共有8个岔路口，每个岔路口就是一行，每行随便选择一个地方放置棋子。但是每放一个棋子，就需要检查当前的状态还满足八皇后问题吗。不满足直接pass，满足接着放下一行吧。
这是简化版的三皇后问题，其实感觉有点像穷举，但是不满足的提前被pass掉了。
三皇后问题
代码实现（golang 版本）
type EightQueue struct {
Column []int
}
func (eq *EightQueue) CalEightQueues(row int) {
if row == 8 { // 行数满了
fmt.Println(eq.Column) // 打印 当前每行的Q都应该在哪一列
eq.PrintQueue() // 打印图
return
}
for column := 0; column < 8;column ++ { // 每一行有8种摆放方法
if eq.IsOk(row,column) { // 将当前 行，列 代入，查看之前已经放入的Q还是否满足8皇后条件
eq.Column[row] = column
eq.CalEightQueues(row+1) // 考察下一行
}
}
}
func (eq *EightQueue) IsOk(row,column int) bool { // 判断摆放位置是否合适
leftup := column - 1 // 左斜线上方（因为下方还没放入呢，所以不需要判断）
rightup := column + 1 // 右斜线上方
for i := row -1;i >= 0;i-- { // 从当前行往第0行遍历
if eq.Column[i] == column { // 判断该列在某行（下标） 是否存在Q
return false
}
if leftup >= 0 {
if eq.Column[i] == leftup { // 判断其左上对角线上 是否存在Q
return false
}
}
if rightup < 8 {
if eq.Column[i] == rightup { // 判断其右上对角线上 是否存在Q
return false
}
}
leftup-- // 左列 - 1
rightup++ // 右列 + 1
}
return true
}
func (eq *EightQueue) PrintQueue() {
for row := 0; row < 8 ;row++ {
for column := 0; column < 8; column++ {
if eq.Column[row] == column {
fmt.Printf(" Q ")
}else {
fmt.Printf(" * ")
}
}
fmt.Printf("\n")
}
}
执行一下结果
func main() {
eq := EightQueue.EightQueue{
Column : make([]int ,8 ),
}
eq.CalEightQueues(0) // 调用时，当然是从第0行开始遍历了
}
执行结果：
[0 4 7 5 2 6 1 3]
Q * * * * * * *
* * * * Q * * *
* * * * * * * Q
* * * * * Q * *
* * Q * * * * *
* * * * * * Q *
* Q * * * * * *
* * * Q * * * *
[0 5 7 2 6 3 1 4]
Q * * * * * * *
* * * * * Q * *
* * * * * * * Q
* * Q * * * * *
* * * * * * Q *
* * * Q * * * *
* Q * * * * * *
* * * * Q * * *
... 太多了，只打印这么点就够了
0-1 背包
0-1 背包的经典解法是动态规划，但是这里还是以回溯来说。
- 问题：
假设有一个背包，背包的总承载重量是 w kg。现在假设有 n 个物品，每个物品的重量不等，并且不可分割，现在期望选择几个物品，装载到背包中，在不超过背包所能装载重量的前提下，实现背包中的总重量最大。 - 分析：
对于每个物品来说，都有两种不同的选择，装进背包或者不装进背包。对于n个物品来说，总的装法就 2^n 种。去掉总重量超过 w kg的。从剩下的装法中选择重量最接近w kg的。不过，如何才能不重复的穷举出这 2^n 种装法呢。
有没有发现，这和八皇后问题十分相似，就是先穷尽，并及时pass掉不符合规定的。
-
图解:
背包问题
代码实现 （golang 版本）
type Knapsack struct {
MaxWeight int // 背包的最大承重
Items []int // 待放入背包中的物品
}
type ItemInKnapsack struct {
itemIndex int // 记录放进背包中的物品的下标
itemWeight int // 记录被放进背包中物品的重量
}
func (k *Knapsack) PutItemInKnapsack(CurWeight int,n int,items []ItemInKnapsack) {
if n >= len(k.Items) { // 表示 items 中的内容被遍历完了
fmt.Println("共存放的物品个数",len(items)) // 统计一下装进背包里的item
fmt.Printf("存放的为")
sum := 0
for _,v := range items {
sum += v.itemWeight
fmt.Printf(" 下标:%d 重量:%d ",v.itemIndex,v.itemWeight)
}
fmt.Printf("\n总重量为%d:",sum)
fmt.Printf("\n-----\n")
return
}
k.PutItemInKnapsack(CurWeight,n+1,items) // 第n个物品我不放
if CurWeight + k.Items[n] <= k.MaxWeight { // 第n个物品，如果放进去还没达到最大重量，我就放
items = append(items,ItemInKnapsack{n,k.Items[n]})
k.PutItemInKnapsack(CurWeight + k.Items[n],n+1,items)
}
}
执行一下
func main() {
// 最大承重 10，items 是各个物品
k := Knapsack.Knapsack{MaxWeight:10,Items:[]int{3,2,5,2,1,2,3,1,4,5,5,10}}
k.PutItemInKnapsack(0,0,make(map[int]int,10)) // 当前重0，从第0个开始遍历
}
执行结果：
共存放的物品个数 0
存放的为
总重量为0:
-----
共存放的物品个数 1
存放的为 下标:11 重量:10
总重量为10:
-----
共存放的物品个数 1
存放的为 下标:10 重量:5
总重量为5:
-----
共存放的物品个数 2
存放的为 下标:9 重量:5 下标:10 重量:5
总重量为10:
-----
共存放的物品个数 1
存放的为 下标:8 重量:4
总重量为4:
...
共存放的物品个数 3
存放的为 下标:7 重量:1 下标:8 重量:4 下标:10 重量:5
总重量为10:
-----
共存放的物品个数 3
存放的为 下标:7 重量:1 下标:8 重量:4 下标:9 重量:5
总重量为10:
-----
共存放的物品个数 1
存放的为 下标:6 重量:3
总重量为3:
-----
... 太多了，不全打印了
小结
回溯是什么，说白了，就是穷举，但是这个穷举，会在过程中就淘汰掉不符合规范的组合。
