回溯算法

基本算法思想系列文章链接：

回溯算法除了用来指导像深度优先搜索这种经典的算法设计之外，还可以用在很多实际的软件开发场景中，比如正则表达式匹配、编译原理中的语法分析等。

除此之外，很多经典的数学问题都可以用回溯算法解决，比如数独、八皇后、0-1 背包、图的着色、旅行商问题、全排列等等。

如何理解“回溯算法”？

笼统地讲，回溯算法很多时候都应用在“搜索”这类问题上。不过这里说的搜索，并不是狭义的指我们前面讲过的图的搜索算法，而是在一组可能的解中，搜索满足期望的解。

回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。

八皇后问题

我们有一个 8x8 的棋盘，希望往里放 8 个棋子（皇后），每个棋子所在的行、列、对角线都不能有另一个棋子。

我们把这个问题划分成 8 个阶段，依次将 8 个棋子放到第一行、第二行、第三行……第八行。

在放置的过程中，我们不停地检查当前放法，是否满足要求。
- 如果满足，则跳到下一行继续放置棋子；
- 如果不满足，那就再换一种放法，继续尝试。

var result = make([]int, 8)  // 全局或成员变量,下标表示行,值表示queen存储在哪一列

func cal8queens(row int) { //调用方式：cal8queens(0);
        if row == 8 { // 8个棋子都放置好了，打印结果
                printQueens(result)
                return
        }
        for column:=0; column<8; column++ { // 每一行都有8种放法
                if isOK(row, column) { // 有些放法不满足要求
                        result[row] = column // 第row行的棋子放到了column列
                        cal8queens(row+1) //考察下一行
                }
        }
}

func isOK(row, column int) bool { // 判断row行column列放置是否合适
        leftup, rightup :=  column-1, column+1
        for i:=row-1; i>=0; i-- { // 逐行往上考察每一行
                if result[i] == column { return false } // 第i行的column列有棋子吗？
                if leftup >= 0 { // 考察左上对角线：第i行leftup列有棋子吗？
                        if result[i] == leftup { return false }
                }
                if rightup < 8 { // 考察右上对角线：第i行rightup列有棋子吗？
                        if result[i] == rightup {return false}
                }
                leftup--; rightup++
        }
        return true
}

func printQueens(result []int) {  // 打印一个二维矩阵
        for row := 0; row < 8; row++ {
                for column := 0; column < 8; column++ {
                        if result[row] == column {
                                print("Q ")
                        } else {
                                print("* ")
                        }
                }
                println()
        }
        println()
}

正则表达式

正则表达式中，最重要的就是通配符，通配符结合在一起，可以表达非常丰富的语义。为了方便讲解，我假设正则表达式中只包含*和?这两种通配符，并且对这两个通配符的语义稍微做些改变，

其中，“*”匹配任意多个（大于等于 0 个）任意字符，
“?”匹配零个或者一个任意字符

我们依次考察正则表达式中的每个字符，

当是非通配符时，我们就直接跟文本的字符进行匹配，
- 如果相同，则继续往下处理；
- 如果不同，则回溯。
如果遇到特殊字符的时候，我们就有多种处理方式了，也就是所谓的岔路口
- 比如“*”有多种匹配方案，可以匹配任意个文本串中的字符
  - 先随意的选择一种匹配方案
  - 然后继续考察剩下的字符
  - 如果中途发现无法继续匹配下去了，我们就回到这个岔路口，重新选择一种匹配方案
  - 然后再继续匹配剩下的字符。

type Pattern struct {
        matched bool
        pattern []byte  // 正则表达式
        plen    int    // 正则表达式长度
}

func NewPattern(pattern []byte, plen int) *Pattern {
        return &Pattern{pattern: pattern, plen: plen}
}

func (p *Pattern) match(text []byte, tlen int) bool {  // 文本串及长度
        p.matched = false
        p.rmatch(0,0,tlen,text)
        return p.matched
}

func (p *Pattern) rmatch(ti, pj, tlen int, text []byte) { // ti和pj分别是指向文本串和模式串的指针
        if p.matched { return } // 如果已经匹配了，就不要继续递归了
        if pj == p.plen {   // 正则表达式到结尾了
                if ti == tlen { p.matched = true } // 文本串也到结尾了
                return
        }
        if p.pattern[pj] == '*' { // *匹配任意个字符
                for k:=0; k<=tlen-ti; k++ {
                        p.rmatch(ti+k, pj+1, tlen, text)
                }
        } else if p.pattern[pj] == '?' { // ?匹配0个或者1个字符
                p.rmatch(ti, pj+1, tlen, text)
                p.rmatch(ti+1, pj+1, tlen, text)
        } else if ti < tlen && p.pattern[pj] == text[ti] { // 纯字符匹配才行
                p.rmatch(ti+1, pj+1, tlen, text)
        }
}