大家好，上一講我們是講了informed search
是如何利用search的方式來做problem solving，那所謂上一講的
informed search就是沒有利用problem本身的特性，也就是說我們在
有各種可能的action的時候我們並不去估計說可能action
這個action比另外一個action好，那這一講我們要講的就是所謂informed search就是相對來說就是如果我們
有這樣的預估的資訊，我們會猜測說這個動作可能比另外其他幾個動作看起來
比較promising，那如果有，當然這個promising意思並不guarant- ee，並不能保證，如果我們
百分之百知道，那就不叫估計了，我們只是估計說這個可能比較好，但是它也可能是錯的- ，在這種
如果用這種資訊下，我們能不能把search做得更有效率一點，那這是這一講的重點，那- 我們這一講的內容呢
也相對應到我們課本AIMA的三點五和三點六節，好那首先我們會先提一個 架構，我們叫best
first search，那best first search呢，意思就是說我每次都挑
目前看起來最好的那一個action走，那也就是說我可能 一個節點，這個state，我有若干個action，那我每次都走目前看起來最好的，-
只是這邊 目前，何謂目前看起來最好的呢，我們就是用一種方法去計算
那我們會講兩個algorithm，一個greedy search ，一個是A star search，那greedy
search 呢，百分之百就是純粹靠著，我們所謂某個action，哪個action最好就是
百分之百直接靠著我們目前的估計值，就是看我覺得這個 動作比較好，我就直接做，那A
star search就是除了這個估計值之外，我們還 再加上了到目前為止我們花了的所有的cost，test
cost的花費，把這些加進去的話 就產生了A star search，那其實A
star search也是我們這一講的重點，我們上禮拜也有提過，就是 我們來討論一個search
algorithm是用幾個面向來談，包含是 optimality，[iii]，然後還有complexity，那我如果
那optimality，大家知道如果我們已經在討論它的optimality，那意思- 就是我們已經知道它是complete的，有
够一定會給你，那我們接下來再來討論它的optimality，這個當然是一個很好，在- search演算法是一個很好的特性 那A
star它的optimality其實是一個很需要探討的部分，因為它在某一些狀況下，- 它其實保證了optimality
那至於是什麼狀況下，就是我們等一下會講的部分，那接下來第二個部分是，我們叫me- mory
bounded search，因為 A star雖然在所謂那個蠻好的特性，就是某個情況下保證最佳解，但是一般而言，它需要
的記憶體量是非常的大，大致上是exponential這樣的事情，在你記憶體足夠大的- 時候我可以保證這件事，那我們今天
大部分電腦上，可能你在實際上面對一個比較大的問題，你沒辦法有這麼多的
記憶體，那所以我們會提，就是在有限的資源下，我們如何 進行類似A
star的做法，那我們大概也會講兩三種做法，那最後呢，第三個部分，我們會講
我們那時候靠的就是我們看哪一個action比較promising 我們靠的是一個所謂，叫heuristic，翻譯成啟發函式
這樣的東西來判斷，那這個東西在，這個heuristic我們剛剛有提過，就是在A star
的某些condition下它能保證A star永遠給你最佳解，但是要產生具有這樣特性的
heuristic，要怎麼產生呢，這就是我們第三個部分要講的，對同一個search algorithm，你給它不同的heuristic
它也會影響你整個search的performance，那我們會談論如何產生這樣一個- 比較，可能比較好一點的heuristic
那我們所謂best first search，就是一種informed search，那informed
search又稱為 我們又可以把它稱為是heuristic search，那概念上呢，就是我們用一個評估函式，也就是稱為evaluation
function 然後對每個node呢，我們去猜測，預測它的
我們對它，就是我想要做這個action，那一般來說，我們在這個整講來說，都會把這個- heuristic
因為h嘛，就寫成h(n)，n就是哪一個state，或者是node 好，那基本上對h(n)，估計是什麼東西呢，就是估計從n開始
能到的最近的，或者我們也可以稱為說最好的，我們的最近是用cost來算，也就是所以
也就是從n開始能到的最好的那個目標所還要再花的cost
好如果你講距離也行，好，那我們用h來表示，那我們介紹 兩個special
case，一個是greedy search，就是我用，就是我們基本上都是用f 所有的best first
search，所用的都是你對目前，就是目前 的現在節點，你有很多action做，那對於這幾個能到的這個
n，我都去算它的，比如說這是n1，n2，點點點，我們都可以去算它的f(n)
比如說f(n1)，這是f(n2)，然後我們對這個譬如說
這五個，五個節點我都去算它的f值，然後根據目前最
好，在我們的case來說，因為cost，我們說我們就是要最小的那個f值的那個節點來- 進行，比如說如果像f2算出來是
f(n2)算出來是五個裡面最小的，那我們就是take這一個來，優先來搜尋，這就是所- 謂的best
first search 那best first search有幾個特例，一個是greedy
search，就是我f值只用h(n) 就是我完全純粹用h(n)來決定說我現在要優先走
優先拿哪一個，那另外一個case是A star，就是我們今天的重頭戲，那基本上是
g(n)加h(n)，那各位同學如果有，還記得我們上禮拜的內容，其中我們講 過叫uniform
cost search，其實uniform cost search也是一個best first search的特例，它所用的是
uniform cost，就是它
優先是走目前cost最小的，就是path cost最小的，所以它的例子就是f
f(n)呢我們用的就是g(n) 好g就是那個path
cost，OK，所以你還可以 看得出來就是我們其實A star search是一個結合了greedy
所以A star search差不多就，概念上其實就是一個greedy
search配上uniform cost
的結果嘛，因為greedy的話用的就是，只用h 然後uniform
cost 用的就是只用g(n)，那A star就是把這兩個相加 好其實概念上是這個樣子，那應該大家還記得其實uniform
cost的話它是保證optimality的，大致上，就是說 只要你的cost是正的，不要有零，只要是大致上正的話
uniform cost一定會保證給你最佳解，那greedy search呢
它我們等下就會提到，應該蠻明顯的，因為我們只用估計值來走，所以我們不能保證它的op- timality，但是它
如果當你h很對的時候，它可以走的非常非常快，所以基本上我們A star就是希望能結合兩個優點，一方面
能保證最佳節，一方面又能某些情況比uniform cost來的快速一點，好那我們
這個例子我們之後會一直使用，所以我們在後面做一些[iii]的時候如果你們有些困- 惑就可以
配合這張投影片來看，那我們這邊給一個heuristic，這個heuristic- 我們稱為
直線距離，就是SLD，就是這個straight line distance
好我們稱為SLD，好我們現在目標還是一樣，這是台北捷運的一個 為了本課而特化的一個圖，那我們現在目標是從古亭
然後走到台北車站，那上面的這些都是它的distance，那我們現在給一個
heuristic，就是我到底應該要走哪一個，走到哪一個站呢，這個heurist- ic就是
每一個節點，這個h就是我們h(n)，就是SLD
好，那這個就是每一個，到任何一個站，然後到
台北車站的直線距離，就是我不管地圖上面，你就直接，譬如說如果是行天宮這個的話
那我們可以看，行天宮是50嘛，意思就是說這個直線距離是50
OK，那這樣當然是種估計值嘛，因為實際上我沒辦法直線這樣走，實際上
我如果從行天宮走到台北車站我可能得這個樣走，那實際上是跨了10加10加10加35
好，那沒有50，但是anyway，超過50了，但是anyway，這個直線距離是一- 種估計值
好，那我們如果，這邊就列了這個h(n)給大家參考 那如果我們只用greedy search的話，我們看一下
就是greedy search就是我用的f(n)，再提醒一下，就是直接用h(n) 那我直接用這個heuristic來做
的話，好我們看一下，古亭一開始，如果配合 這一頁來看，古亭一開始的話到台北車站的是58嘛，這邊
就是58，所以我們就是從古亭開始，一開始是58，然後之後古亭有兩個路可以走，一-
個是中間 中正紀念堂，一個是東門，那如果你去查剛剛的hSLD的話
一個是48，一個是33，好那現在如果是我們用greedy search的話，那做的就是優先找那個最小的數，我們就會走這一條
優先這樣做，然後從中正紀念堂，33然後，你再展開，四個節點，就是包含古亭，小南- 門，台北
醫院以及東門，那展開地這些你去查，一樣查hSLD，會發現台北醫院最短，距離
台北市的直線距離最短，只有15。
所以我們會優先take這個，search台大醫院這一個。
我們台北醫院以後再展開，你就會展到台北車站以及中山國中，中山國中就是回去了，
那可是，anyway，你就會優先看這個0，到台北車站當然是0嘛，
那我們就優先走這一個，那最後我們就走到，所以這一個Greedy Search給的solution就是這個樣。
好就是跟大家講就是古亭到中山國中然後到台大醫院然後到台北車站。
好。
那接下來我們看一下， 我們一樣去從四個面向來討論，來探討Greedy
Search的特性，那一個就是它是不是 complete。
實際上Greedy Search它不能保證completeness。
好，原因是什麼呢？譬如說，我們舉個例子，如果我們從， 我看一下，我們回到這個地圖來看，
好假設我們從中山國中這裡 如果我們要到臺北站，這是起點，我們要到台北車站。
那 中山國中展開的話，你有兩個可能嘛，一個是南京東路，那我們看一下南京東路的
直線距離是77，好那另外一個是松山機場，它的直線距離是75。
ok？所以我們如果到Greedy Search的話，我們會優先take這一支 展開。
那75以後，你會發現怎麼辦呢？你就只有一條路嘛，對不對？就是又回來 中山國中。
然後到中山國中後你如果再展開，又會再度展開 松山機場以及南京東路。
所以你又會再跑去松山機場，然後又回來。
你會在這邊做無窮 回旋。
中山國中到松山機場然後這樣一直一直回來。
所以原則上在completeness的話，那它是 false的，就是no。
但是當我們講這個 狀態是可以斃掉的，就是我們剛剛講是因為是tree
search嘛，tree search我們不切合 state是不是重複，那我們今天如果用的是grafe
search，就是我們會發現，誒你 就是從中山國中到松山機場以後，
就你第一次可能還是會先take松山機場，但松山機場回來中山國中這是沒辦法的，唯一 一條路。
可中山國中在第二次展的時候，你可能如果做grafe search的話，你不會再展開松山機場。
因為這時候松山機場是已經explored，就是你已經被探索過的，那只剩下南京東路可- 以走，這時候就會 強制被走到這邊來。
也就是說如果你用grafe search去check那repeated state的話，那是可以 保證complete。
那這個，當然這個保證也只是你是 finite state，如果你不是finite spaces，你的state如果超過
有限，就是如果它是無窮space的話，你還是會有可能會出現剛剛這種類似無窮回旋- 的東西。
反正就是 一條路，它不一定是無窮回旋，一條路它是無窮長的一直走下去，然後你一直走不到你的g-
oal。
所以generally，就是反正completeness是no，但是你如果用g- rafe search雖然可以斃掉，但
一定要我們之前也有提過，grafe search的話你記憶體要記憶的東西實在太多，在大部分說 不是一件很可行的辦法。
那既然completeness是no，那相對當然很明顯地，第二個就是 optimality當然一定是不可能做到的嘛。
那但是我們看一下，就算你真的走得到goal，像我們其實剛剛的例子，
我們剛剛的例子最後走的是這樣哦，古亭然後 中正紀念堂、 台大醫院到台北車站。
好，如果我們看一下原來地圖這邊。
你從古亭、 中正紀念堂、 台大醫院、
台北車站，這是我們用Greedy Search找的solution，那你如果加一加的話是
總cost是15嘛加30加40實際上是85。
好這個cost的話是85。
但是這一條的話其實，你可以看到這一條， 如果從這邊走的話其實是cost是20加15加10
加35，這樣加起來的話是 80。
ok？這樣cost是80。
也就說其實我們剛剛用Greedy Search的給你的solution很明顯它不是optimal。
那當然因為completeness的關係，當然你不complet不保證optima- lity，但是我這邊要提的就是
就算你找到goal，就算你能找到goal，它也不能保證是最好的，因為greedy嘛。
那time complexity像space complexity其實基本上都是原則上阿，我們講
what's case的話都是exponential，就是brange
factor的n次方，但是 這個對象比較難估計，因為depend上你的h。
這邊完全depend上你的h，其實我們像剛才講optimality說，能不能保證
optimality，這個其實也是depend上你的h阿，其實h我當然可以給你一個- 保證optimality的h，譬如說，
如果我們剛剛，譬如我今天改一下h， 譬如我知道最佳解是這一個，那我給你的h譬如說這邊的
[iii]這邊都是1、 1、 1，那其它全都是 無窮大、 無窮大、 無窮大。
就我把這個table改一下，會經過這邊東門、 忠孝新生
這是1，然後東門，善導寺1，然後其它的全都是 無窮大、 無窮大、 無窮大、 無窮大、 無窮大。
如果今天給你這個h，那當然這是一種滿明顯的契機，就是我已經知道 optimal是什麼，那那條配置上的給你就很低的，我給1也可以阿給0也可以，然後其-
它都給你 無窮大，那這樣的話當然會optimal，但是可以看得出，
而且那樣的heuristic非常快，就你瞬間直接沖到這邊，可是這個就是完全hi- ghly depend上你的heuristic。
但是原則上是exponential，但是我們要提的就是效能完全depend上你的h- euristic，而且這個影響會非常的大。
［音樂］
于天立副教授 (Associate Professor)
