回溯算法

基本原理

回溯算法基于树的深度优先遍历

DFS：把全部的情况描述成一个树，不同的解决方法对应不同的子树。根据DFS，遍历到一个节点后继续向下遍历，如果某个路径无法满足条件，那么返回上一个节点。如果一个子树遍历完成，那么开始遍历另一个子树。

function check(node) {
  // 需要一个函数判断当前情况是否满足
}

function DFS(root) {
  // 这里使用递归思路：递归遍历一个子树的全部节点；满足后，返回这个节点
  if (check(root)) {
    // 如果满足一个节点，那么继续判断这个节点下面的节点
    check(root.children)
  } else {
    // 如果不满足一个节点，那么回溯到上一个节点
    break;
  }
}

回溯算法核心代码

function backTrack(current, target, list) {
  // 回溯结束条件：临时数组长度大于目标长度；临时数组不满足条件等
  if (current.length === target) {
    // 如果临时数组满足要求，需要把临时数组深拷贝一份，然后放到结果数组中
    list.push([...current]);
    return;
  }
    for (let i = 0; i < len; i++) {
    // 全部数组中是否重复？是否排序？这样可以减少回溯的次数
    if (current.includes(i)) {
      continue;
    }
    // 把当前的情况增加一个
    current.push(i);
    // 继续回溯
    backTrack(current, target, list);
    // 回溯结束后，临时数组去掉这个元素，继续循环
    current.pop();
  }
}

实际使用

78 子集

https://leetcode-cn.com/problems/subsets/

/**
 * @param {number[]} nums
 * @return {number[][]}
 * By Michael An
 */
var subsets = function(nums) {
  const len = nums.length;
  let list = [];
  list.push([]);
  // 处理特殊长度的数组
  if (len === 0) {
    return list;
  } else if (len === 1) {
    list.push(nums);
    return list;
  }

  // 回溯
  var backTrack = function(current, target, list) {
    if (current.length === target) {
      list.push([...current]);
      return;
    }
    nums.forEach((i) => {
      if (current.length === 0 || (!current.includes(i) && i > current[current.length - 1])) {
        current.push(i);
        backTrack(current, target, list);
        current.pop();
      }
    });
  }

  // 处理长度大于1的数组的子集
  list.push(nums);
  // 排序，确保正序进入子序列
  nums.sort((a, b) => a - b);
  // 先循环设置子集的长度，然后回溯，满足长度的可以放入目标数组
  for (let i = 1; i < len; i++) {
    let target = i;
    let current = [];
    backTrack(current, target, list);
  }
  return list;
};

子集2

https://leetcode-cn.com/problems/subsets-ii/submissions/

/**
 * @param {number[]} nums
 * @return {number[][]}
 * By Michael An
 */
var subsetsWithDup = function(nums) {
  const len = nums.length;
  let list = [];
  list.push([]);
  if (len === 0) {
    return list;
  } else if (len === 1) {
    list.push(nums);
    return list;
  }
  var backTrack = function(current, target, list, lastIndex) {
    if (current.length === target) {
      list.push([...current]);
      return;
    }
    nums.forEach((i, index) => {
      if ((current.length === 0 || i >= current[current.length - 1]) && index > lastIndex) {
        current.push(i);
        backTrack(current, target, list, index);
        current.pop();
      }
    });
  }

  nums.sort((a, b) => a - b);
  for (let i = 1; i < len; i++) {
    let target = i;
    let current = [];
    backTrack(current, target, list, -1);
  }

  let dict = {};
  for (let i = 1; i < list.length; i++) {
    let key = list[i].toString();
    if (dict[key]) {
      list.splice(i, 1);
      i--;
    } else {
      dict[key] = true;
    }
  }
  list.push(nums);
  return list;
};

数独问题

一个9*9的数独中，每一行，每一列都是9个数，然后每个小单元格中也是9个数。然后不断回溯。

C++方法，注释 by Michael An

#include<iostream>
using namespace std;
#define LEN 9
int a[LEN][LEN] = {0};

// 辅助函数：判断当前填充这个数，是否满足数独要求？
bool Isvaild(int count) {
  int i = count / 9;
  int j = count % 9;
  // 首先根据一个数，计算余数和商，将一维数据转换成二维数组（i行j列是否满足）
  // 检测行
  for(int iter = 0; iter != j; iter++) {
    if(a[i][iter] == a[i][j]) {
      return 1;
    }
  }
  //检测列
  for(int iter=0; iter!=i; iter++) {
    if(a[iter][j] == a[i][j]){
      return 1;
    }
  }
  //检测九宫   
  for(int p = i/3*3; p < (i/3+1)*3; p++){
    for(int q = j/3*3; q < (j/3+1)*3; q++){
      if(p == i && j == q) {         
        continue;
      }     
      if(a[p][q] == a[i][j]) {
        return 1;
      }
    }
  }
  return 0;
}

// 辅助函数: 打印满足要求的数独
void print() {
  cout<<"数度的解集为"<<":"<<endl;
  for(int i=0; i<9; i++) {
    for(int j=0; j<9; j++) {
      cout<<a[i][j]<<" ";
    }
    cout<<endl;
  }
  cout<<endl;
}

