博客
关于我
数据结构和算法躬行记(5)——回溯算法
阅读量:453 次
发布时间:2019-03-06

本文共 2688 字,大约阅读时间需要 8 分钟。

  回溯算法(backtracking)是一个类似枚举的搜索尝试过程,在寻找问题解的过程中,当发现不满足求解条件时,就退回一步,尝试其它路径,该算法的时间复杂度都不会低于 O(N!),复杂的例题包括等。

  在《》一文中提到,解决一个回溯问题,实际上就是一个决策树的遍历过程,需要思考三个问题:

  (1)路径:已经做出的选择。

  (2)选择列表:当前可以做的选择。

  (3)结束条件:到达决策树底层,无法再做选择的条件。

  下面是改编过的算法通用结构。

function backtrack(路径, 选择列表):    if 满足结束条件        console.log(路径)        return    for 选择 of 选择列表        做选择        backtrack(路径, 选择列表)        撤销选择

  面试题12 和面试题13 。在二维方格或矩阵的运动可用回溯法解决。

一、N皇后

  是一道经典的回溯算法题,将 n 个皇后放置在 n×n 的棋盘上,使皇后彼此之间不能相互攻击,即每个棋子所在的行、列、对角线都不能有另一个棋子。

  在下面的中,N是皇后的数量,backtrack()函数是回溯过程(如下所列),isValid()函数判断是否符合选中条件。

  (1)从第一个 row=0 开始。

  (2)循环列并且试图在每个 column 中放置皇后。

  (3)如果方格 (row, column) 在攻击范围内,那么跳过。

  (4)在 (row, column) 方格上放置皇后,继续寻找下一个位置。

  (5)判断 row 是否和皇后数量相同。

const N = 4;function backtrack(route, row) {  if (row == N) {                //结束条件    console.log(route);    return;  }  for (let column = 0; column < N; column++) {    if (!isValid(route, row, column))      continue;    route[row] = column;        //做选择    backtrack(route, row + 1);  //下一步    route[row] = null;          //撤销选择(可省略)  }}//从下往上 判断row行column列放置是否合适function isValid(route, row, column) {  let leftup = column - 1,    rightup = column + 1;  for (let i = row - 1; i >= 0; i--) {        // 逐行往上考察每一行    if (route[i] == column)                   // 第i行的column列有棋子      return false;         if (leftup >= 0) {                  if (route[i] == leftup)                 // 考察左上对角线:第i行leftup列有棋子        return false;    }    if (rightup < N) {      if (route[i] == rightup)                // 考察右上对角线:第i行rightup列有棋子        return false;    }    leftup--;    rightup++;  }  return true;}

二、0-1背包

  有一个背包,背包总的承载重量是 Wkg。现在有 n 个物品,假设每个物品的重量都不相等,并且不可分割。期望选择几件物品,装载到背包中。在不超过背包容量的前提下,如何让背包中物品的总重量最大?

  把物品依次排列,对于物品选择装或不装,然后递归余下的物品,

let max = Number.MIN_VALUE,    W = 100;function backtrack(route, goods) {  let weight = route.length ? route.reduce((acc, cur) => acc += cur) : 0;  if (weight == W || route.length == goods.length) {    //结束条件    if (weight > max && weight <= W) {      max = weight;    }    console.log(route);    return;  }  for (let i = 0; i < goods.length; i++) {    if(weight + goods[i] > W || route.indexOf(goods[i]) > -1)      continue;    route.push(goods[i]);            //做选择    backtrack(route, goods);    route.pop();                     //撤销选择  }}

三、全排列

  是指输出给定数字序列的全部可能的排列,假设序列中的数字都是唯一的,利用回溯算法枚举出所有排列,

function backtrack(route, nums) {  if (route.length == nums.length) {        //结束条件    console.log(route);    return;  }  for (let i = 0; i < nums.length; i++) {    if (route.indexOf(nums[i]) > -1)      continue;    route.push(nums[i]);        //做选择    backtrack(route, nums);    route.pop();                //撤销选择  }}

  面试题17 。将问题转换成数字排列,用递归实现。

 

转载地址:http://cdafz.baihongyu.com/

你可能感兴趣的文章
MuseTalk如何生成高质量视频(使用技巧)
查看>>
mutiplemap 总结
查看>>
MySQL DELETE 表别名问题
查看>>
MySQL Error Handling in Stored Procedures---转载
查看>>
MVC 区域功能
查看>>
MySQL FEDERATED 提示
查看>>
mysql generic安装_MySQL 5.6 Generic Binary安装与配置_MySQL
查看>>
Mysql group by
查看>>
MySQL I 有福啦,窗口函数大大提高了取数的效率!
查看>>
mysql id自动增长 初始值 Mysql重置auto_increment初始值
查看>>
MySQL in 太多过慢的 3 种解决方案
查看>>
MySQL InnoDB 三大文件日志,看完秒懂
查看>>
Mysql InnoDB 数据更新导致锁表
查看>>
Mysql Innodb 锁机制
查看>>
MySQL InnoDB中意向锁的作用及原理探
查看>>
MySQL InnoDB事务隔离级别与锁机制深入解析
查看>>
Mysql InnoDB存储引擎 —— 数据页
查看>>
Mysql InnoDB存储引擎中的checkpoint技术
查看>>
Mysql InnoDB存储引擎中缓冲池Buffer Pool、Redo Log、Bin Log、Undo Log、Channge Buffer
查看>>
MySQL InnoDB引擎的锁机制详解
查看>>