Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

数据结构和算法躬行记(5)——回溯算法

咖啡机(K.F.J) 2020-09-22 08:33:00 阅读数:115 评论数:0 点赞数:0 收藏数:0

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

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

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

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

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

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

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

面试题12 矩阵路径和面试题13 机器人运动范围。在二维方格或矩阵的运动可用回溯法解决。

一、N皇后

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 打印从 1~n 位的数。将问题转换成数字排列,用递归实现。

 

版权声明
本文为[咖啡机(K.F.J)]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/strick/p/13384038.html

支付宝红包,每日可领(支付宝免费1-2元支付红包)