【課程來源】感謝B站Up主leonding1018的分享，老師的課程內(nèi)容非常精彩。
本文是觀看網(wǎng)絡(luò)視頻課程后的筆記，如涉及版權(quán)問題，請(qǐng)及時(shí)留言或私信與我聯(lián)系。

1.旅行商問題（TSP問題）

TSP問題是一個(gè)NP hard問題，在一個(gè)多項(xiàng)式時(shí)間內(nèi)不能找到一個(gè)最優(yōu)解。

單個(gè)車輛遍歷路徑（TSP問題）可以擴(kuò)展為：多車輛遍歷路徑（VRP），車輛實(shí)時(shí)路徑規(guī)劃，訂單分配給不同車輛（調(diào)度優(yōu)化），零部件排產(chǎn)等。

2.啟發(fā)式搜索算法

2.1.全局搜索算法

2.1.1.貪婪最佳優(yōu)先搜索

2.1.2.A*（A Star）搜索

舉了即時(shí)戰(zhàn)略游戲中目標(biāo)對(duì)象選擇路徑找過障礙物到達(dá)目的地的例子，目標(biāo)是讓英雄從地圖左上角A點(diǎn)運(yùn)動(dòng)到右下角B點(diǎn)。如圖所示，黑色部分為障礙物，“黃橙紅”顏色標(biāo)記了每一個(gè)坐標(biāo)被遍歷訪問的此處。上方為枚舉法對(duì)地圖各坐標(biāo)的訪問頻次，下方為A Star搜索方法對(duì)地圖各坐標(biāo)的訪問頻次。可以看出A Star方法只訪問了較少的坐標(biāo)，提高了搜索效率。

(1)從當(dāng)前點(diǎn)(x=1,y=2)開始遍歷相鄰點(diǎn)（算出g=當(dāng)前點(diǎn)到新點(diǎn)單步距離，h=新點(diǎn)到終點(diǎn)不考慮障礙物的剩余距離，f=g+h）；

(2)選取f最小的點(diǎn)作為新的當(dāng)前點(diǎn)(x=2,y=3)；

(3)重復(fù)步驟1；
(x,y)從(2,3)到(3,3)

(x,y)從(3,3)到(4,3)

(4)注意所有已探索未步入的點(diǎn)，都是候選點(diǎn)，這是便于選錯(cuò)路的回頭糾正；
(x,y)從(4,3)回頭到(1,3)，再回頭到(2,2)

(5)當(dāng)重新選取了當(dāng)前節(jié)點(diǎn)（即回頭）后，相關(guān)已探索節(jié)點(diǎn)的g/h/f值也應(yīng)更新。
注意當(dāng)前點(diǎn)改為(2,2)后，點(diǎn)(3,2)、(4,2)的g/h/f值都進(jìn)行了更新。

(6)注意每個(gè)新點(diǎn)都記錄著其對(duì)應(yīng)的父節(jié)點(diǎn)，便于最后一步回溯；
留意之前每一幅圖上的箭頭，當(dāng)前點(diǎn)變化后，箭頭也發(fā)生了變化。

(7)當(dāng)前點(diǎn)移動(dòng)到終點(diǎn)后，從終點(diǎn)開始，根據(jù)父節(jié)點(diǎn)可反推出最優(yōu)路徑。
上圖中綠色標(biāo)記的路徑。

2.1.3.限制存儲(chǔ)的啟發(fā)式搜索

2.1.4.啟發(fā)函數(shù)h(n)的設(shè)計(jì)

2.2.局部搜索和群算法

2.2.1.貪婪局部搜索

2.2.2.模擬退火搜索

2.2.3.禁忌搜索

2.2.4.局部剪枝搜索

2.2.5.遺傳算法（基因算法）

(1)先隨機(jī)生成一定數(shù)量（例如1000條）的解；
(2)然后按一定比例（例如10%）選出其中較好的100個(gè)保留，其余的900條再變異；
(3)在第上一步新生成的1000條中選100個(gè)保留，其余的變異；
(4)重復(fù)步驟3若干次；
(5)選1000條中最好的一個(gè)，作為最優(yōu)解。

2.3.對(duì)抗搜索

2.3.1.極小極大值算法

2.3.2.α-β剪枝搜索

3.混合機(jī)器學(xué)習(xí)算法的優(yōu)化求解

應(yīng)留意圖片中一些城建概念的關(guān)系，包括：數(shù)據(jù)庫、指示發(fā)現(xiàn)、數(shù)據(jù)挖掘、統(tǒng)計(jì)、圖形識(shí)別、神經(jīng)計(jì)算、人工智能、機(jī)器學(xué)習(xí)、深度學(xué)習(xí)。比如，機(jī)器學(xué)習(xí)的范圍大于深度學(xué)習(xí)，人工智能的范圍大于機(jī)器學(xué)習(xí)。

《終極算法》（推薦書）中將算法分為5大類：
(1)符號(hào)主義：通過規(guī)則和決策樹進(jìn)行推理；
(2)貝葉斯方法：通過統(tǒng)計(jì)學(xué)中的貝葉斯（先驗(yàn)后驗(yàn)）概率；
(3)聯(lián)接主義：模擬人腦，創(chuàng)建節(jié)點(diǎn)和連接網(wǎng)絡(luò)進(jìn)行非線性關(guān)聯(lián)，代表性有神經(jīng)網(wǎng)絡(luò)；
(4)進(jìn)化方法：模擬生物進(jìn)化，迭代創(chuàng)建新的節(jié)點(diǎn)，代表性有遺傳算法；
(5)類比學(xué)派：利用樣本特征相似性，代表性有KNN聚類分析（商品推薦）和支持向量機(jī)。

實(shí)例：在滴滴打車應(yīng)用中。早期使用A Star方法進(jìn)行路徑規(guī)劃和時(shí)間估計(jì)；在后期取得了更多大數(shù)據(jù)后，利用這些數(shù)據(jù)采用RNN（循環(huán)神經(jīng)網(wǎng)絡(luò)）算法進(jìn)行路徑規(guī)劃和時(shí)間估計(jì)。能夠比初期的A-Star方法考慮到了更多的復(fù)雜因素（例如車輛類型、擁堵、修路、時(shí)間、司機(jī)駕齡等），所以預(yù)估時(shí)間更準(zhǔn)確。

4.Hadoop生態(tài)

總結(jié)

以上是生活随笔為你收集整理的大数据与智能算法（一-基础技术）-SMU在线学习笔记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。