數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)

首先看數(shù)據(jù)結(jié)構(gòu)的知識(shí)點(diǎn)都有哪些毫深，如下圖所示。

隊(duì)列和棧是經(jīng)常使用的數(shù)據(jù)結(jié)構(gòu)毒姨，需要了解它們的特點(diǎn)哑蔫。隊(duì)列是先進(jìn)先出，棧是后進(jìn)先出弧呐。

表鸳址，包括很多種，有占用連續(xù)空間的數(shù)組泉懦、用指針鏈接的單向和雙向鏈表稿黍，首尾相接的循環(huán)鏈表、以及散列表崩哩，也叫哈希表巡球。

圖，在特定領(lǐng)域使用的比較多邓嘹，例如路由算法中會(huì)經(jīng)常使用到酣栈，圖分為有向圖、無(wú)向圖及帶權(quán)圖汹押，這部分需要掌握?qǐng)D的深度遍歷和廣度遍歷算法矿筝，了解最短路徑算法。

樹(shù)的內(nèi)容棚贾，樹(shù)一般用作查找與排序的輔助結(jié)構(gòu)窖维，剩下兩個(gè)部分都和樹(shù)有關(guān)榆综，一個(gè)是二叉樹(shù)，一個(gè)是多叉樹(shù)铸史。

多叉樹(shù)包括 B 樹(shù)族鼻疮，有 B 樹(shù)、B+ 樹(shù)琳轿、B* 樹(shù)判沟，比較適合用來(lái)做文件檢索；另外一個(gè)是字典樹(shù)崭篡，適合進(jìn)行字符串的多模匹配挪哄。

二叉樹(shù)包括平衡二叉樹(shù)、紅黑樹(shù)琉闪、哈夫曼樹(shù)中燥，以及堆，適合用于進(jìn)行數(shù)據(jù)查找和排序塘偎。這部分需要了解二叉樹(shù)的構(gòu)建疗涉、插入、刪除操作的實(shí)現(xiàn)吟秩，需要掌握二叉樹(shù)的前序咱扣、中序、后序遍歷涵防。

算法知識(shí)點(diǎn)

來(lái)看算法部分的知識(shí)點(diǎn)匯總闹伪，如下圖所示。

算法題的常用解題方法壮池。

復(fù)雜度是衡量算法好壞的標(biāo)準(zhǔn)之一偏瓤，我們需要掌握計(jì)算算法時(shí)間復(fù)雜度和空間復(fù)雜度的方法。計(jì)算時(shí)間復(fù)雜度的方法一般是找到執(zhí)行次數(shù)最多的語(yǔ)句椰憋，然后計(jì)算語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)厅克，最后用大寫 O 來(lái)表示結(jié)果。

常用的字符串匹配算法橙依，了解不同算法的匹配思路证舟。

排序也是經(jīng)常考察的知識(shí)點(diǎn)窗骑，排序算法分為插入女责、交換、選擇创译、歸并抵知、基數(shù)五類，其中快速排序和堆排序考察的頻率最高，要重點(diǎn)掌握刷喜，需要能夠手寫算法實(shí)現(xiàn)残制。

常用的查找算法，包括二分查找吱肌、二叉排序樹(shù)、B 樹(shù)仰禽、Hash氮墨、BloomFilter 等，需要了解它們的適用場(chǎng)景吐葵，例如二分查找適合小數(shù)量集內(nèi)存查找规揪，B 樹(shù)適合文件索引，Hash 常數(shù)級(jí)的時(shí)間復(fù)雜度更適合對(duì)查找效率要求較高的場(chǎng)合温峭，BloomFilter 適合對(duì)大數(shù)據(jù)集進(jìn)行數(shù)據(jù)存在性過(guò)濾猛铅。

詳解二叉搜索樹(shù)

二叉搜索樹(shù)

如下圖所示，二叉搜索樹(shù)滿足這樣的條件凤藏，每個(gè)節(jié)點(diǎn)包含一個(gè)值奸忽，每個(gè)節(jié)點(diǎn)至多有兩個(gè)子樹(shù)。每個(gè)節(jié)點(diǎn)左子樹(shù)節(jié)點(diǎn)的值都小于自身的值揖庄，每個(gè)節(jié)點(diǎn)右子樹(shù)節(jié)點(diǎn)的值都大于自身的值栗菜。

