本課程分為人工智慧（上）、人工智慧（下）兩部份，第一部分除了人工智慧概論外，著重在目標搜尋、meta heuristic、電腦對弈、演繹學習（包含證言邏輯、一階邏輯及 planning ）等技術。這些技術主要發展時機為人工智慧的第一波及第二波熱潮，也就是 1950 年代至 1990 年代附近的主流發展，即使到現在也在各個領域廣為應用。 課程教學目標： 使同學對人工智慧有基礎概念 同學能夠理解如何運用目標搜尋技術及演繹學習方式達成人工智慧 同學能將相關技術應用到自己的問題上
3-3 Best-First Search (iii) - Optimality of A*
Loading...
From the course by National Taiwan University
人工智慧：搜尋方法與邏輯推論 (Artificial Intelligence - Search & Logic)
140 ratings
From the lesson
Informed search
Meet the Instructors
于天立(Tian-Li,Yu)副教授（Associate Professor）
電機工程學系(Electrical Engineering)
好，接下來我們繼續探討那個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的證明。
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
