《Artificial Intelligence》Lecture 6 Search 3: Search with costs & Heuristic search

對應課本3.5.1，3.6， 3.6.1

1. heuristic search和人類的思維有什麼共同點？

Herbert A Simon（赫伯特西蒙）發現人是用simple heuristics來解決問題的。

A.M. Turing Award Winner，赫伯特西蒙是人工智慧的先驅，也是管理學，決策理論的大師。

One of the most important outcomes of this approach to computer science was Simon』s development—and strong advocacy—of heuristic programming. Drawing on his studies of human psychology and of organizational decision-making, Simon noted that people intend to be rational but that they rarely, if ever, have access to all the information or all the time they would need to make the optimally rational choice. Thus, Simon concluded, we do not, because we cannot, solve problems by using exhaustive, precise algorithms. Rather, we must use simpler heuristics and accept satisfactory rather than optimal results in order to make decisions or solve problems. To use a common analogy: a safecracker with unlimited time can try every combination and thus can be assured of opening the safe eventually. The safecracker who operates in the real world, however, has limited time and so begins by trying combinations based on the owner』s family birthdays, anniversaries, and the like. This heuristic does not guarantee success, but it will work often, and when it works, gives results much more quickly.

2. 一個輔助學習AI的網站

AIspace，就是這個老師為了教AI這門課建立的。

其中一個展示各種graph search algorithm的工具看起來很不錯啊。可以一步一步的跟蹤。

3. 之前講的都是cost equally的情況，現在來看different cost的情況

解決這樣的search問題用的lowest cost first search（也就是Dijkstra's shortest path algorithm），在《人工智慧：一種現代方法》書中，這種方法叫做uniform-cost search.

也可以看做是BFS的generalization。

在lowest cost first search下，frontier是一個priority queue：

選BFS

4. lowest cost first search的性質

可以說大多數情況下是complete和optimal的。

時間複雜度和BFS差不多，只不過多了 ，它是插入priority queue的時間複雜度

5. lower cost first search也是uninformed search嘛？

是的。

6. Heuristic Search

heuristic是computer science里一個很foundamental的詞，人們經常misuse它， 認為heursitc意味著likely to fail。

我們經常把algorithmic和heuristic這兩個詞進行對比，algorithmic是good stuff，保證complete，保證optimal，而heuristic則常常fail。但這樣的理解是錯誤的！

heuristic這個詞的本意是to discover，heuristic並不是algorithmic的反面，而也是一種algorithmic，和algorithm一樣，Heuristic Search也有certain guarantee，也有自己的性質。

從下面的定義可以看出，h(n)一定比optimal要小。

顯然best first search不是optimal的：

也並不complete：

7. 總結

lowest cost search是選過去的cost最小的進行expand，best first search是選未來的cost最小的進行expand。

推薦閱讀：