人工智能程序員入門(mén)應該學(xué)哪些算法？

人工智能這么火，算法是核心要義，應該從哪些開(kāi)始學(xué)習入門(mén)呢？

初期

一.基本算法:

枚舉.

遞歸和分治法.

遞推.

二.圖算法:

圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷.

最短路徑算法

最小生成樹(shù)算法

二分圖的最大匹配 (匈牙利算法)

最大流的增廣路算法(KM算法).

三.數據結構.

串

排序(快排、歸并排(與逆序數有關(guān))、堆排)

簡(jiǎn)單并查集的應用.

哈希表和二分查找等高效查找法(數的Hash,串的Hash)

哈夫曼樹(shù)

堆

trie樹(shù)(靜態(tài)建樹(shù)、動(dòng)態(tài)建樹(shù))

四.簡(jiǎn)單搜索

深度優(yōu)先搜索

廣度優(yōu)先搜索

簡(jiǎn)單搜索技巧和剪枝

五.動(dòng)態(tài)規劃

背包問(wèn)題.

簡(jiǎn)單DP (最長(cháng)公共子序列) (最優(yōu)二分檢索樹(shù)問(wèn)題)

六.數學(xué)

組合數學(xué): 1.加法原理和乘法原理. 2.排列組合. 3.遞推關(guān)系.

數論. 1.素數與整除問(wèn)題 2.進(jìn)制位. 3.同余模運算.

計算方法. 1.二分法求解單調函數相關(guān)知識

七.計算幾何學(xué).

幾何公式.

叉積和點(diǎn)積的運用(如線(xiàn)段相交的判定,點(diǎn)到線(xiàn)段的距離等).

多邊型的簡(jiǎn)單算法(求面積)和相關(guān)判定(點(diǎn)在多邊型內,多邊型是否相交)

凸包.

中級:

一.基本算法:

C++的標準模版庫的應用.

二.圖算法:

差分約束系統的建立和求解.

最小費用最大流

雙連通分量

強連通分支及其縮點(diǎn).

圖的割邊和割點(diǎn)

最小割模型、網(wǎng)絡(luò )流規約

三.數據結構.

線(xiàn)段樹(shù).

靜態(tài)二叉檢索樹(shù).

樹(shù)狀樹(shù)組

RMQ.

并查集的高級應用.

KMP算法.

四.搜索

最優(yōu)化剪枝和可行性剪枝

搜索的技巧和優(yōu)化

記憶化搜索

五.動(dòng)態(tài)規劃

較為復雜的動(dòng)態(tài)規劃(如動(dòng)態(tài)規劃解特別的旅行商TSP問(wèn)題等)

記錄狀態(tài)的動(dòng)態(tài)規劃.

樹(shù)型動(dòng)態(tài)規劃(

六.數學(xué)

組合數學(xué): 1.容斥原理. 2.抽屜原理. 3.置換群與Polya定理4.遞推關(guān)系和母函數.

數學(xué). 1.高斯消元法2.概率問(wèn)題. 3.GCD、擴展的歐幾里德(中國剩余定理)

隨機化算法

七.計算幾何學(xué).

坐標離散化.

掃描線(xiàn)算法(例如求矩形的面積和周長(cháng)并,常和線(xiàn)段樹(shù)或堆一起使用)

幾何工具的綜合應用.

高級:

一.基本算法要求:

代碼快速寫(xiě)成,精簡(jiǎn)但不失風(fēng)格

保證正確性和高效性.

二.圖算法:

度限制最小生成樹(shù)和第K最短路.

最短路,最小生成樹(shù),二分圖,最大流問(wèn)題的相關(guān)理論(主要是模型建立和求解)

小生成樹(shù).

無(wú)向圖、有向圖的最小環(huán)

三.數據結構.

trie圖的建立和應用.

LCA和RMQ問(wèn)題(LCA(最近公共祖先問(wèn)題) 有離線(xiàn)算法(并查集+dfs) 和 在線(xiàn)算法

雙端隊列和它的應用(維護一個(gè)單調的隊列,常常在動(dòng)態(tài)規劃中起到優(yōu)化狀態(tài)轉移的目的).

左偏樹(shù)(可合并堆).

四.搜索

廣搜的狀態(tài)優(yōu)化:利用M進(jìn)制數存儲狀態(tài)、轉化為串用hash表判重、按位壓縮存儲狀態(tài)、雙向廣搜、A*算法.

深搜的優(yōu)化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過(guò)大、可以考慮雙向搜索或者是輪換搜索、IDA*算法.

五.動(dòng)態(tài)規劃

需要用數據結構優(yōu)化的動(dòng)態(tài)規劃.

四邊形不等式理論.

較難的狀態(tài)DP

六.數學(xué)

組合數學(xué). 1.MoBius反演2.偏序關(guān)系理論.

博奕論. 1.極大極小過(guò)程2.Nim問(wèn)題.

七.計算幾何學(xué).

半平面求交

可視圖的建立

點(diǎn)集最小圓覆蓋.

最后，記得關(guān)注微信公眾號：鎂客網(wǎng)（im2maker），更多干貨在等你！