二叉樹(shù)的查詢時(shí)間復(fù)雜度是 log(N)，但是隨著不斷的插入蹄梢、刪除節(jié)點(diǎn)疙筹，二叉樹(shù)的樹(shù)高可能會(huì)不斷變大，當(dāng)一個(gè)二叉搜索樹(shù)所有節(jié)點(diǎn)都只有左子樹(shù)或者都只有右子樹(shù)時(shí)禁炒，其查找性能就退化成線性的了而咆。

平衡二叉樹(shù)

平衡二叉樹(shù)可以解決上面這個(gè)問(wèn)題，平衡二叉樹(shù)保證每個(gè)節(jié)點(diǎn)左右子樹(shù)的高度差的絕對(duì)值不超過(guò) 1幕袱，例如 AVL 樹(shù)暴备。AVL 樹(shù)是嚴(yán)格的平衡二叉樹(shù)，插入或刪除數(shù)據(jù)時(shí)可能經(jīng)常需要旋轉(zhuǎn)來(lái)保持平衡们豌，比較適合插入馍驯、刪除比較少的場(chǎng)景。

紅黑樹(shù)

紅黑樹(shù)是一種更加實(shí)用的非嚴(yán)格的平衡二叉樹(shù)玛痊。紅黑樹(shù)更關(guān)注局部平衡而非整體平衡汰瘫，確保沒(méi)有一條路徑會(huì)比其他路徑長(zhǎng)出 2 倍，所以是接近平衡的擂煞，但減少了許多不必要的旋轉(zhuǎn)操作混弥，更加實(shí)用。前面提到過(guò)，Java 8 的 HashMap 中就應(yīng)用了紅黑樹(shù)來(lái)解決散列沖突時(shí)的查找問(wèn)題蝗拿。TreeMap 也是通過(guò)紅黑樹(shù)來(lái)保證有序性的晾捏。

紅黑樹(shù)除了擁有二叉搜索樹(shù)的特點(diǎn)外，還有以下規(guī)則哀托，如下圖所示惦辛。

每個(gè)節(jié)點(diǎn)不是紅色就是黑色。

根節(jié)點(diǎn)是黑色仓手。

每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)胖齐，如圖中的黑色三角。

紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色的嗽冒。

任意節(jié)點(diǎn)到其葉節(jié)點(diǎn)的每條路徑上呀伙，包含相同數(shù)量的黑色節(jié)點(diǎn)。? ??

詳解?B 樹(shù)

B?樹(shù)

B 樹(shù)是一種多叉樹(shù)添坊，也叫多路搜索樹(shù)剿另。B 樹(shù)中每個(gè)節(jié)點(diǎn)可以存儲(chǔ)多個(gè)元素，非常適合用在文件索引上贬蛙，可以有效減少磁盤 IO 次數(shù)雨女。B 樹(shù)中所有結(jié)點(diǎn)的最大子節(jié)點(diǎn)數(shù)稱為 B 樹(shù)的階，如下圖所示是一棵 3 階 B 樹(shù)阳准，也叫 2-3 樹(shù)戚篙。

一個(gè) m 階 B 樹(shù)有如下特點(diǎn)：

非葉節(jié)點(diǎn)最多有 m 棵子樹(shù)；

根節(jié)點(diǎn)最少有兩個(gè)子樹(shù)溺职，非根岔擂、非葉節(jié)點(diǎn)最少有 m/2 棵子樹(shù)；

非葉子結(jié)點(diǎn)中保存的關(guān)鍵字個(gè)數(shù)浪耘，等于該節(jié)點(diǎn)子樹(shù)個(gè)數(shù)?1乱灵，就是說(shuō)一個(gè)節(jié)點(diǎn)如果有 3棵子樹(shù)，那么其中必定包含 2 個(gè)關(guān)鍵字七冲；

非葉子節(jié)點(diǎn)中的關(guān)鍵字大小有序痛倚，如上圖中左邊的節(jié)點(diǎn)中 37、51 兩個(gè)元素就是有序的澜躺；

節(jié)點(diǎn)中每個(gè)關(guān)鍵字的左子樹(shù)中的關(guān)鍵字都小于該關(guān)鍵字蝉稳，右子樹(shù)中的關(guān)鍵字都大于該關(guān)鍵字。如上圖中關(guān)鍵字 51 的左子樹(shù)有 42掘鄙、49耘戚，都小于 51，右子樹(shù)的節(jié)點(diǎn)有 59操漠，大于51收津；

所有葉節(jié)點(diǎn)都在同一層。