// 回溯函数
// 参数：当前填写的单元格的序号
void first_chek(int count){
  // 如果已经填充了81个，那么直接打印数独（或者返回这个数独）
  if (81 == count){
    print();
    return;
  }
  // 获取当前的序号所在的行列编号（i-j）
  int i = count / 9;   //列
  int j = count % 9;   //行

  // 如果当前编号是空，那么
  if(a[i][j]==0) {
    // 遍历这个空单元格，然后进一步回溯
    for(int n=1; n<=9; n++) {
      a[i][j] = n;
      if(!Isvaild(count)){  //这个值不冲突，回溯下一个单元格（DFS）
        first_chek(count+1)
      }
    }      
    a[i][j] = 0;
  }
  // 如果当前编号已经有值，那么回溯下一个编号
  else{       
    first_chek(count+1);
  }
}

// 主函数
int main() {
  // 设置数独中已有的数字
  a[1][2] = 3;
  a[5][3] = 9;
  a[8][8] = 1;
  a[4][4] = 4;
  first_chek(0);
  return 0;
}

这个思路可以解决复杂情况下，多步骤判断的情况。

8皇后问题

八皇后问题：需要把八个皇后放在国际象棋中，这八个皇后不能互相吃（不能在横线、竖线、斜线上）

JS 方法（实际测试有问题！）没看懂

// 初始化棋盘：每一个节点坐标是i，j，属性index表示是否有位置
// 棋盘总行（列）数 8*8（二维数组）
const n = 8;

// 8皇后的解法数
let iCount = 0;

// arr是长度为n*n的一维数组，保存着n*n个对象（li）并有各自的坐标
let arr = new Array(n ** 2);

// 默认index都为-1，表示没有被任何皇后标记过
// arr[ i*n + j ].y = i; arr[ i*n + j ].x = j; 每一个节点的属性
for(var i=0; i<n; i++){
  for(var j=0; j<n; j++){
    arr[i*n + j] = {};
    arr[i*n + j].x = j;
    arr[i*n + j].y = i;
  }
}

//iQueen从0开始，即皇后0
function setQueen(iQueen){
  if( iQueen == n ){
    iCount++;
    return;
  }

  for(var i=0; i<n; i++) {
    if (arr[iQueen * n + i].index == -1 ) {
      arr[iQueen * n + i].index = iQueen;
      var x = arr[iQueen*n + i].x;
      var y = arr[iQueen*n + i].y;
      for(var j=0; j < arr.length; j++) {
        if( arr[j].index == -1 && (arr[j].x == x || arr[j].y == y || arr[j].x - arr[j].y == x - y || arr[j].x + arr[j].y == x + y)  ){
          arr[j].index = iQueen;
        }
      }
      //执行到这里，就会跳到下一层函数中，在执行完下一层的函数后，才会回溯到上一层继续执行for循环（此时的for循环是上一层的for循环），包括后面的所有代码
      //需要注意的是，例如当前函数的iQueen=1，跳到下一层函数 iQueen=2，下一层函数执行完后，回溯到上一层，此时的执行环境已经是上一层的执行环境了，即iQueen是等于1，而不是等于2
      //递归
      setQueen(iQueen + 1);
      //回溯
      for(var j=0; j<arr.length; j++){
        if(arr[j].index == iQueen ){
          arr[j].index = -1;
        }
      }

    }
  }
}

setQueen(0);
console.log(arr);

n皇后问题

没看懂，有问题

function nQueens(n) {
    var result = [];
    var k = 0;
    result[k] = 0;
    while (k >= 0) {
    //when k<0; there is no solution for this 'n'
        result[k]++;
        while (result[k] <= n && !place(result, k))
            result[k]++;
        //find proper position for the current queen
        if (result[k] <= n) {
            if (k == n - 1) break;
      //the last queen is put at a proper position, end
            else {
                k++;
                result[k] = 0;
        //turn to next queen and init her position
            }
        } else {
            result[k] = 0;
      //before feedback, we should reset the position or it will influence next time we find proper position for her
            k--;
        }
    }
    return result;
}

//judge the current position is proper or not
//k is the serial number of the queen
//res is the array of a partial solution
function place(res, k) {
    var abs = Math.abs;
    for (var i = 0; i < k; i++) {
        if (res[i] == res[k] || abs(res[i] - res[k]) == abs(i - k))
            return false;
    }
    return true;
}

// 设置开始和结束时间（测试算法效率），n=30 计算
var start = Date.now();
var result = nQueens(30);
var end = Date.now();
console.log(result, end - start);

// [
//   1,  3,  5,  2,  4,  9, 11, 13, 15,
//   7, 23, 26, 28, 25, 22, 24, 30, 27,
//  29, 16, 12, 10,  8,  6, 18, 20, 17,
//  14, 21, 19
// ]
// node 环境执行时间：30845ms 浏览器执行时间：28664ms

这个方法实际测试可行