面試官：說說你對貪心算法、回溯算法的理解？應用場景？

作者：灰灰 2021-10-18 07:51:39

開發前端算法

貪心算法，又稱貪婪算法，是算法設計中的一種思想，其期待每一個階段都是局部最優的選擇，從而達到全局最優，但是結果并不一定是最優的

[[429460]]

本文轉載自微信公眾號「JS每日一題」，作者灰灰。轉載本文請聯系JS每日一題公眾號。

一、貪心算法

貪心算法，又稱貪婪算法，是算法設計中的一種思想

其期待每一個階段都是局部最優的選擇，從而達到全局最優，但是結果并不一定是最優的

舉個零錢兌換的例子，如果你有1元、2元、5元的錢幣數張，用于兌換一定的金額，但是要求兌換的錢幣張數最少

如果現在你要兌換11元，按照貪心算法的思想，先選擇面額最大的5元錢幣進行兌換，那么就得到11 = 5 + 5 + 1 的選擇，這種情況是最優的

但是如果你手上錢幣的面額為1、3、4，想要兌換6元，按照貪心算法的思路，我們會 6 = 4 + 1 + 1這樣選擇，這種情況結果就不是最優的選擇

從上面例子可以看到，貪心算法存在一些弊端，使用到貪心算法的場景，都會存在一個特性：

一旦一個問題可以通過貪心法來解決，那么貪心法一般是解決這個問題的最好辦法

至于是否選擇貪心算法，主要看是否有如下兩大特性：

貪心選擇：當某一個問題的整體最優解可通過一系列局部的最優解的選擇達到，并且每次做出的選擇可以依賴以前做出的選擇，但不需要依賴后面需要做出的選擇
最優子結構：如果一個問題的最優解包含其子問題的最優解，則此問題具備最優子結構的性質。問題的最優子結構性質是該問題是否可以用貪心算法求解的關鍵所在

二、回溯算法

回溯算法，也是算法設計中的一種思想，是一種漸進式尋找并構建問題解決方式的策略

回溯算法會先從一個可能的工作開始解決問題，如果不行，就回溯并選擇另一個動作，知道將問題解決

使用回溯算法的問題，有如下特性：

有很多路，例如一個矩陣的方向或者樹的路徑
在這些的路里面，有死路也有生路，思路即不符合題目要求的路，生路則符合
通常使用遞歸來模擬所有的路

常見的偽代碼如下：

result = [] 
function backtrack(路徑, 選擇列表): 
  if 滿足結束條件: 
    result.add(路徑) 
  return 
 
  for 選擇 of 選擇列表: 
    做選擇 
    backtrack(路徑, 選擇列表) 
    撤銷選擇

重點解決三個問題：

路徑：也就是已經做出的選擇
選擇列表
結束條件

例如經典使用回溯算法為解決全排列的問題，如下：

一個不含重復數字的數組 nums ，我們要返回其所有可能的全排列，解決這個問題的思路是：

用遞歸模擬所有的情況
遇到包含重復元素的情況則回溯
收集到所有到達遞歸終點的情況，并返回、

用代碼表示則如下：

var permute = function(nums) { 
    const res = [], path = []; 
    backtracking(nums, nums.length, []); 
    return res; 
     
    function backtracking(n, k, used) { 
        if(path.length === k) { 
            res.push(Array.from(path)); 
            return; 
        } 
        for (let i = 0; i < k; i++ ) { 
            if(used[i]) continue; 
            path.push(n[i]); 
            used[i] = true; // 同支 
            backtracking(n, k, used); 
            path.pop(); 
            used[i] = false; 
        } 
    } 
};