回溯算法 - 简书

基本思想

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。

重点就是要找到规则如何不重复的枚举出所有组合

举例

八皇后问题

在8X8格的国际象棋上摆放八个皇后（棋子），使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上

image.png

func cal8Queen(row int, result []int) {
    if row == 8 {
        printQueens(result)
        total++
        fmt.Printf("第%d种\n", total)
    }
    //每一行都有8种放法
    for column := 0; column < 8; column++ {
        if isOk(row, column, result) {
            //第row行的第column占位
            result[row] = column
            cal8Queen(row+1, result)
        }
    }
}
func isOk(row int, column int, result []int) bool {
    left := column - 1
    right := column + 1
    for i := row - 1; i >= 0; i-- {
        //判断第i行的colmum上有棋子
        if result[i] == column {
            return false
        }

        if left >= 0 {
            //判断第i上左对角线上是否有棋子
            if result[i] == left {
                return false
            }
        }

        if right < 8 {
            //判断第i上右对角线上是否有棋子
            if result[i] == right {
                return false
            }
        }
        //每次向上一行，对角线位置需要改变
        left--
        right++
    }

    return true
}

func printQueens(result []int) {
    for row := 0; row < 8; row++ {
        for column := 0; column < 8; column++ {
            if result[row] == column {
                fmt.Print("Q ")
            } else {
                fmt.Print("* ")
            }
        }
        fmt.Println()
    }

    fmt.Println("===============")
}

0/1背包问题

我们有一个背包，背包总的承载重量是Wkg。现在我们有n个物品，每个物品的重量不等，并且不可分割。
我们现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？

//全部可能都装入包中，找出所有值中满足条件的最大值
func assembleItemSimple(index int, currentWeight int, itemList []int, totalWeight int) {
    if index == len(itemList) {
        if currentWeight > MaxWeight && currentWeight <= totalWeight {
            MaxWeight = currentWeight
        }
        zeroOrOneBagNumber++
        fmt.Println("weight:", currentWeight)
        fmt.Println("number:", zeroOrOneBagNumber)
        return
    }

    //不装入当前Item
    assembleItemSimple(index+1, currentWeight, itemList, totalWeight)
    //装入当前Item
    assembleItemSimple(index+1, currentWeight+itemList[index], itemList, totalWeight)
}

//优化:当前中间超过包的重量的就中止当前选择，回溯到前面
//
func assembleItemOptimize(index int, currentWeight int, itemList []int, totalWeight int) {
    if index == len(itemList) {
        if currentWeight > MaxWeight {
            MaxWeight = currentWeight
        }
        zeroOrOneBagNumber++
        fmt.Println("weight:", currentWeight)
        fmt.Println("number:", zeroOrOneBagNumber)
        return
    }

    //不装入当前Item
    assembleItemOptimize(index+1, currentWeight, itemList, totalWeight)
    //如果加上当前item的重量没有超过总重量，就加入包中 (剪枝操作)
    if currentWeight+itemList[index] <= totalWeight {
        assembleItemOptimize(index+1, currentWeight+itemList[index], itemList, totalWeight)
    }
}

全排列问题

给定一个数组，给出所有数字的排序组合

var permutationArray []int
var selectedArray []bool
var permutationNumber = 0

func GetFullPermutation(originData []int) {
    permutationArray = make([]int, len(originData), len(originData))
    selectedArray = make([]bool, len(originData), len(originData))

    assemble(0, originData)
}

func assemble(index int, originData []int) {
    if index == len(originData) {
        permutationNumber++
        fmt.Println(strings.Trim(strings.Replace(fmt.Sprint(permutationArray), " ", ",", -1), "[]"))
        return
    }

    for i, data := range originData {
        if !selectedArray[i] {
            //如果没有选中则选中
            permutationArray[index] = data
            selectedArray[i] = true
            assemble(index+1, originData)
            //index排列后,设置非选中状态，自动循环到下一个
            selectedArray[i] = false
        }
    }

}

数独

LeetCode数独
一个数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。

image.png

一个数独。

image.png

在线数独游戏
待续...

缺点

回溯法属于深度优先搜索，由于是全局搜索，复杂度相对高。
缺点在于无法简便地减少枚举量--必须先进行生成所有可能的解，然后一一检查