高级算法

本文共--字 阅读约--分钟 | 浏览: -- Last Updated: 2022-02-19

动态规划

动态规划有时被认为是一种与递归相反的技术。递归是从顶部开始将问题分解，通过解决掉所有分解出小问题的方式，来解决整个问题；而动态规划解决方案从底部开始解决问题，将所有的小问题解决掉，然后合并成一个整体解决方案，从而解决掉整个大问题。

使用递归去解决问题虽然简洁，但效率不高。包括 JavaScript 在内的众多语言，不能高效的将递归代码解释为机器代码，尽管写出来的程序简洁，但是执行效率低下，但这并不是说使用递归是件坏事，本质上说，只是那些指令式编程语言和面向对象的编程语言对递归的实现不够完美，因为它们没有将递归作为高级编程的特性。

许多使用递归区解决的编程问题，可以重写为使用动态规划的技巧去解决。动态规划方法通常会使用一个数组来建立一张表，用于存放被分解成众多子问题的解。当算法执行完毕，最终的解法将会在这个表中很明显的地方被找到。

动态规划实例：计算斐波那契数列

常用的递归解法如下：

function fib(n){
  return n > 2 ? fib(n-1) + fib(n-2) : 1;
}

缺点在于很多值会在递归调用的过程中被反复计算，比如计算 fib(5) 会被拆分为 fib(4) + fib(3)，而计算 fib(4) 的时候被拆分 fib(3) + fib(2)，这个时候 fib(3) 被重复计算了两次。

使用动态规划设计的算法从它能解决的最简单的子问题开始，继而通过得到的解，去解决其他更复杂的问题，直到整个问题被解决。所有子问题的解通常被存储在一个数组里以便于访问。

实现如下：

function dynFib(n) {
  if (n === 1 || n === 2) {
    return 1;
  } else {
    var values = new Array(n+1).fill(0);
    // 为方便最终取值，存储结果从数组下标1开始，下标0默认存储0
    values[1] = 1;
    values[2] = 1;
    for (var i = 3; i <= n; i++) {
      values[i] = values[i-1] + values[i-2]
    }
    return values[n]
  }
  // values [0, 1, 1, 2, 3, 5, 8, 13, 21, ...]
}

比较两者之间的计算耗时：

function compare(num) {
  console.log(`计算斐波那契第${num}位耗时比较：`);

  console.time('递归算法：')
  fib(num);
  console.timeEnd('递归算法：')

  console.time('动态规划算法：')
  dynFib(num)
  console.timeEnd('动态规划算法：')
  console.log('结果是: ' +  dynFib(num));
  console.log();
}

compare(10)
compare(20)
compare(30)

// 计算斐波那契第10位耗时比较：
// 递归算法：: 0.240ms
// 动态规划算法：: 0.180ms
// 结果是: 55

// 计算斐波那契第20位耗时比较：
// 递归算法：: 1.648ms
// 动态规划算法：: 0.016ms
// 结果是: 6765

// 计算斐波那契第30位耗时比较：
// 递归算法：: 12.049ms
// 动态规划算法：: 0.053ms
// 结果是: 832040

很明显，动态规划算法是对比递归算法耗时方面的优势是极大的，但我们执行 compare(100) 计算斐波那契数列第100位的结果时，递归算法会挂掉，因为层次太深，而使用动态规划算法耗时也仅为 0.051ms，影响不大。

最后，使用动态规划的算法计算斐波那契数列时，是可以不用数组的，需要用的数组的原因是因为动态规划算法通常需要将中间结果保存起来，不用数组的实现方式如下：

function iterFib(n) {
  var last = 1; // 存储的 fib(n-1)
  var nextLast = 1; // 存储的是 fib(n-2)
  var result = 1; // 存储当前计算的结果，即 fib(n-1) + fib(n-2)

  for (var i = 2; i < n; i++) {
    result = last + nextLast;
    nextLast = last; // 将fib(n-1) 赋值为下一轮的 fib(n-2)
    last = result; // 将fib(n) 赋值为下一轮的 fib(n-1)
  }

  return result;
}

这种写法与尾递归类似，如果使用尾递归实现写法如下：

function fib2(n, a = 0, b = 1) {
  return n >= 2 ? fib2(n-1, b, a+b) : b;
}

