动态规划算法设计字符串比较问题_「Javascript算法设计」× 动态规划与回溯算法...

小灰灰 2023-01-12 11:35 134阅读 0赞

*  分而治之算法
 *  动态规划
 *  回溯算法

## 分而治之算法 ##

分而治之算法是算法设计的一种方式，它将一个问题分成多个和原问题相似的小问题，递归解决小问题，再将解决方式合并以解决原来的问题（例如快速排序，二分搜索等）

分而治之算法可以分成三个部分

1.  分解原问题为多个子问题（原问题的多个小实例）
2.  解决子问题，用返回解决子问题的方式的递归算法。递归算法的基本情形可以用来解决子问题
3.  组合这些子问题的解决方式，得到原问题的解

我们利用二分搜索作为例子来看看什么是分而治之，利用分而治之的理念，实现二分搜索可以是以下逻辑：

1.  分解：计算mid并搜索数组较小或较大的一半
2.  解决：在较小或较大的一半中搜索值
3.  合并：这步不需要，因为我们直接返回了索引值

function binarySearch(array, value, low, high){
         
      if(low > hight){
          // {1}
        return -1
      }
      var mid = parseInt((high + loow) / 2) // {2}
      if(array[mid] == value){
          // {3}
        return mid
      }else if(array[mid] < value){
          // {4}
        high = mid - 1 // {5}
        return binarySearch(array, value, low, high) // {6}
      }else{
         
        low = mid + 1 // {7}
        return binarySearch(array, value, low, high) // {8}
      }
    }

首先，找到找不到搜索值时的终止条件（行\{1\}），也就是当左右边界相触时，表示找不到该值，返回 -1。然后定义中间值mid（行\{2\}），判断中间值和搜索值的大小，若相等，直接返回中间值（行\{3\}），若中间值小于搜索值，这对左边子数组进行搜索，将右边边界缩小到当前中间值的前一位（行\{5\}），进行下一轮递归，若中间值大于搜索值，则对右边子数组进行搜索，将左边边界增加到当前中间值后一位（行\{7\}），进行下一轮遍历。

注意，第一次传入的函数的数组必须是经过排序的，并且low表示数组第一个下标，high表示数组最后一个下标

![68ead3a7ccd8628281060bf2f08005a2.png][]

--------------------

## 动态规划 ##

动态规划（dynamic programming，DP）是一种将复杂问题分解成更小的子问题来解决的优化技术

> 注意：动态规划和分而治之是不同的方法。分而治之方法是把问题分解成相互独立的子问题，然后组合它们的答案，而动态规划则是将问题分解成相互依赖的子问题。

用动态规划解决问题时，要遵循三个重要步骤：

1.  定义子问题
2.  实现要反复执行来解决子问题的部分
3.  识别并求解出基线条件

下面我们通过两个例子来看动态规划的实战操作（背包问题，最长公共子序列）

**· 背包问题**

背包问题是一个组合优化问题，它可以描述如下：

给定一个固定大小，能够携重量W的背包，以及以组有价值和重要的物品，找出一个最佳解决方案，使得装入背包的物品总重量不超过W，且总价值最大

例子：

![aeb785ad60d335a41701778026c52527.png][]

考虑背包能够携带的重要只有5，我们规定只能往背包里装完整的物品（0-1背包）。对于这个例子，我们可以说最佳解决方案是往背包里装入物品1和物品2，这样总重要5，总价值为7

我们来实现这个背包算法：

我们来分析上面这段代码是如何工作的

搜先，初始化将用于寻找解决方案的矩阵（行\{1\}）。矩阵为 kS\[n+1\]\[capacity + 1\]。然后，忽略矩阵的第一列和第一行，只处理索引不为0的列和行（行\{2\}）并且要迭代数组中每个可用的项。物品i的重要必须小于约束capacity（行\{3\}）才有可能成为解决方案的一部分；否则，总重要就会超出背包能够携带的重要，这是不可能发生的。发生这种情况时，只要忽略它，用之前的值就可以了（行\{5\}）。当找到可以构成解决方案的物品时，选择价值最大的那个（行\{4\}）。然后，问题的解决方案就在这个二维表格右下角的最后一个格子里（行\{7\}）

我们做一个测试用例

const values = [3,4,5]
    weights = [2,3,4]
    capacity = 5
    n = values.length

下图说明例子中kS矩阵的构造

![73f2651f799474040c62e5059a151e78.png][]

请注意，这个算法只输出背包携带物品价值的最大值，而不列出实际的物品。我们可以增加下面的附加函数找出构成解决方案的物品（行\{6\}）

function findValues(n, capacity, kS, weights, values){
         
      let i = n
      let k = capacity
      console.log('构成解的物品：')
      while(i > 0 && k > 0){
         
        if(kS[i][k] !== kS[i-1][k]){
         
          console.log(`物品${
         i}可以是解的一部分 w,v:${
         weights[i - 1]},${
         values[i-1]}`)
          i--
          k -= kS[i][k]
        }else{
         
          i--
        }
      }
    }

