接下來我們介紹兩種search algorithm，那search algorithm基本上就是分成 tree search algorithm與graph search algorithm，好， tree search跟graph search 其實我在一開始有講過，它們最主要的差距其實就是 在於你能不能去比較repeated 的 states， 大部分的search problem本身 是大部分其實我們是以graph來講，但是只要如果你不去check是不是 state之間有沒有重復的話，那其實最後展開的就會變成一個search tree。 那我們先看一下search tree algorithm基本上 會從initial state開始，然後基本上用一個， 在課本裡面大概使用的是所謂的frontier，在實作上， 我們是用Q來記錄，那只要是frontier在empty的情況下， 就是沒有點的情況下，你就會失敗。initial 裡的話， frontier就是前線，你就把initial state擺進去， 然後之後呢，就從這個只要frontier根據你的 不同的search algorithm有不同的優先區， 把frontier裡面的某一個state拿出來， 那可能是最淺的，也可能是cost最小的等等，depend on不同的search algorithm， 然後把這個state展開，好，就是expand， 我們稱為expanding state， 那你把它展開以後呢，就是把這些state再丟回frontier裡面，然後， 當然之前展開的那個state把它丟掉，你就已經移除， 那之後我們就要不斷repeat這個步驟，直到我們找到goal state為止。 那這邊有一個有趣的事情是要check一下，就是習慣上我們在goal test， 一般來說，我們不會一展開就test，也就是說，如果說我們有一個state， 現在今天我們展到某一個狀態，那它比如說它下面有三個，這裡面其實是已經夠了。 好，那其它還有兩個，那我們把這個state展開的時候， 我們把這三個state加入frontier的時候， 其實這個時候我們通常不做goal test。 我們是把goal test延遲delay到甚麼時候呢？ 到你從frontier在，這幾個放在frontier裡面，那直到你在frontier， 等到把它拿出來的時候，這時我們才去看它是不是goal test， 也就是在這邊，我們其實是remove、choose一個node， 從frontier裡面拿出來，然後這時候才去做goal test， 那如果它是goal 我們就說這個search找到這個goal， 那為甚麼要這樣做呢？為甚麼我們不把 在還沒加入frontier，就是我們把一個state一展開，那如果它含有goal，我們就停止， 後面那一層就不用做 那主要原因其實是， 如果你一展開，它含有goal，你就說search結束的話， 那其實你不能保證某些情況下我不能保證給你最佳的解。 好，這是一個狀況，等一下我們會有例子來說明這一些。 那我們先看一下 tree search algorithm是，因為它不check repeated state，那如果你原來的problem本身， 就是repeated state這種情況下發生非常多的時候其實可以很糟糕。 這邊舉一個例子，就是這是一個problem，這是problem本身， 這problem本身其實很單純，其實你看起來似乎是一個linear的狀態， 就是我有A，B，C，D state， 那其實，只是這每一個state都有兩種方法走到， 就是從A你有兩種方法走到B，從B有兩種方法走到C，從C有兩種方法走到D， 如果，這個問題本身看起來並不算很難，假設你可以想像， 假設這邊有n個problem、n個state好了。 因為這其實雖然看似有兩種路徑，但是其實，說穿了就是單線，就是單線並行這種感覺， 可是如果你用tree search algorithm， 然後不check你的state有沒有重復的情況，那你從A開始你會有左右兩條路， 然後展到的走到的其實都是B，那這個B雖然一樣， 可是在tree seach我們去不check， 所以你會認為它們在algorith上思維是不一樣的，那從B再開始你有兩條路線走到C， B開始這邊有兩條，那你這樣一直展開下去n個state， 在我右邊這種tree search algorithm裡面展開的結果就會有2的n次方。 就會變exponent，如果我左邊有100個，這邊100個state的話，其實是linear， 你只要一路往下走100個時間你就走完了，到右邊的圖裡面 2的100次方這個order是目前大部分電腦都沒辦法在有限的時間內handle完， 在合理的時間內handle完。 所以這個情況下我們就是跟各位講說tree search algorithm雖然是比較常用，但是它是有， 可以把一個本來是linear的問題變成一個exponetial的問題，那怎麼解決呢？ 最簡單的方式就是你去，還是要去check repeated state，但是你可能做不到 把所有的state都真的去check， 原則上我們為甚麼不能真的check，可能因為如果我任兩個state都要check， 能check它們不一樣的話，原則上我就必須要記完所有的state， 那這件事其實在很多problem是不可能的，就是如果在我們接下來要講的這個 one holiday in Taipei這個例子其實是還好， 因為我們的站名沒那麼多，可能幾百個站名，那其實記得起來，那如果我們 舉例舉到比如說像西洋象棋，或是中國象棋這種情況下， 像西洋棋的話，合理到state一般來說， 合理的state會被認為是，被估計是10的40次方，這樣的state， 那你如果要任兩個state它們有沒有重復都要能比較的話， 那一般的電腦記憶體是無法記錄下來的， 我們既然不能記所有state，那其實還是有辦法可以解決， 你可以用hash table的方式，學過資料結構的同學大概知道， 就是我不能真的check兩個state一不一樣，但是我可以做一件事情， 我可以把這些state換成hash值，然後去比較它們的hash值， 如果它們的hash值是一樣的話，我就當作它們是一樣， 那這樣比其實當然不是很準確，因為有些state它們可能 不一樣，但是卻對應到一樣的hash值，這樣可能會有一些誤差， 而且你可能記憶體有限，譬如說我這樣子記， 我hash table的size是一百萬，一百萬是一般電腦可以handle的情況， 那就是我記一百萬個不同的、最近使用的state， 那超過這一百萬以上，它們state就算相同，我也當作很不同，可是， 即使用這麼簡單的技巧，其實就能大量避免，至少可以避免像剛剛這個問題， 因為在這個問題裡面，我只要有hash table， 我很容易發現B是同一個，這並不難。就是，我如果hash table， 假設說，可以最近使用過的一百萬個state，那我從A展下來， B就是第一個嘛，你馬上可以check它們是怎樣的， 所以我就不用把它展成兩個B，那B往下走的時候就是最近使用的C可以去記， 直到你從A往下走一百萬個state以後，你才開始把A這個state忘記。 那這樣，我的意思是說，即使在有限的記憶體用hashtable，這個不是很準確的 check state一不一樣的狀態，你仍然能避免大部分的， 只用tree search algorithm造成的一些困擾， 那這個也是目前大部分 被大量使用的技巧。 那tree search algorithm當然就是我們真的去check說， state一不一樣，所以我們基本上用另外一個，叫做explored set， 就是你這個state已經被探索過來的話， 你就把它丟進這個explored set。那這個事情我剛剛就提了， 就是你在大部分現實的問題，這個algorithm雖然是概念性的，可以用， 但是你只要state夠多的話，這個可以想象，我一直丟嘛， 探索過的你就丟進這個Q，這個explored set裡面， 那這個explored set會長太快，通常大部分 電腦記憶體是無法handle的。 但是anyway，如果可以的話，那這時所謂的tree search algorithm， 那這跟之前的前兩頁的 那個tree search algorithm差別只有這三行，只有這個2，9，和11這一行。 其實你看到的很簡單，就是我initial一個explored set，那只要我一旦 探索過這個node的呢，我就把這個node丟進這個explored set，那接下來， 我要再展開的時候，如果你在frontier那我不展開， 那如果在exploredset呢我也不展開。 這樣的話就會如果重復的，已經被探索過，我就不會再一次去探索它， 這樣可以大量節省時間，但是前提就是你的記憶體要夠大。 好，那這邊是一個，我們用剛剛的就是 one holiday in Taipei這個例子去展的一個partial的一個search tree， 那不管用tree search algorithm還是graph search algorithm， 你在展開的過程形成的一個資料結構過程都是一個tree的狀態， 所以說我們都稱為一個search tree。 那我們從古亭開始，古亭站開始， 那大家可以配合一下，就是手邊有投影片的話，如果從古亭開始你能走的兩個， 就是兩個state，就是中正紀念堂以及東門， 所以你從這邊開始把這個丟進frontier， 然後之後你把，因為只有一個嘛，所以你沒有什麼次序問題， 你把古亭從frontier拿出來，然後繼續展開，那展開就是中正紀念堂，以及東門。 那如果你今天用的是graph search的話， 你就會把古亭丟進explored set， 然後現在接下來， 中正紀念堂以及東門這兩個，會在frontier set裡面， 那接下來再從frontier裡面再挑一個 出來展，那挑哪一個呢？這depend on不同的searchalgorithm，或不同的做法。 那我們先假設如果今天我挑了中正紀念堂好了，就今天如果我是在frontier裡面， 我這兩個都在frontier，我挑中正紀念堂出來，那一樣， 如果你在graph search的話，你再度把它丟進explored， 好，這個已經展過，所以這邊我們來用深灰色來表示。那接下來， 這個東門還在frontier裡面，那你展開中正紀念堂， 展開了這個也丟進frontier裡面。 好，那這裡面再次展開牽涉到一件事情，牽涉到從中正紀念堂展開， 如果你今天是用graph search algorithm的話， 你會發現其實中正紀念堂， 其實你再展開的時候還有古亭嘛，你從古亭來的，你還是可以再回到古亭去， 但是你如果用graph search的話，你會發現它已經就是古亭。 從中央展開的時候其實有古亭這一個。 可是根據我們search, graph search的algorithm. 那古亭已經在exploded set 所以你不會再次把它加入frontier了。 好大家可以還有印象的話。也就是這一行。 就你從中正紀念堂展開的時候有古亭. 那它因為已經在exploded set 所以你不會再一次把它加入frontier. 好， 那如果你今天用的是tree search algorithm的話，那很抱歉， 你不會知道這件事情。你還是會連到古亭. 那這個古亭一樣放在frontier裡面。 那同理你今天用的是tree search的話，那古亭下次再展開還是會到中正紀念堂。 好你會這邊會有個古亭-中正紀念堂......的一個類似無窮迴圈的狀態下去。 好，那我們這邊看一下tree search 和graph search 其實有一個很重要的特性，稱為frontier separation. 好就是這邊講的，frontier separation, 那這重點是甚麼呢？ 它講述了它有一個property. 不然是graph search 或 tree search 都有類似。 我們都用到一個frontier 這個cue。有些 node 擺在frontier 裡面。 那這frontier 它separation的特性就是說 它會把已經展過的set 和沒有展過的set 會分隔兩邊。 好，就是沒有展過的和展過的它們不可能連在一起。就中間一定隔一個frontier. 譬如說，如果我們用下面這一個例子。 然後這是exploded,從這邊開始展。 那你exploded一展開的時候旁邊就白的就是frontier. 好這在frontier，這在frontier。 Frontier, frontier. 那接下來淺灰色，就是你還沒展，unexploded. 那你如果今天frontier 選了一個來展，比如選了這一個來展的話那接下來你的， 會造成就是你的exploded在這邊，然後你的frontier呢在上面這一層。 就是這六個。然後接下來外面的就是，全部外面就是unexploded. 那這個特性是存在的，separation特性是存在的。 那這裡其實課本有個提示啦。其實因為我們在講 演算法，這是一個演算法。我們在講演算法時候兩個重點嘛。 一個是它的效能，一個是它的正確性。接下來我們會談論它們的效能。 但是對正確性來說因為這是人工智能課程我們並沒有過多的著墨。 但是如果你想要去證明說 graph search 或 tree search algorithm 它是正確的。也就是說如果你存在 goal 這個目標它的確會走到 goal 這個目標的話那你所需要的 因為這在一個 loop裡面嘛， 那你所需要的是我們稱為，在演算法呢我們稱為一個loop invariant. 我們就稱為在一個迴圈裡面永遠不會變的。那你在這個證明過程中，在graph search 裡面的 loop invariant 其實就是我們講的這個separation property. 就是不管在回圈的第幾層，你隨時隨地frontier都分隔了 exploded跟 unexploded 的 set。 所以當你結束的時候，就當你沒有 unexploded, 就你 frontier 全部是空的時候， 這是終止條件嘛。所以你就會發現所有的 state 人家都看過。 都會進入exploded，因為你不可能沒有frontier的情況下結果你卻還有unexploded. 因為不可能嘛，因為你要分隔 Frontier 已經不在了 那，exploded又必須 跟 unexploded必須要分隔。 那唯一的可能就是已經沒有unexploded。這樣子這個條件才能成立。 好了，那這就是我們講的 loop invariant. 你如果能證明這件事情的話 那你就基本上就證明了graph search是正確的。 好那接下來我們提一個事情。在這部分就是我們有時候概念上我們是用state來講，概念上。 但我們正在implement的時候，在實做這個演算法的時候， 我們常常，有些時候我們習慣用node. 就我們一個樹狀圖，我們一個tree展開 它裡面有這個結點那個結點，我們用一個node來講。那node跟 state呢，基本上它 大致上是one to one, 就一對一的對應，但它不是百分之百。 那一般而言，我們node我們通常會記得比state還多一點的資訊。 那，原因是因為實做後這樣比較簡單。 我們看一下 如果有些同學要去做小精靈的作業的話， 那其實這邊對這個會特別有感覺。 一般來說我們一個node 當然它對應的就是某個 state 嘛。 對應就是我們problem formulation 的某一個state. 但是你為了要便於日後的計算。譬如說 你最後走到 goal state 的時候你可能想要， 因為我們最後不是說 goal state 就結束。你必須，我們必須要知道solution. Solution 是一個 sequence of action 對不對？ 那你可能要想要知道你是怎麼來的。 好就是我最後走走走，有一個node 它最後走到 goal. 它就是 goal state. 那我們要看說，哎，你怎麼來？ 就是說通常情況下是我們是trace回去。 就走路這樣一路走回去。然後把那action 收集起來。就說，好， 你的 sequence of action就是這一套。那，所以我們就很喜歡把parent 記起來。 這樣到時候回去找你是怎麼走來的會比較簡單。 那另外一個通式我們可能也需要一個資訊就是 你目前為止到這個state你花了多少cost 所以我們通常也會記一個path cost 免得每一次你都真的要從頭開始加。 也就我們會加，到目前為止你有譬如說20個cost. 那你如果下一個action要花6，那你下一個就是26。你就這樣一直疊加下去， 這樣子比較簡單。那我們習慣上會記一些它能展開的結點，以及到目前為止多深了。 記這個depth的原因是因為有一些演算法它會要求你在深入多少的時候回傳一些值。 好，就比如我們限制說你目前只能搜尋到第四層。這樣的話這個depth的資訊就很有用。 好，那我們要update一個node的話其實就， 這邊就很單純啦。其實你problem基本上就是 我們呼叫result 這個 function 嘛。 我們剛才 problem formation 就是有呼叫 result 這個 function. 那傳入的就是一個state 那在這個 state 執行一個 action到目前這個state嘛。 對這個node, 目前 node 所代表的state 就是我的parent 的 state 執行的那一個 action, 然後我到的這個 state，這就是我現在在的s’這個 state. 好，那你的parent就是parent 然後你的action就是我剛才舉的那個action 那你的path cost其實很簡單。 如果就是說我們疊加的情況下你這個node的cost就是你 parent 的path cost 因為parent反正有計量的資料結構 那接下來加上我的 step cost. 好，這 step cost, 我這邊還有這個result當然就是在problem formulation的時候有給定的。 所以這個我們是well known 的事情。 接下來我們要開始介紹各種不同的search algorithm. 那其實如果我們就提過嘛，如果你的記憶體夠我們才會用graph search. 那 in general我們會假設如果你不刻意假設具體很大量 goal 的話。 那我們講的是tree search algorithm. 那tree search algorithm如果它去熟悉那演算法的話。 其實不同的search algorithm 所對應到的只是改變你queue的實作。我們講過frontier好像都是 用queue來做。那只是你把一堆結點丟進這個queue裡面。 那接下來我們從frontier choose選一個出來要選擇哪一個。 那這就決定了不同的演算法。 比如說你可能用first in first out 的 queue 好first in first out就大部分基本上我們還是， 主要結構上我們還是習慣稱它為queue啦。那 last in first out的話， 有另外一個別名就stack,就堆一疊。 好那另外一個我們也可以採用priority queue. Priority queue實做大部分是用 heap 這個資料結構來實做。那有興趣的同學去看一下資料結構。 那priority queue的重點就是說 我每一個結點都有不同的，我可以指定某個值為它的priority, 然後之後每次從這個queue拿出來的一定都是當時priority最高的那個結點。 好那我們剛提到，就是一個search 的strategy 不同只是差別在你從 frontier 把 node 拿出來的次序不同而已。 那我們接下來要探討各種不同的search演算法。 那基本上我們用四個面向來討論。好一個部分就是， 就是演算法當中常用的time complexity 還有 space complexity，這我們都會提。再來還有兩個比較特別的是completeness. 那completeness定義就是說，如果有goal的話，就是你在searchspace裡面 如果有目標的話。你能不能always找到目標， 那如果可以的話你就是complete. 那接下來是optimality, optimality 是說 如果這個 有兩種講法。一種兩個都要。一個就說如果你有若干個goal, multiple goal 的話，你能不能永遠都找到給你最少cost的那個goal. 那第二個是， 就算你只有單一個goal, 或是我剛剛講的 multiple goal裡面的其中某一個。但是你能不能用最少的、最短的路徑走到那一個goal. 因為可能你有，如果有不同的走法的話。那如果可以的話 那我們就稱為你是optimal或是我們就稱為不是。那當然，很明顯的如果一個演算法 它如果不保證completeness的話那他當然不可能保證optimality. 好，那 time complexity 跟space complexity的時候 這邊我們要再提醒一下就是在人工智慧裡面 我們講了很多search algorithm,其實很多時候它的bottleneck 其實並不出在時間複雜度。更多時候其實像我們剛剛講的tree和graph, 但graph的performance一般是比較好,但是你能做到的前提是你的記憶體要夠。 在很多search algorithm的時候，space complexity 可能在一般演算法並不特別強調，可是在人工智慧我們可能比較在意的是 implementation這一塊。就你真的要把它做出來的情況下。 space complexity其實是我們很concern的一個要點。 好那我們接下來再討論的四個面向的時候， 我們做一些假設、做一些參數這樣我們比較好討論。一個是b, 這個b是指我們最大的branch factor 好在這search過程你的 problem formulation 最大的branch factor，那假設，假設我有這邊有3，這邊有2。 然後這邊有4個等等。那假設這4是整個search過程中最大的。 那我們b就等於4，就是最大的那個branch factor 好，那你的，接下來我們講這個d。d是指你有最好的， 就是假設你從這邊開始不知到多遠，好到一個這是optimal 的goal， optimal的目標。那這個的深度我們就稱為d 所以你到底要經過多少個node 好這邊就經過幾個結點那我們就稱為d，那m的話是你這個search space裡面 最深最深的深度。 好那這個depends on 你的problem,那可以是無窮大。 可以是無窮大。最簡單如果你在tree search algorithm， 像我們剛剛的，台北的地圖其實如果你用 tree search algorithm你可以一直重復嘛。 你可以從古亭到中正紀念堂、中正紀念堂到古亭...... 那你整個search space 一直， 基本上, m 就是無窮大。
