回溯法

  1. 1. 概述
  2. 2. 示例
  3. 3. 解法
  4. 4. 完整代码

回溯法

1. 概述

回溯法是暴力搜索法的一种:cold_sweat:
暴力搜索法通用算法

c = first(P)
while c != nil {
    if valid(P, c) {
        output(P, c)
    }
    c = next(P, c)
}

回溯法基本思想:

  1. 判断当前路径是否正确
  2. 如果正确,继续向下进行
  3. 如果不正确,回溯到上一步的下一个路径

2. 示例

八皇后问题是回溯法经典例子
问题:
如何能够在8×8的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?
(任两个皇后都不能处于同一条横行、纵行或斜线上。该问题可以推广为nxn的棋盘上放置n个皇后问题)

穷举法:
根据组合公式:

$$C^{n \times n}_n={n \times n \choose n}$$

,则8×8共有$C^{64}_8=\frac{64!}{(64-8)!8!}=4426165368$

真实解:
92个不同的解,去除旋转和对称,只有12个解

3. 解法

  • first(P)
    所有皇后的位置,一个二维数组,其中第一位是皇后个数(N), 第二维有两个分别为行(row),列(col).行和列默认初期化为-1

    var queens = make([][]int, N)
    for k, _ := range queens {
      tmp := []int{-1, -1}
      queens[k] = tmp
    }

    起始位置从第0个皇后,从第一行第一列开始

    nQ(0, 0)
  • c != nil
    循环条件 row -> N; 并且没有找到皇后位置

    for row < N && !found {
    // ...
    }
  • valid(P, c)
    两个皇后都不能处于同一条横行、纵行或斜线上

    func valid(row int, col int, currentQueen int) bool {
      for k := 0; k < currentQueen; k++ {
          queen := queens[k]
          if row == queen[0] || col == queen[1] || math.Abs(float64(queen[0]-row)) == math.Abs(float64(queen[1]-col)) {
              return false
          }
      }
      return true
    }
  • output(P, c)
    当判断成立时给当前皇后位置赋值,并递归查找下一个皇后

    queens[currentQueen][0] = row
    queens[currentQueen][1] = currentCol
    found = nQ(currentQueen+1, currentCol+1)

    如果递归失败,会回溯到当前行列,并尝试下一行

  • c = next(P, c)
    通过行进行循环所以,下一个是下一行

    row++

4. 完整代码

package main

import (
    "fmt"
    "math"
)

const N = 8

var queens = make([][]int, N)

func main() {
    for k, _ := range queens {
        tmp := []int{-1, -1}
        queens[k] = tmp
    }
    fmt.Println(queens)
    nQ(0, 0)
    fmt.Println(queens)
}

func nQ(currentQueen int, currentCol int) bool {
    if currentQueen >= N {
        return true
    }
    found := false
    row := 0
    for row < N && !found {
        if valid(row, currentCol, currentQueen) {
            queens[currentQueen][0] = row
            queens[currentQueen][1] = currentCol
            found = nQ(currentQueen+1, currentCol+1)
        }
        row++
    }
    return found
}

func valid(row int, col int, currentQueen int) bool {
    for k := 0; k < currentQueen; k++ {
        queen := queens[k]
        if row == queen[0] || col == queen[1] || math.Abs(float64(queen[0]-row)) == math.Abs(float64(queen[1]-col)) {
            return false
        }
    }
    return true
}

转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 wind.kaisa@gmail.com

文章标题:回溯法

本文作者:kaisawind

发布时间:2020-06-11, 02:06:12

最后更新:2020-11-18, 15:55:44

原始链接:https://kaisawind.gitee.io/2020/06/10/2020-06-11-backtracking/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