如何設計演演算法？常見的演演算法正規化介紹

如何設計演演算法？下面本篇文章給大家分析一下常見的演演算法正規化。有一定的參考價值，有需要的朋友可以參考一下，希望對大家有所幫助。

首先明確三個概念：

演演算法： 按步驟解決問題的過程。

正規化： 思考問題的模式。

演演算法正規化： 為問題構建高效解決方案的常規方法。

本文討論一些常用的演演算法正規化，例如

分治演演算法
動態規劃
貪婪演演算法
回溯演演算法

分治法

在排序演演算法中，合併和快速排序這兩種演演算法的共同點就是分而治之的演演算法。

分而治之是一種常見的演演算法設計，它的思路是把問題分解為與原始問題相似的較小子問題。通常以遞迴方式解決子問題，並結合子問題的解決方案來解決原始問題。

分治法的邏輯可以分為三個步驟：

將原始問題劃分為較小的子問題。
通過遞迴解決子問題，解決完畢之後返回子問題的解決方案。
將子問題的解決方案合併為原始問題的解決方案。

分治法的例子：二叉搜尋

下面是用分治實現的二叉搜尋。

function binarySearchRecursive(array, value, low, high) {
    if (low <= high) {
        const mid = Math.floor((low + high) / 2);
        const element = array[mid];

        if (element < value) {
            return binarySearchRecursive(array, value, mid + 1, high);
        } else if (element > value) {
            return binarySearchRecursive(array, value, low, mid - 1);
        } else {
            return mid;
        }
    }
    return null;
}

export function binarySearch(array, value) {
    const sortedArray = quickSort(array);
    const low = 0;
    const high = sortedArray.length - 1;

    return binarySearchRecursive(array, value, low, high);
}

請注意，上面的 binarySearch 函數是供他人呼叫的，而 binarySearchRecursive 是實現分治法的地方。

動態規劃法

動態規劃是一種優化技術，用於通過把複雜問題分解為較小的子問題來解決。看上去很像是分治法，但動態規劃不是把問題分解為獨立的子問題然後再組合在一起，而是隻把問題分解為獨立的子問題。

演演算法邏輯分為三個步驟：

定義子問題。
重複解決子問題。
識別並解決基本問題。

動態規劃案例：最小硬幣找零問題

這是一個名為為硬幣找零問題的常見面試題。硬幣找零問題是給定找零的金額，找出可以用多少特定數量的硬幣來找零的方式。最小硬幣找零問題只是找到使用給定面額的錢所需的最少硬幣數量。例如，如果需要找零 3 毛 7 分，則可以使用 1 個 2 分，1個 5 分，1 個 1 毛錢和1個 2 毛錢。

function minCoinChange(coins, amount) {
    const cache = [];
    const makeChange = (value) => {
        if (!value) {
            return [];
        }
        if (cache[value]) {
            return cache[value];
        }
        let min = [];
        let newMin;
        let newAmount;
        for (let i = 0; i < coins.length; i++) {
            const coin = coins[i];
            newAmount = value - coin;
            if (newAmount >= 0) {
                newMin = makeChange(newAmount);
            }
            if (newAmount >= 0 && 
            (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)) {
                min = [coin].concat(newMin);
            }
        }
        return (cache[value] = min);
    }
    return makeChange(amount);
}

在上面的程式碼中，引數 coins 表示面額（在人民幣中為 [1, 2, 5, 10, 20, 50]）。為了防止重複計算，用到了一個 cache 。 makeChange 函數是遞迴實現的，它是一個內部函數，可以存取 cache。

console.log(minCoinChange([1, 2, 5 10, 20], 37)); // => [2, 5, 10, 20]
console.log(minCoinChange([1, 3, 4], 6)) // => [3, 3]

貪婪演演算法

貪婪演演算法與當前的最優解決方案相關，並試圖找到一個全域性的最佳方案。與動態規劃不同，它不考慮全域性。貪婪演演算法傾向於簡單直觀，但可能不是整體最優的解決方案。

貪婪演演算法案例：最小硬幣找零問題

上面用動態規劃解決的硬幣問題也可以用貪婪演演算法解決。這個解決方案的是否能得到最優解取決於所採用的面額。

function minCoinChange(coins, amount) {
    const change = [];
    let total = 0;
    for (let i = coins.length; i>= 0; i--) {
        const coin = coins[i];
        while (total + coin <= amount) {
            change.push(coin);
            total += coin;
        }
    }
    return change;
}

可以看到，貪婪演演算法比動態規劃的方案要簡單得多。下面看一下同樣的求解案例，來了解兩者之間的區別：

console.log(minCoinChange([1, 2, 5 10, 20], 37)); // => [2, 5, 10, 20]
console.log(minCoinChange([1, 3, 4], 6)) // => [4, 1, 1]

貪婪演演算法給出了第一個問題的最優解，但第二個並不是最優解（應該是 [3，3]）。

貪婪演演算法比動態規劃演演算法要簡單而且更快，但是得到的有可能不是最優解。

回溯演演算法

回溯演演算法非常適合逐步查詢和構建解決方案。

嘗試以一種方式解決問題。
如果它不起作用，就回溯並重復步驟 1，直到找到合適的解決方案為止。

對於回溯演演算法，我會另寫一篇文章來介紹更復雜的演演算法。究竟寫什麼我還沒想好，也許是寫一個對數獨求解的程式，如果你對這個感興趣，請關注我的公眾號！

演演算法是永無止境的，希望本文能幫你瞭解一些常見的演演算法正規化。

相關免費學習推薦：

以上就是如何設計演演算法？常見的演演算法正規化介紹的詳細內容，更多請關注TW511.COM其它相關文章！