B 樹(shù)在查找時(shí)，從根結(jié)點(diǎn)開(kāi)始撞秋，對(duì)結(jié)點(diǎn)內(nèi)的有序的關(guān)鍵字序列進(jìn)行二分查找长捧，如果找到就結(jié)束，沒(méi)有找到就進(jìn)入查詢關(guān)鍵字所屬范圍的子樹(shù)進(jìn)行查找吻贿，直到葉節(jié)點(diǎn)串结。

總結(jié)一下：

B 樹(shù)的關(guān)鍵字分布在整顆樹(shù)中，一個(gè)關(guān)鍵字只出現(xiàn)在一個(gè)節(jié)點(diǎn)中舅列；

搜索可能在非葉節(jié)點(diǎn)停止肌割；

B 樹(shù)一般應(yīng)用在文件系統(tǒng)。

B+?樹(shù)

下圖是 B 樹(shù)的一個(gè)變種剧蹂，叫作 B+ 樹(shù)声功。

B+ 樹(shù)的定義與 B 樹(shù)基本相同烦却，除了下面這幾個(gè)特點(diǎn)宠叼。

節(jié)點(diǎn)中的關(guān)鍵字與子樹(shù)數(shù)目相同，比如節(jié)點(diǎn)中有 3 個(gè)關(guān)鍵字其爵，那么就有 3 棵子樹(shù)冒冬；

關(guān)鍵字對(duì)應(yīng)的子樹(shù)中的節(jié)點(diǎn)都大于或等于關(guān)鍵字，子樹(shù)中包括關(guān)鍵字自身摩渺；

所有關(guān)鍵字都出現(xiàn)在葉子節(jié)點(diǎn)中简烤；

所有葉子節(jié)點(diǎn)都有指向下一個(gè)葉子節(jié)點(diǎn)的指針。

與 B 樹(shù)不同摇幻，B+ 樹(shù)在搜索時(shí)不會(huì)在非葉子節(jié)點(diǎn)命中横侦，一定會(huì)查詢到葉子節(jié)點(diǎn)；另外一個(gè)绰姻，葉子節(jié)點(diǎn)相當(dāng)于數(shù)據(jù)存儲(chǔ)層枉侧，保存關(guān)鍵字對(duì)應(yīng)的數(shù)據(jù)，而非葉子節(jié)點(diǎn)只保存關(guān)鍵字和指向葉節(jié)點(diǎn)的指針狂芋，不保存關(guān)鍵字對(duì)應(yīng)的數(shù)據(jù)榨馁，所以同樣數(shù)量關(guān)鍵字的非葉節(jié)點(diǎn)，B+ 樹(shù)比 B 樹(shù)要小很多帜矾。

B+ 樹(shù)更適合索引系統(tǒng)翼虫，MySQL 數(shù)據(jù)庫(kù)的索引就提供了 B+ 樹(shù)實(shí)現(xiàn)。原因有三個(gè)：

由于葉節(jié)點(diǎn)之間有指針相連屡萤，B+ 樹(shù)更適合范圍檢索珍剑；

由于非頁(yè)節(jié)點(diǎn)只保存關(guān)鍵字和指針，同樣大小非葉節(jié)點(diǎn)死陆，B+ 樹(shù)可以容納更多的關(guān)鍵字次慢，可以降低樹(shù)高，查詢時(shí)磁盤讀寫代價(jià)更低；

B+ 樹(shù)的查詢效率比較穩(wěn)定迫像。任何關(guān)鍵字的查找必須走一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路劈愚，所有關(guān)鍵字查詢的路徑長(zhǎng)度相同，效率相當(dāng)闻妓。

最后可以簡(jiǎn)單了解菌羽，還有一種 B* 樹(shù)的變種，在 B+ 樹(shù)的非葉節(jié)點(diǎn)上由缆，也增加了指向同一層下一個(gè)非葉節(jié)點(diǎn)的指針注祖。

詳解字符串匹配

字符串匹配問(wèn)題

在面試時(shí)，字符串相關(guān)的問(wèn)題經(jīng)常作為算法考察題均唉，下面來(lái)看字符串匹配的問(wèn)題是晨。先來(lái)了解一道常考的面試題：“判斷給定字符串中的括號(hào)是否匹配”舔箭。

