好,接下來我們繼續探討那個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的證明。