好，接下來我們繼續探討那個A*的 保證optimality的條件，那我們其實，剛提過就是重點就是這兩個，就是一個就是 如果你是，你的problem是tree的情況下你只要admissible的條件就夠， 那如果是graph的話， 我們就除admissible以外再加上一個consistent的條件。 好，那其實這個，有時候啦，有時候我們在 呃，口語上，這個嚴格講起來就是， 我剛才講就是tree就是admissible那graph要 admissible而且consistent。那，只是有時候口語上我們會習慣 就是你如果講，你的heuristic是admissible的時候， 我們有時候也不再去問tree或graph，因為其實一般來說我們談過就 如果大部分的search如果你不花那麼記憶體去記得話， 大致上都是一種tree search的結構， 所以我們習慣上當heuristic說是admissible的時候其實就， 呃，我們通常就是指它A*就是會給optimal的solution。 那我們現在接下來就來證明這件事情， 那這兩個證明其實說實話式子算是很簡單，但是，就請各位 要記得我們到底在證甚麼。好我們首先先證明第一個。 好，第一個部分就是只要你是admissible的時候，那A*在tree上面就是保證 會給optimal的solution，那所謂在tree上面的意思就是說， 我們的重點其實只是在於你沒有 多條path可以到同一個goal啦，對我們來說，就是， 就算如果是tree search，就算你真的有這種情況下我們也視為 那個goal是不同的goal嘛，就是因為我們不知道它是同一個state。 好，這就是符合我們tree search的條件。好，那這個證明其實，可以看這個圖哦， 其實就是我從starting開始，然後假設，這怎麼設定就是，我的 G‘是一個比較 就是，它也是一個goal，但它的f比較大，好，就是f，就是我們叫sub optimal， sub optimal,就是不是最佳解， 那這一個g是我們真正的最佳解，好，也就是說這個條件已經給了，就是， 那我實際上的G就是，一定是比G’的cost來的小 G是真正的cost，就是我從starting point走到G‘一定比較大，那 走到G比較小，大家先記得這個條件，那接下來我們要做的證明呢， 就是，呃，要證明說，如果從 starting point經過node n，我會走到g， 也就是說n是某一個從starting到g上面的一條路徑上的某一個節點。 那我們要證的就是，真正要證的就是f的G’會大於f的n， 好我們只要證明著一點的話其實就證明，呃，A*會給optimal solution， 為甚麼呢？因為如果今天G和n都在frontier裡面的話， 那frontier，根據A*的特性嘛，它一定會優先挑n出來， 會優先展開n，它不會先展到G‘， 因為如果今天我展到G’的話， 那其實就會，A*就會給G‘，因為你優先展開G’，
然後發現G‘也是一個goal，然後它就會 return這個goal出來，那這樣就不對了。 那，如果今天，n永遠都先展n，也就是說只要n是starting point到g目標上面的任何一個節點，那n都會優先。 因為我n沒有限定哦，n沒有限定到哪一個節點，就是任何一個都可以 那，我證明的就是，這邊的所有的n，所有的node都會比g* 被優先展開。那這樣的話很明顯，我們的G一定會，優先被展開， 所以就會給optimal solution。好，這就是我們要證明的東西。 好，那其實證明的式子都在這一邊哦，那只是， 呃，可能為了比較清楚一點我們重寫一次，那我們可以這樣 大家可以follow，好，那我們先講第一件事情， 可能，我們剛才講admissible的時候，注意一下哦，admissible 好，大家記得這個條件，admissible條件就是對所有的 對所有的state，那，我的，它的估計值都小於等於 真正的要花的值。就從n走到goal的值都一定小於等於真正的， 那h*是真正的那一個。好，given這個條件其實，有個很有趣的， 哦，對不起，這邊我可能要稍微再提一個條件哦，就是我可能沒有特別講，但原則上， 就是我們h是，我們這邊談的都不談論負的，就是也就是說這個東西 我沒有特別寫，但你，如果有同學有興趣的話就加一下。 這個條件我們是給的啦，一般來說我們在討論，我們現在討論的東西都沒有，不討論負的。 好，那這些都是正的的情況下， 好那，保證了一件事，當我說一個h是admissible的時候其實保證了一件事， 就是h of任何一個goal, 大家可以算一下，因為，我們一樣嘛，它必須小於...... 啊當然，大於等於零，那它小於等於真正的花費， 好，那如果g是一個goal對不對，那它到最近的goal， 其實就是它自己，主要的實質花費，這個我們知道它等於零， 你已經在goal的，那你還要再到最近的goal，就是你自己，要花的花費當然是零。 所以，這件事就保證了一件 guarantee一件事，就是h對任何一個goal，它等於0. ok？這個是，當我說h是admissible的時候保證了一件事， 我剛把剛剛那個圖再畫一下哦，這邊到n 這邊到G，好，那這邊我故意畫長一點，讓大家記得這個G’是比較不好 的一個goal，當然它也是一個目標，但是它的cost比較高，也就是說， 這個比較大，G‘ 是大於 G of G，好，那根據這個， 我們導出來只要它是goal你的h是零，我們同理也知道這件事情。 這兩個是我們一開始先給定的東西，這是我們手邊有這些工具了那麼接下來我們就可以證明， 開始我們的證明。我們要證明的其實就是這個樣子，我們先把f of G’ 記住我們的目標，我們真的要證明的目標就是這件事情，大於f（n） 這是我們想要證明的事情，好，就是我的，我的G， 我的，這樣，n每一個節點都會優先被展開然後g不會被展開， 這是我們要證明的目標，那接下來我們就從 這個開始。好，那根據A*的定義，我們就把它寫開，那基本上就是G加上h，對不對？ 好，那就，任何節點吧! 那這個定義就是G+h，那我們根據， 因為你跟我說，h是admissible，所以我們知道這一項 為0，所以它就等於g的 G’， 好，那接下來我們根據定義，你的定義就是G‘是比較不好的goal， 那G是比較好的goal，所以我們知道它嚴格大於g of G， 好，這是給的條件就在這邊， 好，給的條件，好，那，接下來再把這個寫開， 這個東西，其實，就是從starting point， 哦，這是start. starting point 到G這個目標所有花的那個cost，那， 它當然剛剛好等於我到目前為止，到n所花的 已經花的cost，加上我接下來從n到G 那一段所要花的cost，那，那一段所要花的cost我們如果 有個oracle給你的話就是h*， 對不對，這兩個剛剛好相等，就是我的從 starting point一直到G所有這邊total cost， 就等於這一段cost加上這一段cost， 好，這就是這個等式所寫，那當然這個h*我們是不知道， 只是你想象反正有這個函式，哦，它是最佳值，那 既然是admissible，我們知道這一項，對不對，我們知道這個條件， 你說h是admissible，所以這個東西，當然 大於等於g(n)加上h(n)，好，這個條件就是因為 我任何一個h都是低估，我永遠不會，可以一樣啦， 不用百分之百，就是應該是，正確講法就是 不會高估，不會高估h*，那寫到這邊，答案已經出來了，這個東西 g(n)加h(n)其實就是f(n)， 好，那已經我們證明完畢了，就是，從這邊開始，我們最後是嚴格的大於f(n) f of n，ok？那，這就是這整個的證明， 大家就是記得這幾件事情哦。好，我們剛剛講完了就是 在A*上，如果是在tree search的話只要admissible就夠，但是如果是 graph search的話我們要加一個條件就是consistent， 那graph search跟tree search在這邊的主要差別就是你同一個節點，你有沒有辦法 用，如果在graph上的話你可能有別的path可以過來嘛！ 到同一個節點，所以我們要加一個，呃，consistency的條件， 等一下我們會看到， 所以consistency意識就是三角不等式，而且要保證的事情就是你的 f在整個search的過程中會non-decreasing哦， 在整個search的過程，那如果是tree的話其實你就算是原來 的問題是graph的形狀，但是如果你用不同的path可以到同一個goal， 在tree search的時候它會把它視為不同的goal，就是會變. Goal 1 然後這邊會變 Goal 2. 無法去瞭解這兩個是同一個goal, 所以基本上我們剛剛的admissible的條件就夠了。 好，那，我們這邊，這邊有個lemma. 好這邊如果這個lemma成立。好這邊如果這個lemma成立， 則A*就會給你optimal solution. 這邊我們不用證明的。那我們這邊用， 呃，就是我直接用口條說明為甚麼呢？我們先看一下這個lemma, 就是如果今天這f是consistent，你如果給我這個， 那我們就說A*的，在search的過程中f永遠都是non-decreasing. 好就是它可以一樣，但它絕對不會再變更小。好這個lemma我們等一下就會證明。 這個lemma我們是會證明的。那如果given這個 lemma的情況下， 我們用這邊，接下來用嘴巴說明，好就是為甚麼A*就會給你optimality呢？ 因為如果今天A* 在search的過程你的 f 永遠都不會下降，它只有可能 持平或相等，那第一等我們A* search的方法就是在frontier裡面都挑f最小的出來。 那意思就說，我可以有些cut-off值，譬如說像我們在search 的時候古亭大家都還記得的話。古亭是，算出來f值是58。 好，那也就說在58以內的， 都會先被看完。那其實就只有古亭自己啦。或是我們如果照這張圖上的話就是60以內。 好，就像有search, A*是又有像等高線。就60以內會都先被看完， 才會看f大於等於60以外的。好，因為， 因為我絕對不會說譬如這5，8看完，結果你下一個的時候， 我說不會發生的是，這邊如果變40。這是不可能發生的。 如果我們說這個lemma就要證明就是在f不會忽然掉下來。 好，那如果這成立的話那也就是說我一定是以這個60為原則的話， 以這個為cut-off的話，那這邊58看完了以後，那， 接下來還會看大於等於58以外的。好，那其實如果大家還記得的話， 東門算出來應該f是68。那其它這幾個是80，80。 然後到台北站是80。那像台大醫院算出來是f是85。 那，照整個search過程也就說我會先把80的 全部看完，80以內，小於等於80的全部看完。那，才會再看 大於等於80的。好，那這樣的話因為在這個過程中我已經找到有goal了。 再這80以內我已經找到有個goal了。所以台大醫院這些都不會再被看。 好如果這個，這整個證明是，這整個過程， 就是這個lemma如果是正確的話，那意思就是說A*在 search的過程中它的f反正是慢慢，慢慢變大。 然後在這個contour裡面，就是某一個cut-off裡面所有的node都會被expand過。 然後才會再expand超過這個f. 那只要在這裡面，給你了一個goal. 也就說A*任何時間點只要給你一個goal, 它一定是第一個f最小最小的goal. 也就說如果這以前，因為A*假設給你這個goal嘛。 台北車站它也只給你80。那，之後如果有 再展下去的話那個goal的f值會可能越來越大。 它不可能小於80。好如果那這樣，也就這樣 我們就證明瞭A*是一個，呃，可以給你optimal. 那注意這個lemma的話我們接下來就繼續證明。 好,那接下來我們只要證明這個lemma證明完我們就等於證明瞭A*的optimality. Consistency為甚麼又被稱為三角不等式呢？ 我其實剛有提到。也有人稱為monotocity就是單調性。 那，呃，看左邊這個圖就看得出來。其實如果我從一個節點n, 我走到，這是有一條它直接的successor. 它就是你直接展開某個action它可以直接到的children, n’. 那這邊的cost我們當然知道就是 c(n,a,n'). 好那這邊是預估值。從n你還要走多少，可以走到g. 那這是從n'你還要走，大概還要花多少cost才可以走到，走到g. 那consistent的條件是這個。 就是，呃，這個。好就是h(n)必須小於等於這個step cost的加上 h(n'). 好那這個其實看啊看出來就是兩邊合大於等於三邊。 好就是這個嘛。就是兩邊和。這個加這一個必須要大於等於第三邊。 好所以很多時候我們稱它為三角不等式。它其實就是三角不等式。 好那接下來這個證明我們要證的就是我們說在 A* search的過程，我不管你有多少的path可以到。但是，我們要證的就是f， n'的f一定大於等於n的f。好寫出來就是這個樣，我們要證的是這個東西。 好我們要證明這件事情那基本上我剛的lemma就成立 就是你A*只要從某個點你能往後展。 那所有的那些f都會比我現在的這個大或是等於。好就必須大於等於我現在的parent. 那其實這個東西很好證，我們還是，為了講解我們還是在另一頁來寫。 好，那首先我要證明我的目標，我的目標是這一個。 好那我的條件是consistency. Consistency的意思是說我n如果今天有一條，一個cost, 那cost寫成c， n然後做個action，a，然後我能走到 n’，好它是n’. 好，那這邊估計值到這是我的goal. 這邊估計值是你還要走這麼久，然後這邊要走這麼久。好，那我們給的條件我們有的 這是目標，這是目標。我們要證明的目標。 那我們有的條件是consistency. Consistency就兩邊合大於等於第三邊。也就是說h(n') 加上c, 你從這個地方來 會大於等於第三邊。 好這我們given，given我們要證明這件事情。就證明這個目標。那我們就把它寫開來。 其實證明過程還蠻單純的。好這個f一樣根據A*的定義你就把它寫成g跟h。 好那接下來呢，這一個。 我們先展這一個。 這個東西的cost就是實際上的cost嘛。 那它當然等於你到n為止，已經花的cost. 哦，對不起。 到n為止已經花的cost。再加上我剛剛才畫的這一條step cost. 好這應該可以嘛。就是，這一個， 我把g(n')展開。它其實就到n花的然後再加一個step cost. 然後後面照抄。這是n的，h(n'). ok? 好這就是，這當然直接相等。 那接下來就是要用我們的consistency的條件就是這兩項。 好這兩項加起來我們剛才用上面才寫的，就是這一個。 好，那它當然大於等於，好前面這一項照抄。它大於等於h(n). ok這是條件，就是如果知道h是consistency的話， 那consistent的話那就符合這件事。那這個東西我們當然知道其實寫出來就是f(n)啦。 n的g+h嘛就是n的f。好那到這邊我們證明完畢 如果我有一條就A*在search的過程中n展到了n'. 那n'的f一定大於等於n本身的f。好所以在整個A*的過程中，f只會 只可能越來越大或是不變。但它不可能會縮小。 好所以照這樣展開的過程中A*只要給我個goal, 它一定是我最小的f，最小的goal. 它絕對不會給我別的goal. 好這是，關於A*的optimality的證明。