一般面試題目的描述都比較簡(jiǎn)單罩缴，在解答前，可以跟面試官進(jìn)一步溝通一下題目要求和細(xì)節(jié)层扶。以這道題為例箫章，可以跟面試官確認(rèn)括號(hào)的范圍，是不是只考慮大中小括號(hào)就可以镜会，包不包括尖括號(hào)檬寂；對(duì)函數(shù)的入?yún)⒑头祷刂涤袥](méi)有什么樣的要求；需不需要考慮針對(duì)大文件的操作等戳表。

我們假定細(xì)化后本題的要求為：只考慮大中小括號(hào)桶至；不考慮針對(duì)大文件的操作，以字符串作為入?yún)⒇倚瘢祷刂禐椴紶栴愋土鸵伲晃闯霈F(xiàn)括號(hào)也算作匹配的情況。那么季率，解題思路如下野瘦。

字符匹配問(wèn)題可以考慮使用棧的特性來(lái)處理。

遇到左括號(hào)時(shí)入棧飒泻，遇到右括號(hào)時(shí)出棧對(duì)比鞭光，看是不是成對(duì)的括號(hào)。

當(dāng)匹配完成時(shí)泞遗，如果棧內(nèi)為空說(shuō)明匹配惰许，否則說(shuō)明左括號(hào)多于右括號(hào)。

字符串代碼

來(lái)看實(shí)際的實(shí)現(xiàn)代碼史辙，如下圖所示(巧妙運(yùn)用hahmap把對(duì)應(yīng)括號(hào)用key和value的方式存儲(chǔ))汹买。

按照上面的思路佩伤，需要對(duì)字符串進(jìn)行遍歷，所以首先要能確定棧操作的觸發(fā)條件晦毙，就是定義好括號(hào)對(duì)生巡，方便入棧和出棧匹配。這里要注意见妒，編碼實(shí)現(xiàn)時(shí)一定要注意編碼風(fēng)格與規(guī)范孤荣，例如變量命名必須要有明確意義，不要簡(jiǎn)單使用 a须揣、b 這種沒(méi)有明確意義的變量名盐股。

我們首先定義了 brackets 的 map，key 是所有右括號(hào)耻卡，value 是對(duì)應(yīng)的左括號(hào)疯汁，這樣定義方便出棧時(shí)對(duì)比括號(hào)是否是成對(duì)。

再看一下匹配函數(shù)的邏輯卵酪。這里也要注意幌蚊，作為工具類函數(shù)，要做好健壯性防御凛澎，首先要對(duì)輸入?yún)?shù)進(jìn)行驗(yàn)空霹肝。

然后我們定義一個(gè)保存字符類型的棧估蹄，開(kāi)始對(duì)輸入的字符串進(jìn)行遍歷塑煎。

如果當(dāng)前字符是 brackets 中的值，也就是左括號(hào)臭蚁，則入棧最铁。這里要注意，map 的值查詢方法是 O(N) 的垮兑，因?yàn)楸绢}中括號(hào)種類很少冷尉，才使用這種方式讓代碼更簡(jiǎn)潔一些。如果當(dāng)前字符不是左括號(hào)系枪，在使用 containskey 來(lái)判斷是不是右括號(hào)雀哨。如果是右括號(hào)，需要檢驗(yàn)是否匹配私爷，如果棧為空表示右括號(hào)多于左括號(hào)雾棺，如果棧不空，但出棧的左括號(hào)不匹配衬浑，這兩種情況都說(shuō)明字符串中的括號(hào)是不匹配的捌浩。

當(dāng)遍歷完成時(shí)，如果棧中沒(méi)有多余的左括號(hào)工秩，則匹配尸饺。

最后強(qiáng)調(diào)一下：編碼題除了編程思路进统，一定要注意編程風(fēng)格和細(xì)節(jié)點(diǎn)的處理。

字符串解題思路

接下來(lái)浪听，總結(jié)一下字符串匹配類問(wèn)題的解題技巧螟碎。

首先要認(rèn)真審題，避免答偏迹栓「可以先確定是單模式匹配問(wèn)題還是多模式匹配問(wèn)題，命中條件是否有多個(gè)迈螟。

然后確定對(duì)算法時(shí)間復(fù)雜度或者內(nèi)存占用是否有額外要求叉抡。

最后要明確期望的返回值是什么，比如存在有多個(gè)命中結(jié)果時(shí)答毫，是返回第一個(gè)命中的褥民，還是全部返回。

關(guān)于解題思路洗搂。

如果是單模式匹配問(wèn)題消返，可以考慮使用 BM 或者 KMP 算法。

如果是多模匹配耘拇，可以考慮使用 Tire 樹(shù)來(lái)解決撵颊。

