回溯算法实例

之前简单了解过回溯算法，没有举例。今天来回顾一下，回溯算法有一套相对固定的核心逻辑。

if 满足条件 ：
    跳出循环

for 条件 in 条件集合：
    做出选择
    backtrack()
    撤销选择

if 语句用来判断是否达到跳出条件，达到就返回结果。 for 循环才是这段核心代码中的核心，先从条件池中做出选择，然后用剩余条件去做回溯， 整个结果全走完一遍，撤销选择，挑选第二个条件，再走一变。 举个例子就是 "abcd"四个字母的不同排序方法有多少种，就是先挑出a字母作为第一个的字母，然后用"bcd"充当第二次循环的条件池，然后再循环，一次类推。 循环完一轮后，跳出循环，再选择字母“b”做开头的第一个字母，继续循环。
以下是go的示例代码：

package main

import "fmt"

func helper(bt []byte, start int, str *[]string) {
    if start == len(bt) {
        *str = append(*str, string(bt))
    } else {
        for i := start; i <= len(bt)-1; i++ {
            if i != start {
                tmp := bt[start]
                bt[start] = bt[i]
                bt[i] = tmp
            }

            fmt.Println(str)
            helper(bt, start+1, str)

            if i != start {
                tmp := bt[start]
                bt[start] = bt[i]
                bt[i] = tmp
            }
        }
    }
}

func getAbc(s string) []string {
    str := make([]string, 0)
    helper([]byte(s), 0, &str)
    return str
}

func main() {
    fmt.Println(getAbc("abc"))
}

还有一个就是九宫格问题，就是从1-10中抽取数字，排列成3*3的九宫格，要求是任意方向的两个数字加起来必须是质数。 逻辑跟上面的全排列类似，首先定义两个list， 一个是1-9， 另一个是20以内的质数。for 循环 9 次， 每次选选定一个数字作为第一个，然后从剩余的数字中选择一个数字填充第二个格子，这里就多加了一步判断，判断是否前两个横竖都是两个数相加都是质数。还是go的代码示例：

package main

import (
    "fmt"
)

var pos [9]int
var sub []int = []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
var num []int = []int{1, 2, 3, 5, 7, 11, 13, 17, 19}

/*从质数中查找，找到返回true*/
func searchFromNum(n int) bool {
    for i := 0; i < 9; i++ {
        if n == num[i] {
            return true
        }
    }
    return false
}

/*检验结果是否正确*/
func check(n int) bool {
    //行相邻
    for i := 0; i < n; i++ {
        for j := 0; j < n-1; j++ {
            if searchFromNum(pos[i*n+j]+pos[i*n+j+1]) == false {
                return false
            }
        }
    }
    //列相邻
    for j := 0; j < n; j++ {
        for i := 0; i < n-1; i++ {
            if searchFromNum(pos[i*n+j]+pos[(i+1)*n+j]) == false {
                return false
            }
        }
    }
    return true
}

var down, up int = 0, 9

/*填入0~8到九宫格的解，全排列（枚举）*/
func fillBox(i, n, r int, count *int) {
    if i == n {
        if check(r) {
            (*count)++
            for i := 0; i < r; i++ {
                for j := 0; j < r; j++ {
                    fmt.Printf("%3d", pos[i*r+j])
                }
                fmt.Println()
            }
            fmt.Println("============")
        }
        return
    }
    for j := down; j <= up; j++ {
        if sub[j] != -1 {
            pos[i] = sub[j]
            sub[j] = -1
            fillBox(i+1, n, r, count)
            sub[j] = pos[i]
        }
    }
}

func main() {
    count := 0
    fillBox(0, 9, 3, &count)
    fmt.Println(count)
}

九宫格的第二个示例：

package Jiu

import "fmt"

var pos [9]int
var sub []int = []int{1,2,3,4,5,6,7,8,9,10}
var num []int = []int{1,2,3,5,7,11, 13, 17, 19}

func searchFromNum(n int) bool {
    for i :=0; i < 9; i++  {
        if n == num[i] {
            return true
        }
    }
    return false
}

func check(i int) bool {
    //纵向
    if i-3 >= 0 {
        if searchFromNum(pos[i] + pos[i-3]) == false {
            return false
        }
    }

    //横向
    if i%3 != 0 {
        if searchFromNum(pos[i] + pos[i-1]) == false {
            return false
        }
    }

    return true
}

var down, up int = 0, 9

func fillBox(i, n, r int, count *int) {
    if i == n {
        (*count)++
        for i :=0; i < r; i++  {
            for j :=0; j < r; j++  {
                fmt.Printf("%3d", pos[i*r+j])
            }
            fmt.Println()
        }
        fmt.Println("==========")
        return
    }

    for j := down; j <= up; j++  {
        pos[i] = sub[j]
        if sub[j] != -1 && check(i, n) {
            sub[j] = -1
            fillBox(i+1, n, r, count)
            sub[j] = pos[i]
        }
    }
}

func main() {
    count := 0
    fillBox(0, 9, 3, &count)
    fmt.Println(count)
}

以上代码都是我从网上摘取下来的。大体思路我是有了，但是让我自己复写不一定能写出来，抄写下来作为备忘。