Explore
For Enterprise
Join for Free
Log In

Rutgers University
Become a skilled supply chain leader in 4 months
Earn the Supply Chain Excellence MasterTrack™ Certificate from a top-ranked business school.
Imperial College London
Register today for Global Master of Public Health webinar
RSVP to Imperial's upcoming webinar to learn more about their GMPH program on Feb 11.

Explore todo o Coursera

Navegar
Os melhores cursos
For Enterprise
Entrar
Inscreva-se gratuitamente

2-4 Uninformed Search (i) - Breadth-First Search, Uniform-Cost Search

Loading...

人工智慧：搜尋方法與邏輯推論 (Artificial Intelligence - Search & Logic)

Universidade Nacional de Taiwan

4.8 (168 classificações) | 16K alunos inscritos

Cadastre-se gratuitamente

本課程分為人工智慧（上）、人工智慧（下）兩部份，第一部分除了人工智慧概論外，著重在目標搜尋、meta heuristic、電腦對弈、演繹學習（包含證言邏輯、一階邏輯及 planning ）等技術。這些技術主要發展時機為人工智慧的第一波及第二波熱潮，也就是 1950 年代至 1990 年代附近的主流發展，即使到現在也在各個領域廣為應用。課程教學目標：使同學對人工智慧有基礎概念同學能夠理解如何運用目標搜尋技術及演繹學習方式達成人工智慧同學能將相關技術應用到自己的問題上

Visualizar o programa do curso

Habilidades que você aprenderá

Artificial Intelligence (AI), Search Algorithm, A.I. Artificial Intelligence, Algorithms

Avaliações

4.8 (168 classificações)

5 stars
135 ratings
4 stars
26 ratings
3 stars
6 ratings
2 stars
1 ratings

Na lição

Uninformed search

2-1 Problem Solving Agents, Problem Formulation (i)14:46

2-2 Problem Formulation (ii) - Abstraction18:26

2-3 Search on Tree and Graph21:16

2-4 Uninformed Search (i) - Breadth-First Search, Uniform-Cost Search18:09

2-5 Uninformed Search (ii) - Depth-First Search, Depth-Limited Search, Iterative-Deepening Search14:03

2-6 Uninformed Search (iii) - Iterative-Deepening Search, Bidirectional Search15:25

Ministrado por

于天立
副教授 (Associate Professor)

Experimente o curso Gratuito

Transcrição

所謂 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.

Coursera

Sobre
Liderança
Carreiras
Lista de cursos
Certificados
Certificados MasterTrack™
Notas
For Enterprise
For Government
For Campus

Comunidade

Aprendizes
Parceiros
Desenvolvedores
Testadores beta
Tradutores
Blog
Tech Blog

Mais

Termos
Privacidade
Ajuda
Acessibilidade
Imprensa
Contato
Diretório
Afiliados

Aprenda em qualquer lugar

Siga-nos

© 2020 Coursera Inc. Todos os direitos reservados.