在實(shí)現(xiàn)匹配算法時(shí)，可以考慮用前綴或者后綴匹配的方式來(lái)進(jìn)行惫叛。

最后可以考慮是否能夠通過(guò)棧倡勇、二叉樹(shù)或者多叉樹(shù)等數(shù)據(jù)結(jié)構(gòu)來(lái)輔助解決。

建議了解一下常見(jiàn)的字符串單模嘉涌、多模匹配算法的處理思路妻熊。

詳解?TopK

TopK?問(wèn)題

TopK 問(wèn)題是在實(shí)際業(yè)務(wù)中經(jīng)常出現(xiàn)的典型問(wèn)題，例如微博的熱門排行就屬于 TopK 問(wèn)題仑最。

TopK 一般是要求在 N 個(gè)數(shù)的集合中找到最小或者最大的 K 個(gè)值扔役，通常 N 都非常得大。TopK 可以通過(guò)排序的方式解決警医，但是時(shí)間復(fù)雜度較高亿胸，一般是 O(nk)，這里我們來(lái)看看更加高效的方法预皇。

如下圖所示侈玄，首先取前 K 個(gè)元素建立一個(gè)大根堆，然后對(duì)剩下的 N-K 個(gè)元素進(jìn)行遍歷深啤，如果小于堆頂?shù)脑剞致瑒t替換掉堆頂元素，然后調(diào)整堆溯街。當(dāng)全部遍歷完成時(shí)诱桂，堆中的 K 個(gè)元素就是最小的 K 個(gè)值洋丐。

這個(gè)算法的時(shí)間復(fù)雜度是 N*logK。算法的優(yōu)點(diǎn)是不用在內(nèi)存中讀入全部的元素挥等，能夠適用于非常大的數(shù)據(jù)集友绝。

TopK 變種問(wèn)題

TopK 變種的問(wèn)題，就是從 N 個(gè)有序隊(duì)列中肝劲，找到最小或者最大的 K 個(gè)值迁客。這個(gè)問(wèn)題的不同點(diǎn)在于，是對(duì)多個(gè)數(shù)據(jù)集進(jìn)行排序辞槐。由于初始的數(shù)據(jù)集是有序的掷漱，因此不需要遍歷完 N 個(gè)隊(duì)列中所有的元素。因此榄檬，解題思路是如何減少要遍歷的元素卜范。

解題思路如下圖所示。

第一步先用 N 個(gè)隊(duì)列的隊(duì)頭元素鹿榜，也就是每個(gè)隊(duì)列的最小元素海雪，組成一個(gè)有 K 個(gè)元素的小根堆。方式同 TopK 中的方法舱殿。

第二步獲取堆頂值奥裸，也就是所有隊(duì)列中最小的一個(gè)元素。

第三步用這個(gè)堆頂元素所在隊(duì)列的下一個(gè)值放入堆頂沪袭，然后調(diào)整堆湾宙。

最后重復(fù)這個(gè)步驟直到獲取夠 K 個(gè)數(shù)。

這里還可以有個(gè)小優(yōu)化就是第三步往堆頂放入新值時(shí)枝恋，跟堆的最大值進(jìn)行一下比較创倔，如果已經(jīng)大于堆中最大值嗡害，就可以提前終止循環(huán)了焚碌。這個(gè)算法的時(shí)間復(fù)雜度是 (N+K-1)*logK，注意這里與隊(duì)列的長(zhǎng)度無(wú)關(guān)霸妹。

詳解常用算法

算法的知識(shí)點(diǎn)比較多十电，提高算法解題能力需要適當(dāng)刷題，但不能單純依靠刷題來(lái)解決問(wèn)題叹螟。需要掌握幾種常用解題思路與方法鹃骂，才能以不變應(yīng)萬(wàn)變。這里講一下：分治罢绽、動(dòng)態(tài)規(guī)劃畏线、貪心、回溯和分支界定這五種常用的算法題解題方法良价，來(lái)看看它們分別適用于什么場(chǎng)景寝殴，如何應(yīng)用蒿叠。

分治法

分治法的思想是將一個(gè)難以直接解決的復(fù)雜問(wèn)題或者大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題蚣常，分而治之市咽。比如快速排序、歸并排序等都是應(yīng)用了分治法抵蚊。

適合使用分治法的場(chǎng)景需要滿足三點(diǎn)要求：

可以分解為子問(wèn)題施绎；

子問(wèn)題的解可以合并為原問(wèn)題的解；

