大學(xué)信息技術(shù)基礎(chǔ)教程課件 6.2 算法策略

6.2算法策略6.2算法策略【問(wèn)題導(dǎo)入】

算法策略是解決問(wèn)題的方法，它指導(dǎo)算法的設(shè)計(jì)，而算法是實(shí)現(xiàn)策略的具體實(shí)現(xiàn)步驟。

在求解“計(jì)劃旅行時(shí)間和費(fèi)用”問(wèn)題中，如何搜索“行程路線規(guī)劃”問(wèn)題的解決方法？請(qǐng)?jiān)O(shè)計(jì)可實(shí)現(xiàn)的算法。6.2算法策略隨著人工智能、大數(shù)據(jù)等技術(shù)的不斷發(fā)展，算法策略在各個(gè)領(lǐng)域的應(yīng)用越來(lái)越廣泛。掌握算法策略將有助于我們更好地適應(yīng)未來(lái)社會(huì)的發(fā)展需求，提高自己的競(jìng)爭(zhēng)力。算法策略是指在問(wèn)題空間中隨機(jī)搜索所有可能的解決問(wèn)題的方法，直至選擇一種有效的方法解決問(wèn)題。6.2算法策略算法是計(jì)算思維的核心要素之一。通過(guò)學(xué)習(xí)算法，學(xué)生能夠用明確的、可執(zhí)行的操作步驟描述問(wèn)題求解方案，能夠用順序、分支和循環(huán)三種基本控制結(jié)構(gòu)設(shè)計(jì)程序解決問(wèn)題，這些都是計(jì)算思維的重要表現(xiàn)。算法（Algorithm）是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。目錄頁(yè)contents窮舉策略及算法分治策略及算法動(dòng)態(tài)規(guī)劃策略及算法貪心策略及算法1234回溯法及算法5選題背景及意義ONE窮舉策略及算法1窮舉策略及算法窮舉策略的基本思想：列舉出所有可能的情況，逐個(gè)判斷哪些是符合問(wèn)題所要求的條件，從而得到問(wèn)題的全部解答。這種策略通過(guò)系統(tǒng)地檢查問(wèn)題所有可能的情況，確保不遺漏任何一種可能性，以此來(lái)找到符合特定條件的答案。窮舉策略主要用于解決“是否存在”和“有多少可能性”等問(wèn)題，其關(guān)鍵在于如何列舉所有的情況，因?yàn)檫z漏某些情況可能會(huì)導(dǎo)致得不到正確的解。1窮舉策略及算法窮舉算法的步驟：①確定問(wèn)題的范圍：需要明確問(wèn)題的范圍，確定所有可能的解的范圍。②列舉所有可能的情況：根據(jù)問(wèn)題的條件，列舉出所有可能的情況。這可以通過(guò)順序列舉、組合列舉或排列列舉等方法實(shí)現(xiàn)。③驗(yàn)證每個(gè)情況：對(duì)每個(gè)列舉出來(lái)的情況進(jìn)行驗(yàn)證，看是否滿足問(wèn)題的所有條件。?④找出符合條件的解：在所有驗(yàn)證的情況下，找出滿足問(wèn)題條件的解。1窮舉策略及算法窮舉算法的步驟：①確定問(wèn)題的范圍：需要明確問(wèn)題的范圍，確定所有可能的解的范圍。②列舉所有可能的情況：根據(jù)問(wèn)題的條件，列舉出所有可能的情況。這可以通過(guò)順序列舉、組合列舉或排列列舉等方法實(shí)現(xiàn)。③驗(yàn)證每個(gè)情況：對(duì)每個(gè)列舉出來(lái)的情況進(jìn)行驗(yàn)證，看是否滿足問(wèn)題的所有條件。?④找出符合條件的解：在所有驗(yàn)證的情況下，找出滿足問(wèn)題條件的解。明確行程路線規(guī)劃的具體要求，如起點(diǎn)和終點(diǎn)、需要訪問(wèn)的地點(diǎn)、每個(gè)地點(diǎn)的訪問(wèn)順序等。(1)定義問(wèn)題計(jì)算路徑成本：對(duì)于每條生成的路徑，計(jì)算其總成本，這通常涉及到距離、時(shí)間的計(jì)算。(3)計(jì)算路徑成本通過(guò)組合和排列所有地點(diǎn)，生成所有可能的路徑組合。這可以通過(guò)編寫(xiě)程序或使用專門的算法來(lái)實(shí)現(xiàn)。（DFS、BFS）(2)生成所有可能的路徑比較所有路徑的成本，選擇成本最低（或滿足其他優(yōu)化目標(biāo)）的路徑作為最優(yōu)路徑。(4)選擇最優(yōu)路徑對(duì)選擇的最優(yōu)路徑進(jìn)行驗(yàn)證，確保它滿足所有約束條件，并根據(jù)需要進(jìn)一步優(yōu)化。(5)驗(yàn)證和優(yōu)化1窮舉策略及算法【例6-2-1】行程路線規(guī)劃問(wèn)題TWO2分治策略及算法2分治策略及算法分治策略的基本思想：將一個(gè)難以直接解決的大問(wèn)題，分解成一些規(guī)模較小的子問(wèn)題，這些子問(wèn)題相互獨(dú)立且與原問(wèn)題相同，然后各個(gè)擊破，分而治之。分治策略常常與遞歸結(jié)合使用：通過(guò)反復(fù)應(yīng)用分治，可以使子問(wèn)題與原問(wèn)題類型一致而規(guī)模不斷縮小，最終使子問(wèn)題縮小到很容易求解的狀態(tài)，這種算法就是遞歸算法。2分治策略及算法一般來(lái)說(shuō)，分治算法在每一層遞歸上都有3個(gè)步驟。①分解：將原問(wèn)題分解成一系列子問(wèn)題。②求解：遞歸地求解各子問(wèn)題。若子問(wèn)題足夠小，則直接求解。③合并：將子問(wèn)題的解合并成原問(wèn)題的解。2分治策略及算法歸并排序算法是一種分治算法，它將一個(gè)大問(wèn)題分解成兩個(gè)或更多個(gè)相同或相似的子問(wèn)題，直到最后子問(wèn)題可以簡(jiǎn)單的直接求解，原問(wèn)題則可通過(guò)子問(wèn)題的解合并得到解決。歸并排序算法的基本步驟如下：①分解：將當(dāng)前待排序的序列分解成兩個(gè)子序列，直到子序列的長(zhǎng)度為1，即每個(gè)元素自成一個(gè)序列。②遞歸進(jìn)行排序并合并：對(duì)每個(gè)子序列進(jìn)行排序，然后兩兩合并已排序的子序列，直到最終合并為一個(gè)完整的序列。2分治策略及算法①分解：將數(shù)組分解為更小的子數(shù)組，直到每個(gè)子數(shù)組只包含一個(gè)元素。即分解后得到：[7]，[6]，[8]，[9]，[3]，[4]，[2]，[1]子數(shù)組。②遞歸進(jìn)行排序并合并：合并這些子數(shù)組，同時(shí)在合并的過(guò)程中對(duì)它們進(jìn)行排序。這個(gè)過(guò)程可以通過(guò)遞歸實(shí)現(xiàn)，每次取兩個(gè)子數(shù)組進(jìn)行比較和合并，直到所有子數(shù)組合并為一個(gè)排序后的數(shù)組。具體步驟如下：合并[7]，[6]后得到[6,7]；合并[8]，[9]后得到[8,9]；合并[3]，[4]后得到[3,4]；合并[2]，[1]后得到[1,2]；合并[6,7]，[8,9]后得到[6,7,8,9]；合并[3,4]，[1,2]后得到[1,2,3,4]；合并[6,7,8,9]，[1,2,3,4]后得到最終歸并排序后的數(shù)組[1,2,3,4,6,7,8,9]。【例6-2-2】將無(wú)序數(shù)組[7,6,8,9,3,4,2,1]排序2分治策略及算法快速排序的基本思想是：通過(guò)一次排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列?？焖倥判蛩惴ǖ幕静襟E如下：①?gòu)臄?shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"。②重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任何一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)操作。③遞歸地把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。2分治策略及算法從[7,1,9,8,3,4,2,6]數(shù)組選6為“基準(zhǔn)”，快速排序后得到[1,3,4,2],[6],[7,9,8]；從[1,3,4,2]數(shù)組選2為"基準(zhǔn)"，快速排序后得到[1],[2],[3,4];從[3,4]數(shù)組選4為"基準(zhǔn)"，快速排序后得到[3],[4]；從[7,9,8]數(shù)組選8為"基準(zhǔn)"，快速排序后得到[7],[8],[9]；最終得到快速排序后的數(shù)組[1,2,3,4,6,7,8,9]?！纠?-2-3】將無(wú)序數(shù)組[7,1,9,8,3,4,2,6]排序THREE動(dòng)態(tài)規(guī)劃策略及算法3動(dòng)態(tài)規(guī)劃策略及算法動(dòng)態(tài)規(guī)劃策略的基本思想：與分治策略類似，也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。與分治策略不同的是，適合用動(dòng)態(tài)規(guī)劃策略求解的問(wèn)題，經(jīng)分解得到的子問(wèn)題往往不是獨(dú)立的。若用分治策略來(lái)解這類問(wèn)題，則相同的子問(wèn)題會(huì)被求解多次，以至于最后解決原問(wèn)題需要耗費(fèi)指數(shù)級(jí)時(shí)間。然而，不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。如果能夠保存已解決的子問(wèn)題的答案，在需要時(shí)再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間的算法。3動(dòng)態(tài)規(guī)劃策略及算法動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問(wèn)題。在這類問(wèn)題中，可能會(huì)有許多可行解，每個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值（最大值或最小值）的那個(gè)解。當(dāng)然，最優(yōu)解可能會(huì)有多個(gè)，動(dòng)態(tài)規(guī)劃算法能找出其中的一個(gè)最優(yōu)解。3動(dòng)態(tài)規(guī)劃策略及算法設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法，通常按照以下幾個(gè)步驟進(jìn)行。①找出最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征。②遞歸地定義最優(yōu)解的值。③以自底向上的方式計(jì)算出最優(yōu)值。④根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。步驟①～③是動(dòng)態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形下，步驟④可以省略。若需要求出問(wèn)題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟④。此時(shí)，在步驟③中計(jì)算最優(yōu)值時(shí)，通常需記錄更多的信息，以便在步驟④中根據(jù)所記錄的信息快速構(gòu)造出一個(gè)最優(yōu)解。3動(dòng)態(tài)規(guī)劃策略及算法【例6-2-4】爬樓梯問(wèn)題：有一座高度是10級(jí)臺(tái)階的樓梯，從下往上走，每跨一步只能向上1級(jí)或者2級(jí)臺(tái)階。求出一共有多少種走法。要解決一個(gè)給定的問(wèn)題，可以先解決其子問(wèn)題，再合并子問(wèn)題的解以得出原問(wèn)題的解。通常許多子問(wèn)題非常相似，為此動(dòng)態(tài)規(guī)劃法試圖只解決每個(gè)子問(wèn)題一次，從而減少計(jì)算量。一旦某個(gè)給定子問(wèn)題的解已經(jīng)算出，則將其記憶化存儲(chǔ)，以便下次需要同一個(gè)子問(wèn)題解之時(shí)直接查找。①找出最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征：通過(guò)分析題目可以得到1到10級(jí)臺(tái)階的所有走法是1到8級(jí)臺(tái)階的所有走法加上1到9級(jí)臺(tái)階的所有走法。則F(10)=F(9)+F(8)。②遞歸地定義最優(yōu)解的值：設(shè)置a保存倒數(shù)第二個(gè)子狀態(tài)數(shù)據(jù)，b保存倒數(shù)第一個(gè)子狀態(tài)數(shù)據(jù)，temp保存當(dāng)前狀態(tài)數(shù)據(jù).③以自底向上的方式計(jì)算出最優(yōu)值。3動(dòng)態(tài)規(guī)劃策略及算法【例6-2-4】爬樓梯問(wèn)題：有一座高度是10級(jí)臺(tái)階的樓梯，從下往上走，每跨一步只能向上1級(jí)或者2級(jí)臺(tái)階。求出一共有多少種走法。FOUR貪心策略及算法4貪心策略及算法心策略的基本思想：和動(dòng)態(tài)規(guī)劃策略一樣，貪心法也經(jīng)常用于解決最優(yōu)化問(wèn)題。與動(dòng)態(tài)規(guī)劃策略不同的是，貪心策略在解決問(wèn)題的策略上是僅根據(jù)當(dāng)前已有的信息做出選擇，而且一旦做出了選擇，不管將來(lái)有什么結(jié)果，這個(gè)選擇都不會(huì)改變。換而言之，貪心策略并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)。這種局部最優(yōu)選擇并不能保證總能獲得全局最優(yōu)解，但通常能得到較好的近似最優(yōu)解。4貪心策略及算法貪心算法的步驟：?①將問(wèn)題分解為多個(gè)子問(wèn)題。②選擇合適的貪心策略，得到每一個(gè)子問(wèn)題的局部最優(yōu)解。?③將子問(wèn)題的局部最優(yōu)解合并成原問(wèn)題的最優(yōu)解。4貪心策略及算法根據(jù)貪心算法，一開(kāi)始肯定是看需要幾張20的，此題需要1張，那還剩36-20=16；看完20的再來(lái)看10元的，需要1張10元，現(xiàn)在還剩16-10=6；下面繼續(xù)是看5和1，分別各需要1張；最后得到的答案是，如果想要湊齊36元最少需要4張錢幣。這個(gè)例子，每次都是用最大的紙幣去匹配，剩下的余額再用較小點(diǎn)的面額去匹配，這個(gè)就是貪心算法在對(duì)問(wèn)題進(jìn)行求解時(shí)，每次都是做出當(dāng)前看來(lái)最好的選擇。【例6-2-5】現(xiàn)在有20、10、5、1這4種數(shù)額的錢幣，如果想要湊齊36元，那最少需要幾張錢幣。4貪心策略及算法根據(jù)貪心算法，一開(kāi)始就看需要幾張10元，本例題題需要1張，剩余金額是8元；這時(shí)無(wú)法用9的紙幣，只能用8張1元的錢幣；；最后的結(jié)果是用了9張紙幣。實(shí)際上通過(guò)肉眼就能看出用2張9元的錢幣就可以了。通過(guò)這個(gè)例題說(shuō)明了通過(guò)貪心算法所得到的結(jié)果不一定是最優(yōu)的結(jié)果?！纠?-2-6】現(xiàn)在有10、9、1這3種金額的錢幣，如果想要湊齊18元，最少需要幾張錢幣。FIVE回溯法及算法5

回溯法及算法回溯法的基本思想：在確定了解空間的組織結(jié)構(gòu)后，回溯法從開(kāi)始結(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)，以深度優(yōu)先的方式搜索整個(gè)解空間。這個(gè)開(kāi)始結(jié)點(diǎn)就成為一個(gè)活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處，搜索向縱深方向移至一個(gè)新結(jié)點(diǎn)。這個(gè)新結(jié)點(diǎn)就成為一個(gè)新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動(dòng)，則當(dāng)前的擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。換句話說(shuō)，這個(gè)結(jié)點(diǎn)不再是一個(gè)活結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動(dòng)（回溯）至最近的一個(gè)活結(jié)點(diǎn)處