// 在当次调用中： fib2(n, a = 0, b = 1)
//    参数列表中的a => nextLast
//    参数列表中的b => last
// 而在递归中 fib2(n-1, b, a+b)
//    将上一次的last当做下一次的nextLast =>   nextLast = last
//    将当前的result(nextLast+last) 当做下一次的last => last = result = nextLast + last
// 所以调用到最后，都会变成调用 fib2(1, last, result) 在这个最后一次调用被执行之前结果就已经被计算出来了
// 成为了参数列表中的第三个参数， 最后一次调用执行，由于 n = 1 直接返回了第三个参数即结果

这两种写法的耗时相差不大，小优于最初的使用数组的动态规划算法，但都远远优于递归算法。

寻找最长公共子串

另一个适合使用动态规划去解决的问题是寻找两个字符串的最长公共子串。例如，在单词“raven”和“havoc”中，最长的公共子串是“av”，我们从暴力方式开始去解决这个问题。给出A和B两个字符串，我们可以通过从A的第一个字符开始与B的对应的每一个字符进行比对的方式找到它们的最长公共子串。如果此时没有找到匹配的字母，则移动到A的第二个字符串，然后再从B的第一个字符串开始进行比对，以此类推。

function lcs(a, b) {
  var maxArr = new Array(a.length).fill(0);
  for (var i = 0; i < a.length; i++) {
    var ca = a[i];
    var max = 0;
    var cai = i;

    for (var j = 0; j < b.length; j++) {
      var cb = b[j];
      if (ca == cb) {
        // 如果找到了匹配的字符，则当前的a的下标指针cai向后移动，b的下标指针通过循环控制也向后移动
        // 即已经找到相同的呢，那么开始比较a的下一位与b的下一位
        // max++是记录最长子串的长度
        max++;
        cai++
        ca = a[cai]
      } else if (max > 0) {
        // 如果ca和cb不等，但是max>0，说明之前是有找到过相同的，但是a,b的指针都移到下一位进行比较的时候发现不同了
        // 此时找到的公共子串的长度是大于以前存储的最大长度时就覆盖
        if (maxArr[i] < max) {
          maxArr[i] = max;
        }
        // ca cb不等的时候，要继续向后匹配b的后续字符串，
        // 所以将a相关的指针和值到重置到该轮循环的初始状态，继续与b之后的字符串进行比较
        // 为什么只在max>0的时候做这件事呢，因为如果max=0，则说明a相关的指针和值就是初始状态，没有发生过变化
        ca = a[i];
        max = 0;
        cai = i;
        continue;
      }
    }
  }
  console.log(maxArr); // [0,4,4,3,2,1]
  // 这个结果的意思是
  // 从a的下标0开始能搜索到的最长公共子串是0
  // 从a的下标1开始能搜索到的最长公共子串是4
  // ...

  // 以下部分可以不管，只是将结果展示出来而已
  const maxInfo = [];
  const maxLen = Math.max.apply(Math, maxArr);
  let maxLenIdx = maxArr.indexOf(maxLen);
  // 可能存在多个一样长度的公共子串
  while (maxArr.indexOf(maxLen, maxLenIdx++) > -1) {
    maxInfo.push({
      start: maxLenIdx - 1, 
      max: maxLen
    })
    // maxLenIdx++ 先赋值后自增以便下一次循环，但是自增完之后执行push操作就需要-1 才是真正匹配到的值的下标
  }
  const result = [];
  for (var i = 0; i < maxInfo.length; i++) {
    const { start, max } = maxInfo[i];
    result.push(a.slice(start, start+max))
  }

  return result;
}

console.log(lcs('backe2', 'cacke12cke2ac2')); // [ 'acke', 'cke2' ]

具体的执行过程体现如下：

动态规划算法使用一个二维数组存储两个字符串相同位置的比较结果，初始化时，该数组的每个元素设置为0，每次在这两个数组的相同位置发现了匹配，就将数组对应的行和列的元素在前一行列的匹配值基础上加1，否则保存为0。

按照这种方式，一个变量会持续记录下找到了多少个匹配项，当算法执行完毕，这个变量会结合一个索引变量来获得最长公共子串。