子問(wèn)題之間沒(méi)有關(guān)聯(lián)贞绳。

使用分治法解決問(wèn)題的一般步驟如下圖表格所示谷醉。

第一步，要找到最小子問(wèn)題的求解方法冈闭；

第二步孤紧，要找到合并子問(wèn)題解的方法；

第三步拒秘，要找到遞歸終止條件号显。

動(dòng)態(tài)規(guī)劃法

動(dòng)態(tài)規(guī)劃法，與分治法類似躺酒，也是將問(wèn)題分解為多個(gè)子問(wèn)題押蚤。與分治法不同的是，子問(wèn)題的解之間是有關(guān)聯(lián)的羹应。前一子問(wèn)題的解揽碘，為后一子問(wèn)題的求解提供了有用的信息。動(dòng)態(tài)規(guī)劃法依次解決各子問(wèn)題园匹，在求解每一個(gè)子問(wèn)題時(shí)雳刺，列出所有局部解，通過(guò)決策保留那些有可能達(dá)到全局最優(yōu)的局部解裸违。最后一個(gè)子問(wèn)題的解就是初始問(wèn)題的解掖桦。

使用動(dòng)態(tài)規(guī)劃的場(chǎng)景需要也滿足三點(diǎn)條件：

子問(wèn)題的求解必須是按順序進(jìn)行的；

相鄰的子問(wèn)題之間有關(guān)聯(lián)關(guān)系供汛；

最后一個(gè)子問(wèn)題的解就是初始問(wèn)題的解枪汪。

使用動(dòng)態(tài)規(guī)劃解決問(wèn)題時(shí)，如上圖表格第二行怔昨。

第一步雀久，先要分析最優(yōu)解的性質(zhì)；

第二步趁舀，遞歸的定義最優(yōu)解赖捌；

第三步，記錄不同階段的最優(yōu)值矮烹；

第四步越庇，根據(jù)階段最優(yōu)解選擇全局最優(yōu)解

貪心算法

第三個(gè)貪心算法奋隶，因?yàn)樗紤]的是局部的最優(yōu)解，所以貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解悦荒。貪心算法的關(guān)鍵是貪心策略的選擇唯欣。貪心策略必須具備無(wú)后效性，就是說(shuō)某個(gè)狀態(tài)以后的過(guò)程不會(huì)影響以前的狀態(tài)搬味，只與當(dāng)前狀態(tài)有關(guān)境氢。

貪心算法使用的場(chǎng)景必須滿足兩點(diǎn)：

局部最優(yōu)解能產(chǎn)生全局最優(yōu)解；

就是剛才說(shuō)的必須具備無(wú)后效性碰纬。

如下圖所示萍聊，使用貪心算法解題的一般步驟為：

第一步，先分解為子問(wèn)題悦析；

第二步寿桨、按貪心策略計(jì)算每個(gè)子問(wèn)題的局部最優(yōu)解；

第三步强戴，合并局部最優(yōu)解亭螟。

回溯算法

回溯算法實(shí)際上是一種深度優(yōu)先的搜索算法，按選優(yōu)的條件向前搜索骑歹，當(dāng)探索到某一步時(shí)预烙，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回上一步重新選擇道媚，這種走不通就退回再走的方法就是回溯法扁掸。

回溯法適用于能夠深度優(yōu)先搜索，并且需要獲取解空間的所有解的場(chǎng)合最域，例如迷宮問(wèn)題等谴分。

如上圖所示，回溯法一般的解題步驟為：

第一步先針對(duì)所給問(wèn)題镀脂，確定問(wèn)題的解空間牺蹄；

第二步、確定結(jié)點(diǎn)的擴(kuò)展搜索規(guī)則狗热；

第三步钞馁，以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索匿刮。

分支界定法

最后是分支界定法，與回溯法的求解目標(biāo)不同探颈∈焱瑁回溯法的求解目標(biāo)是找出滿足約束條件的所有解，而分支界定法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解伪节。

分支界定法適用于廣度優(yōu)先搜索光羞，并且獲取解空間的任意解就可以的場(chǎng)合绩鸣，例如求解整數(shù)規(guī)劃問(wèn)題。

如上圖所示纱兑，分支界定法一般的解題步驟：

第一步先確定解的特征呀闻；

第二步在確定子節(jié)點(diǎn)搜索策略，例如是先入先出潜慎，還是先入后出捡多；

第三步通過(guò)廣度優(yōu)先遍歷尋找解。