人工智能-搜尋

人工智能-搜尋

搜尋是人工智能很重要的一種解決問題的途徑，以下對各種搜尋進行一個分類總結。

首先是搜尋的定義，我們要解決一個問題，要經過很多步驟才能達到最終的目标，搜尋就是要找到這些步驟，即解決問題的方法。

搜尋有其局限性，它必須依賴于現有的知識，它不能自己學習知識，人工智能解決問題的另外一種途徑就是學習，通過學習可以創造或者吸取新的知識。

下面是正文

搜尋（Search）

求解一個問題就是一系列動作，并且搜尋是為達到目标尋找這些動作的過程。

針對不同資料結構：

圖搜尋

樹搜尋

經典搜尋（Classic Search）

無資訊搜尋（uninformed search 即盲目搜尋，沒有除定義之外的資訊）

按照節點的擴充順序區分

寬度優先（breadth-first），用FIFO隊列實作

深度優先（depth-first）：拓展最深的未擴充節點，用LIFO隊列實作

深度受限搜尋（depth-limited）：限制搜尋深度

疊代加深搜尋（iterative deepening）：結合深度優先與寬度優先的優勢

一緻代價搜尋（uninform-cost）：擴充最低代價的未擴充節點

雙向搜尋（bidirectional ）

無資訊搜尋的政策評價

完備性：是否總能找到一個存在的解

時間複雜性

空間複雜性

最優性：是否總能找到最優的解

有資訊搜尋（informed search 亦稱啟發式搜尋，采用問題定義外的資訊，能夠找到比無資訊搜尋更有效的解）

最佳優先搜尋（best-first）：基于評價函數選擇最優拓展節點，大多數該類算法還包括一個啟發式函數

貪心搜尋

A*搜尋

以上的搜尋是經典搜尋，它們的特點是

可觀測

确定性

已知環境

經典搜尋保留搜尋的路徑，其路徑就是問題的解

但在很多問題中，到達目标的路徑不重要，是以就有了超越經典搜尋

有路徑-->無路徑

超越經典搜尋（Beyond Classical Search）

分為局部搜尋與群體智能

局部搜尋（local search）

不關注路徑，搜尋後不保留路徑，其優點為

1.占用記憶體小

2.能在大的或者無限的空間中找到合理的解

爬山法（hill-climbing）：一種疊代算法，開始時随機選取一解，對其不斷優化

随機爬山法（Stochastic hill-climbing）：向上移動的過程中随機選擇，收斂速度慢

首選爬山法（First-choice hill-climbing）：随機生成後繼節點，直到出現更好的

随機重新開機爬山法（Random-restart hill-climbing）：完備性高，接近于1

局部束搜尋（Local Beam Search）

随機束搜尋（Stochastic Beam Search）

禁忌搜尋（Tabu Search）

三種政策

禁止政策（Forbidding strategy）

釋放政策（Freeing strategy）

短期政策（Short-term strategy）

模拟退火（Simulated Annealing）：一種在大搜尋空間逼近全局最優解的元啟發方法

遺傳算法（Genetic Algorithms）：一種模仿自然選擇過程的啟發式算法

群體智能（Swarm Intelligence）

通過大量智能體通過合作實作，它是分布式的、自組織的、在一個環境内分布的。

蟻群優化（Colony Optimization）：受蟻群尋炸食物的行為的啟發，用于發現一個圖上的最佳路徑

粒子群優化（Particle Swarm Optimization）：受魚類，鳥類群體行為的社會行為啟發

單智能體-->多智能體

對抗搜尋（Adversarial Search）

我們在針對其他智能體做規劃時，那些智能體有可能也在做着規劃

以上搜尋針對單智能體，而對抗搜尋針對多智能體

博弈（Game）

零和博弈（Zero sum games）：智能體之間完全對立

非零和博弈（Non-zero sum games）：智能體之間是自主的方式

完全資訊（Perfect information）/不完全資訊（Imperfect information）

确定性（Deterministic）/随機性（Stochastic）

剪枝 （Alpha-Beta Pruning）

博弈樹的大小往往呈指數增加，通過剪枝，可以減小博弈樹，加快搜尋時間

啟發評價函數（Heuristic Evaluation Function）

盡管通過剪枝可以去掉博弈樹的大部分，但是搜尋的深度依然很深，是以用評價函數計算在指定位置該博弈的期望值

随機博弈（Stochastic Game）

一種有一定機率轉換的動态博弈

蒙特卡羅方法（Monte-Carlo Methods）

憑借重複随機采樣來獲得數值結果

蒙特卡羅樹搜尋（MCTS Monte-Carlo Tree Search）

将蒙特卡洛仿真與博弈樹搜尋相結合

限制滿足問題（Constraint Satisfaction Problem）

狀态必須滿足若幹限制的對象

标準搜尋中狀态不可分割，GSP中狀态用因子表示，是一系列變量。

GSP問題通常複雜性很高

範疇

有限/無限

離散/連續

限制

線性/非線性

1元/多元

回溯搜尋（Backtracking Search）

原文位址

https://www.cnblogs.com/zhanghad/p/12483761.html