算法原理如下：

  • 1、使用二维数组，字母A的字符串长度即代表二维数组包含A.length个一维数组（行高），字母B的字符串长度作为一维数组的长度（列宽）

  • 2、使用max来记录最大的匹配值，使用index时记录max发生变化时此时的A串的下标是哪一个。即这个index代表着公共子串的最后一个字符的下标。

  • 3、两个循环，外层ca依次与内层cb进行相比，如果相等，就查看ca的前一位与cb的前一位的匹配值arr[Ai-1][Bi-1]   

    • 如果匹配值为0，则说明ca的前一位与cb的前一位是不同的, 则设置arr[Ai][Bi] = 1   
    • 如果匹配值为1，则说明ca的前一位与cb的前一位是相同的, 则设置arr[Ai][Bi] = arr[Ai-1][Bi-1] + 1 = 2, 表示此轮比完ca与cb加上各自的前一位已经有连续两位是匹配相等的   
    • 如果匹配值为2，则说明ca的前两位与cb的前两位是相同的, 则设置arr[Ai][Bi] = arr[Ai-1][Bi-1] + 1 = 3, 表示此轮比完ca与cb加上各自的前两位已经有连续三位是匹配相等的   
    • 即在各自前一位的匹配值的基础上加1即可

  • 3、当发现相等，就会需要去更新arr这个存储匹配值的数组，此时，将更新的值与max相比，是不是大于max，是就赋值给max，并记录当前A串的下标赋值给index。

具体实现如下：

function lcs2(A, B) {
  var aLen = A.length;
  var bLen = B.length;
  var arr = [];
  for (var i = 0; i < aLen; i++) { // 行高
    arr[i] = new Array(bLen).fill(0) // 填充列宽
  }
  var max = 0;
  var index = 0;

  for (var Ai = 0; Ai < aLen; Ai++) {
    var ca = A[Ai];
    for (var Bi = 0; Bi < bLen; Bi++) {
      var cb = B[Bi];

      if (ca === cb) {
        // 由于，在比较时，若发现相等，就查看各自的前一位匹配值
        // 数组的第一行和第一列没有办法访问各自前一位匹配值
        // 所以如果此时相等直接将其设置为1即可
        if (!arr[Ai-1] || !arr[Ai-1][Bi-1]) {
          arr[Ai][Bi] = 1;
        } else {
          // 不是第一行和第一列则取得各自前一位的匹配值加1即可
          arr[Ai][Bi] = arr[Ai-1][Bi-1] + 1;
        }
        if (arr[Ai][Bi] > max) {
          max = arr[Ai][Bi];
          index = Ai;
        }
      }
    }
  }

  console.log(arr);
  //[[ 0, 0, 0, 0, 0, 0 ],
  // [ 0, 1, 0, 0, 0, 0 ],
  // [ 0, 0, 2, 0, 0, 1 ],
  // [ 1, 0, 0, 3, 0, 0 ],
  // [ 0, 0, 1, 0, 0, 1 ]]

  return A.slice(index-max+1, index+1)
}
console.log(lcs2('abcdc', 'dbcd2c')); // bcd

此例的执行过程如下：

背包问题

背包问题是算法研究中的一个经典问题，试想你是一个保险箱大盗，打开了一个装满奇珍异宝的保险箱，但是你必须将这些宝贝放入你的一个小背包中，保险箱中的物品规格和价值不同，你希望自己的背包装进的宝贝价值最大。

如果我们在这个例子中的保险箱中有5件物品，它们的尺寸分别是3、4、7、8、9，而它们的价值分别是4、5、10、11、13，且背包的容器为16，那么恰当的解决方案是选取第三件和第五件，尺寸为16刚好填满背包，总价值为23。

用来解决这个问题的递归实现代码如下：

var size = [3, 4, 7, 8, 9]
var value = [4, 5, 10, 11, 13]
var capacity = 16;
var n = 5; // 物品的件数

