人工智慧-問題形式化

一、首先我們來看一個栗子：

我們需要從阿拉德（Arad），到達首都布加勒斯特（Bucharest）期間只能開車從相鄰的城市穿過，不能一次性坐飛機到達。要完成這個任務，如何和人工智慧的搜索扯上關係，如圖：

上圖看出，是從阿拉德（Arad）出發

要到達：首都布加勒斯特（Bucharest）

其中智能體的目標是開車去布加勒斯特。我們將目標考慮成是世界的一個狀態集合，目標被滿足的那些狀態的集合。比如其中的一個狀態集合{Arad、Sibiu、Fagaras、Bucharest}智能體沿著這條路（這個狀態集合）就能夠到達目的地。如下圖紅色箭頭所示：

智能體的任務是找出現在和未來如何行動，以使它達到一個目標狀態。為達到目標，尋找這樣的行動序列的過程被稱為搜索（智能體在搜索上面紅色箭頭的路徑的過程被稱為搜索）。

搜索演算法的輸入是問題，輸出是問題的解，以行動序列的形式返回問題的解。解一旦被找到，它所建議的行動將會付諸實施，這被稱為執行階段。

那麼，我們通過形式化，搜索和執行就完成了對智能體的簡單設計。

問題的形式化是在給定目標下確定需要考慮哪些行動和狀態的過程。現在我們假設智能體將在開車從一個主要城鎮到另一個城鎮的層次上考慮行動。因此每個狀態表示智能體在一個特定的城鎮中，比如說智能體在Pitesti城市，那麼可以說智能體的狀態就可以表達為<Pitesti>。

那麼我們將上面例子的相關知識總結概括一下就是：

我們最終的解就是城市序列，智能按照這個序列執行動作（這裡指的是開車到達下一個狀態）一步一步執行，就能到達最後的目標狀態。

那麼通過這個栗子，引出通用的問題形式化!

二、問題形式化

一個問題可以由四個組成部分來形式化：

1、初始狀態（智能體一開始的初始狀態）

2、動作或後續函數（智能體能夠執行的動作，以及執行該動作後獲得的代價）

4、路徑代價（到達目標狀態到時候，評價一下從初始狀態經過的動作序列獲取的總代價）

其中一個解是從初始狀態到目標狀態的動作系列，簡單來說，智能體的問題都可以描述為：

定義智能體的初始狀態，找出智能體可以走的動作序列，然後進行執行，執行後得到的新狀態，智能體對目前狀態進行目標狀態的測試。

• 如果不是目標狀態，則將從初始狀態達到該新狀態的代價保存起來，繼續重複尋找該新狀態可以執行的動作。
• 如果是目標狀態，則over，返回從初始狀態到達該目標狀態的總代價即可。

下面通過兩個栗子更加深刻的理解問題形式化表示！

三、問題形式化栗子

例題1，假如我們現在有一個吸塵器，對兩個房子進行吸收塵灰，目標是兩個房子都乾淨，那麼這個問題如何形式化為智能體的搜索問題。

換句話說我們應該如何找到這個問題的四個部分，初始狀態、動作或後續函數、目標測試、路徑代價

我們很容易得到四個部分分別如下：

於是我們將一個問題建模成了智能體的搜索問題，關鍵就是正確的找到這個問題的四個部分，在仔細分析後，找到這個問題並不是太困難。

下面我們再來看一個例子：

例題二、8數碼問題

八數碼問題也稱為九宮問題。在3×3的棋盤，擺有八個棋子，每個棋子上標有1至8的某一數字，不同棋子上標的數字不相同。棋盤上還有一個空格，與空格相鄰的棋子可以移到空格中。要求解決的問題是：給出一個初始狀態和一個目標狀態，找出一種從初始轉變成目標狀態的移動棋子步數最少的移動步驟。

目標就是將初始狀態轉移到目標狀態的最小步數。比如初始狀態是下面這個：

目標狀態是下面這個：

我們的目標就是將初始狀態變為目標狀態所需要的最小步數，應該怎麼做？那麼這個問題，我們應該如何形式化呢？

還是關鍵找到那四個基本組成部分：初始狀態、動作或後續函數、目標測試、路徑代價

分析後，結果如下：

四、總結

本次筆記講解了人工智慧智能體的問題的形式化表示，將任何一個智能體的問題都統一形式化為4個部分，這有助於後面知識的講解，比如針對四個部分中的路徑代價來進行不同演算法的優化等等.....

參考： 所有內容來自於學堂在線公開課《人工智慧》 地址：人工智慧（自主模式）-學堂在線-最大的中文慕課（mooc）平台

推薦閱讀：