回溯

OOM_Killer · · 576 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

如何理解回溯

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

... 太多了,不全打印了

小结

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


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

本文来自:简书

感谢作者:OOM_Killer

查看原文:回溯

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

576 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传