function knapsack(capacity, size, value, n) {
  if (n === 0 || capacity === 0) { // 背包剩余容量为0或没有物品可供判断了，即装不了，价值为0
    return 0;
  }

  if (size[n-1] > capacity) { // 装不下第n件物品，则排除该件，递归判断下一件
    return knapsack(capacity, size, value, n-1)
  } else { // 能装下
    
    // 选择装下第n件，背包容量减少size[n-1]，价值加上value[n-1]，递归去装下一件
    var addCurValue = value[n-1] + knapsack(capacity - size[n-1], size, value, n - 1)

    // 选择不装第n件，直接递归去装下一件
    var noAddCurValue = knapsack(capacity, size, value, n - 1);

    // 每当可以装下的时候都有两个递归发生
    // 选择装当前这一件装或者不装，分出两条递归计算是装划算还是不装换算，最后返回更大值即价值最大化
    return Math.max(addCurValue, noAddCurValue)
  }
}

console.log(knapsack(capacity, size, value, n)); // 23

使用动态规划算法的话，会声明一个大小为k[n][c]（n为物品数量，c为容量大小）的二维数组，其中的k[i][j]表示在面对前i件物品时，且容量为j时所能获得的最大价值。

而计算k[i][j]的方法如下：

  • 如果容量j是小于size[i]，这个时候背包容量不足以放下第i件物品，只能选择不拿，此时k[i][j] = k[i-1][j] 即面对前i-1件物品时（相当于物品列表里没有第i件时），容量为j时的最大价值。

  • 如果容量j是大于等于size[i]，这个时候背包容易可以放下第i件物品的，究竟拿还是不拿，自然要比较这两种情况那种情况价值更大一些。

    • 如果拿，就等于value[i](选择放下的这一件的价值) + k[i-1][j-size[i]](当放下这一件，剩余容量j-size[i]面对前i-1件物品时的最大价值，相当于物品列表里没有第i件时，以容量j-size[i]能获得的最大值)，即 a = value[i] + k[i-1][j-size[i]]

    • 如果不拿，k[i][j]就等于容量为j的时候，面对前i-1件物品时（相当于物品列表里没有第i件时）能够获得的最大价值，即 b = k[i-1][j]。

    • 比较两者谁大，谁大就最终赋值k[i][j] = max(a, b)

实现如下：

function max(a, b) {
  return a > b ? a : b;
}

function dKnapsack(capacity, size, value, n) {
  // 因为在理解的时候，i，j 都是从1开始
  // 而JavaScript中下标都是从0开始
  // 所以在下面21-22行的时候，会在i为0和j为0的时候往二维数组中塞0
  // 这样 k[5][16]就是表示面对前5件物品，容量为16的时候能够获得的最大价值，而不需要用k[4][15]表示

  // 在size和value两个数组最前列插入0
  // 这样当前比较的就是size[i] 也不用写作size[i-1]了
  size.unshift(0);
  value.unshift(0);

  var k = [];
  for (var i = 0; i <= n; i++) {
    k[i] = [];
    var str = ''
    for (var j = 0; j <= capacity; j++) {
      if (i === 0 || j === 0) {
        k[i][j] = 0;
      } else if (size[i] <= j) {
        k[i][j] = max(value[i] + k[i-1][j-size[i]], k[i-1][j])
      } else {
        k[i][j] = k[i-1][j];
      }
      str += ` ${k[i][j]}`
    }
    console.log(str);
  }
  return k[n][capacity]
}

var size = [3, 4, 7, 8, 9]
var value = [4, 5, 10, 11, 13]
var capacity = 16
var n = 5
console.log(dKnapsack(capacity, size, value, n)); // 23

// 最终的k如下，理解时可以当第一行和第一列不存在
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
// 0 0 0 4 4 4 4 4 4 4 4 4 4 4 4 4 4
// 0 0 0 4 5 5 5 9 9 9 9 9 9 9 9 9 9
// 0 0 0 4 5 5 5 10 10 10 14 15 15 15 19 19 19
// 0 0 0 4 5 5 5 10 11 11 14 15 16 16 19 21 21
// 0 0 0 4 5 5 5 10 11 13 14 15 17 18 19 21 23

贪心算法

贪心算法是一种以寻找“优质解”为手段从而达成整体解决方案的算法，这些优质的解决方案被称为局部最优解，将有希望得到正确的最终解决方案，也称为全局最优解。“贪心”这个术语来自于这些算法无论如何总是选择当前的最优解这个事实。通常，贪心算法会用于那些看起来近乎无法找到完整解决方案的问题，然而，出于时间和空间的考虑，次优解也是可以接受的。