**· 最长公共子序列**

另一个经常被当作编程挑战问题的动态规划问题是最长公共子序列（LCS）：找出两个字符串序列的最长子序列的长度。最长子序列是指，在两个字符串序列中以相同顺序出现，但不要求连续（非字符串子串）的字符串序列

考虑如下的例子。

![c7d67e569142b11de8fa3d1d60a1a4e7.png][]

再看看具体的算法

与背包问题比较，我们会发现两者非常相似，这项从顶部开始构建解决方案的技术被称为记忆化，而解决方案就在表格或矩阵的右下角

我们用图来展示：

![9e1c8781481f9f84a8c809f6a9c4a955.png][]

--------------------

## 回溯算法 ##

回溯是一种渐进式寻找并构建问题解决方式的策略。我们从一个**可能的动作**开始并试着用这个动作解决问题。如果不能解决，就回溯并选择另一个动作直到将问题解决。根据这种行为，回溯算法会尝试所有可能的动作（如果更快找到了解决方法就尝试较少的次数）来解决问题

我们以迷宫老鼠问题来看回溯算法

假设我们有一个大小为N x N的矩阵，矩阵的每个位置是一个方块。每个位置（或块）可以是空闲的（值为1）或是被阻挡的（值为0），如下图所示，其中S是起点，D是终点

![13e71127dc3443b8922586a666c062c5.png][]

矩阵就是迷宫，‘老鼠’的目标是从位置\[0\]\[0\]开始并移动到\[n-1\]\[n-1\]（终点）。老鼠可以在垂直或水平方向上任何未被阻挡的位置间移动

我们先声明下算法的基本结构

首先创建一个包含解的矩阵。将每个位置初始化为零（行\{1\}）。对于老鼠采取的每步行为，我们将路径标记为1。如果算法能够找到一个解（行\{2\}），就返回解决矩阵，否则返回一条错误信息（行\{3\}）

然后我们开始构思findPath函数，它会试着从位置x和y开始在给定的maze矩阵中找到一个解。回溯技巧也使用递归，这也是这个算法有回溯能力的原因

function findPath(maze, x, y, solution){
         
      const Len = maze.length
      
      if(x === Len - 1 && y === Len - 1){
           // {4}
        solution[x][y] = 1
        return true
      }
    
      if(isSafe(maze, x, y) === true){
           // {5}
        solution[x][y] = 1  // {6}
        if(findPath(maze, x + 1, y, solution){
           // {7}
          return true
        }
        if(findPath(maze, x, y+1, solution){
           // {8}
          return true
        }
    
        solution[x][y] = 0  // {9}
        return false
      }
      return false  // {10}
    }

算法的第一步是验证老鼠是否到达了终点（行\{4\}），如果到了，就将最后一个位置标记为路径的一部分并且返回true，表示移动成功结束。如果不是最后一步，要验证老鼠能否安全移动至该位置（行\{5\} 表示根据下面声明的isSafe方法判断出该位置空闲）。如果是安全的，我们将这步加入路径（行\{6\}）并试着在maze矩阵中水平移动（向右）到下一个位置（行\{7\}）。如果水平移动不可行，我们就试着垂直向下移动到下一个位置（行\{8\}）。如果水平和垂直都不能移动，那么将这步从路径中移除并回溯（行\{9\}），表示算法会尝试另一个可能的解。在算法尝试了所有可能的动作之后还是找不到解时，就返回false（行\{10\}），表示这个问题无解

实现isSafe函数

function isSafe(maze, x, y){
         
      const Len = maze.length
      
      if(x >= 0 && y >= 0 && x < Len && y < Len && maze[x][y] !== 0){
         
        return true
      }
      return false
    }

下面进行测试

const maze = [
      [1,0,0,0],
      [1,1,1,1],
      [0,0,1,0],
      [0,1,1,1]
    ]
    console.log(ratInAMaze(maze))

[68ead3a7ccd8628281060bf2f08005a2.png]: /images/20221119/2817aa2119b9475a9015b7a74abb9fda.png
[aeb785ad60d335a41701778026c52527.png]: /images/20221119/3986926d44dc44718a53ac5eee15a6b2.png
[73f2651f799474040c62e5059a151e78.png]: /images/20221119/64704b77c7b0412f863d8e6969f021a7.png
[c7d67e569142b11de8fa3d1d60a1a4e7.png]: /images/20221119/44aa0ae01b634603a21bae195bbed4a5.png
[9e1c8781481f9f84a8c809f6a9c4a955.png]: /images/20221119/66044b77e0b140f2acd28f856950a3cb.png
[13e71127dc3443b8922586a666c062c5.png]: /images/20221119/9ce6effc7f3048b0a40eef7a17bdb891.png