回溯

如何理解回溯

回溯可以理解成一个人在前进的过程中有无数个岔路口,经过一个岔路口,又有一个岔路口。每在一个岔路口选择一个道都会影响这个人之后的人生。
有的人在每一个岔路口都能做出十分正确的选择,所以这个人的生活和事业都达到了人生巅峰。而有的人一步,步步错,可能就是它最初的选择的那个岔路口就是错的,导致这个人就一致生活坎坷。
经典的回溯算法解决的问题很多,如八皇后、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:
-----
... 太多了,不全打印了

小结

回溯是什么,说白了,就是穷举,但是这个穷举,会在过程中就淘汰掉不符合规范的组合。

有疑问加站长微信联系(非本文作者)

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
• 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传