贪心算法是一种比较简单的算法，总是会选择当下的最优解，而不去考虑这一次的选择会不会对未来的选择造成影响，使用贪心算法通常表明，实现者希望做出这一系列的局部“最优”选择能够带来最终的整体“最优”选择。如果局部最优确实可以带来整体最优的话，该算法将会产生一个最优解，否则则会得到一个次优解，然而对很多问题来说，寻找最优解很麻烦，这么做不值得，所以使用贪心算法就足够了。

找零问题

如果你在商店购物，消费完毕后，需要找零63块，店员要怎样给你这些零钱呢？通常生活中，就是使用的贪心算法来解决这个问题。

假设：

  • 我们只有10元、5元、1元的面额，通常会找零6张10元，3张1元。
  • 如果只有50元、10元、5元、1元的面额，通常会找零1张50元，1张10元，3张1元。

实现如下：

var total = 63;
var coins1 = [10, 5, 1]
var coins2 = [50, 10, 5, 1]

function makeChange(total, coins) { // change也有零钱的意思
  var result = [];
  var num = total;

  for (var i = 0; i < coins.length; i++) {
    var remainder = num % coins[i]; // 剩余需要找零的钱
    result.push(Math.floor(num / coins[i])) // 当前面值用了多少张
    num = remainder;
  }

  showResult(result, coins)
}

function showResult(result, coins) {
  result.forEach((r, i) => {
    console.log(`使用${coins[i]}元面值${r}张`);
  })
  console.log();
}

makeChange(total, coins1)
// 使用10元面值6张
// 使用5元面值0张
// 使用1元面值3张

makeChange(total, coins2)
// 使用50元面值1张
// 使用10元面值1张
// 使用5元面值0张
// 使用1元面值3张

背包问题的贪心算法解决方案

我们之前提到的背包问题，是常态化理解的0-1背包问题，因为你必须考虑放入整个物品或者不放入，就想你无法选择将只放入“半台电视”一样。

而反之，如果用到的物品是可拆分的，那么可以简单通过物品的单价除以单位体积来确定物品的价值，比如一包烟100元20根，那么我装入半包烟，就是10根50元。

比如我们在网络游戏世界中，拥有的背包容量是100，我们去挖矿，不管什么矿石都占一个格子，结果一锄头下去，爆出来的金矿、银矿、铜矿中加起来有200个，那么，我们肯定先装价值最高的金矿直到金矿被装完或者背包装满，接着装价值次高的银矿，直到银矿被装满或将背包装满，以此类推。

由于物品体积单位与背包体积单位是相同的，物品又都是可按照体积拆分的，那么就可以将每个物品全部拆成N个体积单元，那么在这种情况下的最优解是，先装价值最高的物品直到该物品装完或者背包装满，接着装价值次高的。这种，我们就可以使用贪心算法来解决，这类背包问题被称为部分背包问题。

以下算法用于解决部分背包问题：

（1）背包的容量为capacity，物品的价值为value，体积为size

（2）因为都是可拆分的，所以按value/size每一份的价格aPrice来排序物品。

（3）按aPrice的价值大小来考虑物品，尽可能的做到价值最大化

举例：给出下列四种物品

物品 A B C D
价值 50 140 60 60
体积 5 20 10 12
单份价格 10 7 6 5

假设背包容量为30，那么最优解就是装入所有的物品A（耗费容量5获得价值50）、装入所有的B物品（耗费容量20获得价值140）、装入一半的物品C（耗费容量5获得价值30），最终获得最大价值为220。

代码如下：

// 已经按单份价值降序排列
var values = [50, 140, 60, 60]
var sizes = [5, 20, 10, 12]
var capacity = 30

function knapsack(values, sizes, capacity) {
  var load = 0; // 已装的容量
  var maxVal = 0; // 最大价值

  for (var i = 0; i < values.length && load < capacity ; i++) {
    if (sizes[i] <= capacity - load) { // 当前考虑的物品是否可以全部装下
      // 可以装完
      maxVal += values[i]
      load += sizes[i]
    } else {
      // 不可以装完 按份装 
      // 必然会将背包装满 因为当前的物品装不完才走到了这里
      var aPrice = values[i] / sizes[i]
      maxVal += aPrice * (capacity - load)
      load = capacity; // 装满
    }
  }

  return maxVal;
}

console.log(knapsack(values, sizes, capacity)); // 220