本課程有兩大課程目標： 1. 使同學了解如何以搜尋達成人工智慧 2. 使同學能將相關技術應用到自己的問題上
2-4 Uninformed Search (i) - Breadth-First Search, Uniform-Cost Search
Loading...
Do curso por National Taiwan University
人工智慧：搜尋方法與邏輯推論 (Artificial Intelligence - Search & Logic)
139 ratings
Na lição
Uninformed search
Conheça os instrutores
于天立(Tian-Li,Yu)副教授（Associate Professor）
電機工程學系(Electrical Engineering)
所謂 Uninformed Search,
Blind Search 基本上我們就是不使用，我們就只用 你在 Problem Definition
所拿得到的資訊，大家回想一下就是 包含的 Initial State, 包含的 Goal State,
包含的 Transition Model，就是我從 State S 執行A 能到達
S Prime，還有我的 Goal Test我們知道，然後我們有所謂的 Path Cost 還有 Step Cost 的這些資訊。
如果僅僅只用這些資訊的話那我們就稱為Uninformed Search
那如果額外再用一些智慧去猜測怎麼樣比較好的話 那是我們下一講所要講的。
這部分我們基本上要講5種不同的 Search By the Rational Search
不包含在這一個，By the Rational Search 其實是一種，它並不是 從 Frontier
拿 Node 的次序，而是你 Search 的 方式根本就是從兩端開始，是可能不太一樣的。
那我們會講 Breadth-first 以及 Uniform-cost，還有 Depth-first，還有 Depth-limited，還有Iterative
deepening 首先Breadth-First Search 我們又簡稱為 BFS，那這是其實如果
各位有修過資料結構或演算法可能大家都，或者離散甚至離散可能都聽過，但是 我們可能第一次碰到我們還是很簡單地講一下。
基本上就是你展開 從 Frontier 展開的時候就是展最淺的哪一個，譬如說我們從
A 開始，那概念上你就是 A 展開，那 A 這邊究竟 Explode，那這邊是
看你 Tree，如果是Tree 的話就丟進去，那你這邊的話是就放在 Frontier
裡面 那如果不是 Tree 的話你就是直接把它丟掉，A 就不需要。
那我們用 queue 來真的來寫，因為它其實 Exactly 就是相當於你 Frontier 用 queue，FIFO queue 來做。
那我們用 queue 的話習慣上就是畫一個 類似管子的東西。
那我們假設從最右端，這邊進去然後從這邊拿出來。
那我們看一下 一開始我們就是 Initial 嘛，我們就把
A 丟進去 那之後，你就把 A 拿出來，A
就丟掉 然後之後 A 展開是 B 和 C，你就把 B 和 C
丟進來 然後之後再來你就拿一個，然後就是把 B 丟掉。
B 展開的同時你就是 展開就是 D 和 E。
這是我們到這邊 之後你就發現，從這個，First in first out 的話你就是展的就是 C。
C 展開然後就是 F 以及 G。
ok那接下來就後面就一樣，你展開 D 沒有 children
的就沒事，你就沒有東西要放進 frontier，那 E 展開，F 展開，G 展開 到這樣結束。
這是 BFS 的部分。
那我們來探討一下它 就是我們剛剛講的四個面向，那首先第一個是它是不是
Completeness 這邊蠻明顯的就是我如果整個 Search
base 裡面存在 goal，那我這樣一直一層一層地這樣展下去
我遲早應該展得到我的 goal 吧，所以原則上是 Yes 原則上是
Yes，這邊呢有一些特例，第一個是譬如說 如果你的 goal
雖然存在，但是它在無窮深的地方 那這樣你要無窮久的時間才能找到它。
不過這些特例一般在大部分的 case 是不太存在的
你如果有這樣的問題其實基本上你要把那個，如果你的 goal
真的在無窮深的地方那其實你要執行的 就是你的 solution，你的 sequence of action基本上也就是無窮長嘛。
那基本上在概念上成立 但是在實做上是不太可能的，我們電腦沒辦法去 maintain 這樣一個無窮長的
sequence 那另外一個就是你的 Breadth factor，就是b 是不是 finite，是不是有限。
如果你的 b 就是我一個東西 可以這邊基本上有無窮多個 action 的話，那也不能保證你展得到嘛
譬如我的 goal 在這裡好了，可是這邊因為有無窮多個，你根本在有限的時間展不過來。
但是這個例子也是 就在大部分的問題來說 b 我們一般來說是 finite。
就是說這邊雖然有個條件 說 b 是 finite 的，但是大部分的問題是成立的
Optimal 呢，這個應該蠻明顯的，直覺就是 不太可能了。
我們這邊寫說 Yes only of，就是只有在某些特定狀況成立，那其實意思就是 No
了 就你如果只要我一個 simple answer 說 Yes or No，那我會回答 No。
在某個條件下 是成立的。
大家應該可以看得出來，BFS 因為它每次都展得 frontier 都是
最淺的那一個嘛，所以它永遠給你的 goal 就是 展開裡面最淺的。
就是如果我一個樹狀 結構從 Initial State
展展展，這邊假設有個 g1 好了，那這邊有個g2，這個比較深。
那 BFS 永遠都會這樣，它是一路這樣從這邊展過來，這邊展過來 直到展到 g1 為止停，它一定說給你 g1 比較淺的那一個。
那你不能保證 g1 的 cost 比較小嘛，因為可能其實你到 g2 的 cost
是比較小的 所以它既然 BFS 保證給你是最淺的那一個
所以它會是最 Optimal 的情況下就是你的 Path
的 Cost 是一個跟你的深度，跟你在展開的層數呈一個正相關的關係
如果說正比的話那就一定是，因為它給你最淺的那同時就是給你 Path Cost
最小的，不過這個條件當然是蠻嚴苛的，就是我們說 in general 它是 not optimal。
那 Time complexity 基本上就是你展一層嘛
展一層要1，展第二層要b，展第三層要b平方 這樣一直展下去，我們講 worst case 嘛。
那你展到 d 大家還記得 d 是我們那個目標，你至少展到 d 那一層你就找到目標嘛，就
worst case 你展到 d 那全部所要畫的其實就是 b 的 d 次方。
當然這個其實是 基本上是 exponential，那這個可能很難避免，我們接下來看到很多
在不同的演算法search algorithm，在其他面向可能有一些或多或少的改進或不同，但是在
Time complexity 這一部分 一般而言不太容易改變，一般而言。
當然你可以 lose 其他一些特性 那當然如果你的 goal test 是在 expansion，
就像我們講的那個版本，就是你在 展開以後你才開始，你才做
check 它是不是 goal，那這樣的話其實是 b+1，你要再多深一層，不過這個差別很小
那 Space complexity 呢，基本上，如果我們回到這一層看。
我們這邊白色的 node 白色的點就是在 frontier 嘛，那你看我展到這一層的時候基本上我
frontier 就全部的四格 那可以想象，如果我展到第三層的時候，展到第四層的時候它其實就是全部
就是2的，這是2的2次方嘛，那下一層就是2的3次方，下一層是 2的4次方等等，那我
frontier worst case 就是這邊全部都要記起來 所以我的 frontier 基本上就是
exponential 的形式 就是我的 space 要記得是 exponential 的事情。
好我們現在講，其實剛講過就是 Time complexity
一般的時候 還好對不對，你程式寫完就算你一個比較大的問題你丟到電腦裡面
你說真的很慢，那我乾脆給它跑個兩個禮拜，乾脆跑個一個月 也許我可以等。
但是你有個問題是，你如果真的問題 state 夠多的話，我們
很容易一秒鐘，以現在電腦的速度，因為一秒鐘你大概可以 check 10的9次方這樣的
node，那你全部都要把它記起來的話 你就算一個 node 只占了若干
byte，不多的情況下你還是很容易展到 100 M 以上，那因為
Mega 是10的6次方嘛，你說這邊的話 10的8次方個 byte
嘛，對不對，那你可以看就算我一個 node，一個節點，我展一個節點
我只要記10個 byte對不對，那因為我現在電腦就實在是很快10的9次方的
order 已經基本上，所以我很容易 很容易一秒鐘就展我可能要100個MB這樣。
那如果用 這個速度來算的話，基本上你讓電腦放著它跑一天所需要的記憶體就要 8個 tera，8000個GB。
這樣的記憶體我想現在大部分的電腦是無法 handle 的
也就是說你即使可以把電腦擺在那兒它跑一天沒關係，但是 實際上你記憶體馬上就爆掉。
所以這個 Space complexity 其實是對我們來說是比較困擾的事情 接下來我們介紹 Uniform-Cost Search。
Uniform-Cost Search 基本上 為什麼我們會接在 BFS 後面介紹呢，因為它，其實 BFS 是 Uniform-Cost 的一個特例。
Uniform-Cost 在展開是怎麼展呢，就是你在 frontier 裡面你展開
最少的 path cost，最少的 path cost。
那今天如果 如果我的 Search tree 裡面每一個 cost，每一個任何一個 action
的 cost 都是1的話，都是一樣的，我們講說1，那基本上它就是
BFS 就你展最小的 path cost 就相當於你優先展開最少層的
所以你可以把 BFS 視為 Uniform-Cost 的一個特例
當然你的 step cost 不 equal 的話，那它們當然就不太一樣
那這個最常用的實做方法就是 Priority queue
我們用 Priority queue 實做，那我們把 path cost 我們後面就俗稱把它稱為 g(n)。
g(n) 就是你從 initial state 到 n 這個 state 所要花的 path cost，那我們把這個當做
priority，然後每次都找那個最小的那一個 優先展開。
我們這邊舉個例子，就是一樣的地圖，那我們
換個起點和終點我們來舉例，那我們起點是在民權西路這裡，這是我們起點。
那我們終點是在善導寺 所以在這個地圖上大家很明顯我有兩條 path
來走，那我們 看一下 Uniform-Cost 要怎麼走。
一開始的 path cost 是0 這樣ok，那接下來你展開，就是你把這兩個展開。
這兩個就 你把民權西路這個節點展開，然後你會產生中山國小以及雙連這兩個站
把它丟掉，丟進frontier，所以民權西路這個丟掉，那剩下的frontier裡面- ，這邊是15，
min path cost這邊也是15，這兩個在我的frontier裡面，那接下來我選最小的那個
來展開，那最小的，其實沒什麼差別啦，兩個15都一樣，那假設我展這個15好了，那我就
展中山國小這一個，那我就把它這個node丟掉，那接下來把它更新成
行天宮，那我所花path cost是15加35，所以這邊是50。
OK，好那我現在frontier裡面有兩個，就是15和 50，我清除一下，這邊是15，這邊是50，
這邊已經看完，看完，好這是我在我的frontier裡面，那接下來
我就展的，uniform cost展的就是15這個node，那再次把它丟掉，那接下來展開這個是30，
OK，好，那30跟50同樣去比較，30丟掉， 那接下來會到這邊，台北車站，這邊是50，好，50和50其實
一樣啦，那你展哪一個都可以，那當然你從台北車站再展一次你就覺得到goal了，但是e- ither
way我們沒什麼關係，但是 我們可以用這個展展看，你說50，假設我選了這一個，那你在展開的時候這邊會變成85
到這邊，可是，記得一下，我們那時候講的 tree
search algorithm，其實就，你應該先把它
先你就不管它是不是goal，你就先把它丟進frontier，不然的話，在這個例子你- 不保證optimality，因為你如果
真的用這邊來走的話，其實它不是optimal嘛，因為可以看到我從行天宮50開始，走- 三個10過來才是80，
好，也就是說這時候為什麼，就是回應到我們剛剛tree's algorithm為什麼我們的goal
test要在 frontier拿出來的時候才check，就是不應該在現在check，就是你從台北-
車站50展開 的時候你發現到善導寺是85，可是這個時候你不管它是不是goal，你就把它丟進fro-
ntier，所以我現在frontier裡面是有 50和85這兩個節點，那之後我選擇小的展開，所以應該是50，展開
好，到松江南京這邊是60，
好，之後對這個60再度展開，那到忠孝新生是70，
好，70和85還是一樣，你最小的其實是70，所以70展開，你又到善導寺，如果是你是 tree
search algorithm的話，在這邊你不會發現你是同一個善導寺，也就是在這邊的話你展開-
會有一個 善導寺85，然後有另外一個善導寺
80，你其實會有這兩個東西，然後這時候你會，這時候你都在frontier裡面，- 然後同樣
你選最小的cost，所以你接下來會選擇這一個站，就善導寺80來展開，然後這時候你做- goal
test發現 那已經到goal了，所以你回傳最小的是80，那如果你今天用的是graph-sear-
ch的時候， 你會發現，在你要弄一個善導寺80的時候，你會發現這個善導寺其實已經展開過了，已經存在
你的frontier裡面，這時候你要做一個，我們成為relaxation的動作，就-
是你如果要比較 80跟85哪一個小，因為我們現在要找
小的，你會發現原來的我記錄的是80，85這個比較 大，我現在新的80比較小，所以這時候我們，你要
把善導寺85丟掉，然後換成善導寺80， 這邊你如果用priority queue來實做的話，priority
queue有一個function稱為decreasekey，你要呼叫這個funct- ion，把這個已經存在的
node的85decrease到80，如果你在這樣做的時候你會發現我們剛剛有提到的 我們在記錄一個節點的時候要記錄它的parent，其實這個很重要，因為
同樣是善導寺，善導寺80的來源是忠孝新生，那你善導寺85的來源是台北
車站，那我們最後的solution其實是我們要的是善導寺80，然後從，前一個是忠孝-
新生，前一個是 就是我們要的是這一條，這一條，那如果你記得你的parent
是誰的話，我們拿到善導寺80以後，你就可以回去把這個sequence 完全全部拿出來。
好，那我們來看一下uniform cost search的，它的，就四個面向來探討
一下，首先看它的completeness，那completeness原則上就是 跟我們在，我們講BFS大家知道有一個特例，那BFS如果yes的話，
那它基本上也是yes，那它有個條件啦，它的條件 其實很容易達到，就是說你的cost，step
cost不可以是 負的，而且也不可以剛剛好是零，
為什麼呢？因為你有可能有個例子，就是initial在這邊，然後接下來你有 個state，有個，這邊是一個無窮迴旋，無窮長的一個sequence，可是你這個每-
一個cost假設都是零， 可是這一條路其實沒有goal，就是你沒有，達不到目標。
舉例來說，你可能是個來回的嘛，因為你用tree search，所以你可能是 古亭到中正紀念堂，中正紀念堂到古亭，再到中正紀念堂再到古亭，再到中正紀念堂再到古亭-
，那如果你這個cost是零 的話，那這就，又形成一條無窮長的sequence，而且cost都是零，那你的真正的-
goal在這邊， 那假設這個是100，那這樣就會形成一個問題，就是你這邊零會一直加下去，一直加下去都-
是零，對不對，所以你每次在frontier裡面 優先展開的都是這一條無窮迴旋上的這個node，所以你永遠不會
走到goal這一邊，在這個情況下的話呢，uniform cost不會
給你，不會給你任何的目標，不會回傳任何的目標，即使你的目標存在，但是這個條件很容- 易達成，
就是只要你的step cost不是真的零，就是有很小的， 譬如說很小的ε，只要稍微大於零，那就沒有問題，因為這些ε
你還是累加，你總有一天會加到大於100， 好只要你加到大於100的時候，這個就會優先展開。
OK，這就是如果你的step cost都是正的，不為零，那uniform cost保證一定，只要你的目標存在，它就一定給你 目標。
那另外呢，optimality的問題那其實是yes的，就是原因是為什麼呢？因為 它展開的次序都是path
cost，用最低的開始展，所以也就是說它 第一次遇到goal的時候，它一定是，如果你是若干個goal，那它一定是給你
最小的那一個，就是你有，你可以達到，就目標裡面path cost最小的那一個goal，那如果你是同一個goal，但是不同的path
可以走過來，那其實這個argument並沒有什麼差別，因為如果以tree search來講，它雖然是
同一個goal，但它基本上是視為不同的state，那如果你用graph search的話，我們剛剛有講過，就是你
反正你遇到一個新的比較小的方法能找到這個goal，你還是會呼叫decreaseke- y這個function，然後選擇比較短的方法走
到，所以原則上它是optimality它是yes，那這個相較於BFS這是很大的改進- ，這個基本上是yes。
time complexity跟space complexity基本上是比較難分析一點點，可是如果我們given我們剛剛講的就是
我們step cost如果最小是ε的話，那其實還是OK，就是你如果最佳值，就是你的goal的-
目標是C star， 那我從，那我最多要走多深呢？因為你每一條至少是ε嘛，
至少是ε，那你全部加起來是C star，那也就是說你這條路最長最長深度是這麼多，
深度是這麼多，就是C star，就是C star除上ε， 那因為加1取個flow就是你可能正，你可能多1嘛，
好，那你的worst case，那就是b的這個次方，也就是b的
C star除上ε這個，這樣，這麼多， 這是你的worst
case，那space complexity其實是一樣的，因為你就是，這其實就是一個
BFS是它的一種特例，所以基本上，你時間那麼久，基本上你要記憶的worst case也是那麼多，
這個是沒有變，這個是沒有變化的，我們這邊做一些假設，C star或
ε這些其實都不太重要，重點就是大家要知道的，你的space和 time
complexity其實原則上都還是exponential，這一點跟BFS本身並沒- 有太大的變化。
[聲音]
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
