總結(jié)四大算法聯(lián)系與區(qū)別
以下內(nèi)容為教材：王曉東《計(jì)算機(jī)算法設(shè)計(jì)與分析（第五版）》
算法概述
有人突然問你，什么是算法？
答：算法是能解決一系列問題的清晰指令，能對(duì)一定范圍的輸入，在有限的時(shí)間內(nèi)獲得所求的輸出。
算法滿足的四個(gè)性質(zhì)是什么？
有輸入
有輸出
確定性，沒有歧義指令
有限性，時(shí)間有限。
什么是遞歸算法？
直接或間接調(diào)用自身的算法
分治思想是什么?
把一個(gè)大的問題分成若干個(gè)子問題，這些子問題相互獨(dú)立但是又和原問題相同。分治就可以遞歸的解決這些子問題，然后將這些子問題的解合并，得到原問題的解。
歸并排序的思想是什么？
將帶排序的序列分成大小大致相同的兩個(gè)子序列，分別對(duì)兩個(gè)子序列進(jìn)行排序，最終將排序好的子序列合并。
動(dòng)態(tài)規(guī)劃的思想是什么？
和分治法類似，都是將問題分解成若干個(gè)子問題，先求子問題，再結(jié)合子問題得到原問題的解，但是動(dòng)態(tài)規(guī)劃的子問題不是相互獨(dú)立的，他們之間是有依賴關(guān)系的。
貪心算法和動(dòng)態(tài)規(guī)劃的聯(lián)系是什么？
相同點(diǎn)：都具有最優(yōu)子結(jié)構(gòu)
不同點(diǎn)：選擇性質(zhì)，貪心算法只是在局部做最優(yōu)選擇。
貪心選擇性質(zhì)是什么？
所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇來達(dá)到。
這就是它和動(dòng)態(tài)規(guī)劃的主要區(qū)別。
貪心和動(dòng)態(tài)規(guī)劃的區(qū)別？
貪心算法所做的貪心選擇可以依賴以往所做的選擇但決不依賴將來所做的選擇，也不依賴子問題的解。正是由于這種差別，動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解決每個(gè)子問題，而貪心算法通常以自頂向下的方式進(jìn)行。
最優(yōu)字結(jié)構(gòu)性質(zhì)是什么？
一個(gè)問題的最優(yōu)解包含子問題的最優(yōu)解，就是具有該性質(zhì)。
為什么貪心算法不適用于01背包問題？
貪心無法保證最終能把背包裝滿，一部分閑置的空間讓每千克背包的空間價(jià)值降低了。
在考慮01背包問題的時(shí)候，應(yīng)該比較選擇物品和不選擇這個(gè)物品所導(dǎo)致的最終方案，再做出更好的選擇。
回溯法的基本思想
我以自己的方式表達(dá)：
以深度優(yōu)先的方式搜索整個(gè)解空間。來到一個(gè)解的節(jié)點(diǎn)之后修改狀態(tài)并繼續(xù)遞歸搜索，在此節(jié)點(diǎn)上遞歸結(jié)束并回到當(dāng)前解的節(jié)點(diǎn)之后將當(dāng)前修改了的節(jié)點(diǎn)狀態(tài)恢復(fù)。并以此搜索完整個(gè)解空間。
分支限界法和回溯法的區(qū)別
回溯法是dfs，分支限界法是bfs、或者最小耗費(fèi)優(yōu)先。
分支限界法的搜索策略是什么？
（看了書之后的個(gè)人理解）相當(dāng)于把廣度優(yōu)先搜索用的那個(gè)隊(duì)列改成了優(yōu)先隊(duì)列，出隊(duì)列的時(shí)候是出優(yōu)先級(jí)最高的元素。又有點(diǎn)像二維數(shù)組A*尋路算法一樣。這和以前看到視頻彈幕里有人說dfs+剪枝就是分支限界法還不太一樣。
書中提到：產(chǎn)生兒子節(jié)點(diǎn)的時(shí)候，導(dǎo)致不可行解或者導(dǎo)致非最優(yōu)解的兒子節(jié)點(diǎn)被舍棄，這一點(diǎn)倒是還挺像剪枝的。
圖片鏈接：https://s1.ax1x.com/2022/08/12/vJpXL9.png
請(qǐng)于2022年12月之后再盜此圖。
算法啟示錄
短作業(yè)優(yōu)先：手頭上有很多任務(wù)，如果突然來了一個(gè)更緊急的任務(wù)就先去做更緊急的。緊急的做完了就繼續(xù)做不那么緊急的任務(wù)。
廣度優(yōu)先學(xué)習(xí)：泛泛的學(xué)習(xí)，學(xué)這個(gè)語言那個(gè)語言，這個(gè)技術(shù)那個(gè)技術(shù)。也可以通過這個(gè)來回憶知識(shí)結(jié)構(gòu)樹。
深度優(yōu)先學(xué)習(xí)：學(xué)這個(gè)語言遇到一點(diǎn)不會(huì)的就深挖，發(fā)現(xiàn)需要解決疑問a，b，c，解決疑問a又要去解決a1,?a2..。也應(yīng)用于在房間里找鑰匙，手動(dòng)在文件夾里找一個(gè)文件。
所以學(xué)習(xí)，如果只bfs就會(huì)不深入不精通，會(huì)被面試官pass，如果只dfs就容易消磨斗志，學(xué)習(xí)速度下降，缺少新鮮感。學(xué)習(xí)要bfs和dfs結(jié)合
動(dòng)態(tài)規(guī)劃未來：自底向上，根據(jù)自己曾經(jīng)的履歷和成就來決定自己的下一步。dp[i]＝func(dp[i-1]…)，缺點(diǎn)是容易發(fā)生較大變化，比較隨性。大一上學(xué)期之所以決定走設(shè)計(jì)方向是因?yàn)楦呖己蟮氖罴傧矚g學(xué)adobe做東西，大一下之所以又決定走編程方向，是因?yàn)榇笠簧习l(fā)現(xiàn)自己編程還可以，又喜歡編程了。優(yōu)點(diǎn)是前進(jìn)動(dòng)力更大，迭代性更好。
分治：把回家這件繁瑣事情分成很多段，每段還可以分成好幾個(gè)小段。（一般現(xiàn)實(shí)生活中不會(huì)分太多），先從學(xué)校到學(xué)校所在省，再從學(xué)校省到家的省，再從家的省到家。然后再細(xì)分下去。學(xué)校到學(xué)校附近車站，車站到火車站，火車站到地鐵…
遞歸，分治出來的東西具有相同的子結(jié)構(gòu)，每日總結(jié)，每周總結(jié)，每月總結(jié)，每年總結(jié)。
二分查找：發(fā)現(xiàn)單詞不會(huì)翻字典的時(shí)候，看視頻撥動(dòng)進(jìn)度條的時(shí)候。
貪心算法：找對(duì)象，貪著貪著發(fā)現(xiàn)最終什么都沒貪到。（誤）
計(jì)入哈希表：其實(shí)在看數(shù)學(xué)書的時(shí)候，把常用的公式記錄在扉頁，做題翻書找公式不用再一頁一頁找了，直接看扉頁。就是類似這樣的思想。
插入排序：和別人打牌的發(fā)牌階段自己整理自己的牌
記憶化搜索：經(jīng)過一番大力的網(wǎng)上搜索搜到自己要解決的技術(shù)問題的時(shí)候，把這個(gè)問題保存在自己的博客里或者筆記里。以后再遇到問題先看看自己的筆記里有沒有。
