# W2_人工智慧導論_朱威達.m4a｜長度 02:35:52｜model large-v3 on cuda

[00:00:00] 來來你過來你過來幫我來來來因為我說實在我這字很小我眼睛都看不到來來幫我來看一下這個嗎這個夾好嗎
[00:00:14] 好像說這裡我會選擇來源這裡
[00:00:16] 好試一下試一下
[00:00:18] 長頸兒
[00:00:23] 哦這個嗎
[00:00:23] 應該是應該是螢幕螢幕解決好了看一下誰來幫我一下
[00:00:50] 我試試看
[00:00:51] 好
[00:01:01] 欸
[00:01:10] 直播中好那應該沒問題
[00:01:12] 那看一下那如果切到這個畫面這樣子是不是會有呢
[00:01:24] 是不是
[00:01:27] 剛剛的關鍵是什麼要選輸出的來源是不是
[00:01:37] 奇怪好我以前都沒有做過這件事啊
[00:01:39] 好anyway
[00:01:41] 謝謝同學的幫忙好謝謝
[00:01:43] 好欸好來那回到這裡
[00:01:46] 重點呢就是說要寫清楚你的研究動機你問題的定義
[00:01:50] 你預計要解決的辦法跟文獻
[00:01:53] 那你怎麼寫得出來呢
[00:01:55] 當然就是要想啊
[00:01:56] 然後要找資料啊
[00:01:58] 啊
[00:01:59] 所以這個其實就是不許大家去完成第一個作業
[00:02:02] 你最主要
[00:02:03] 需要花的功夫在這裡
[00:02:05] 你要想要去做一個什麼題目
[00:02:07] 那你就得要先去研究一下
[00:02:10] 目前人家大概都怎麼解的
[00:02:12] 那你預計要怎麼解
[00:02:15] 好
[00:02:16] 那
[00:02:17] 因為你根本就還沒有開始做嘛
[00:02:19] 所以
[00:02:21] 所以說呢
[00:02:23] 在第一個作業裡面
[00:02:24] 我們其實是會把introduction
[00:02:25] 我們其實是會把introduction
[00:02:26] 這一塊的分數放最高的比例
[00:02:30] ok
[00:02:31] 我們可以跟大家講啊
[00:02:32] 到時候你的第三個作業也是一個
[00:02:34] 也是要寫上這個東西
[00:02:37] 不過你不同區塊的分數佔比就會不一樣
[00:02:41] 因為到時候我們就會更在乎你已經執行的進度有多少
[00:02:46] 那第一次我們是把introduction這邊佔的比例是最高的
[00:02:51] 好那方法的話就是說你預計可能要用什麼方法來做
[00:02:55] 好那方法的話就是說你預計可能要用什麼方法來做
[00:02:56] ok那你會說我都還沒有學了我怎麼知道用什麼方法
[00:02:59] 所以你要去找相關的文獻
[00:03:02] 然後要做一個
[00:03:04] 做一個整理啊
[00:03:06] 你至少學一下人家怎麼用什麼方法
[00:03:10] 所以這邊會佔75%的比例
[00:03:13] 其實都是目標都是為了要push大家去把這個報告寫出來
[00:03:18] 你預期的結果是怎麼樣
[00:03:22] 那你說我都還沒有做我怎麼知道預期結果
[00:03:25] 所以這裡就是叫你用想的
[00:03:27] 就是叫你比如說你也可以自己手繪一個圖
[00:03:31] 你預計最後出來的結果應該要什麼樣
[00:03:36] ok你可以畫一個示意圖
[00:03:39] 你可以比如說你如果是要去做一個什麼亂講
[00:03:44] Image generation
[00:03:46] 你要把某一個人的人臉加上鬍子
[00:03:49] 那你就預計他應該要有什麼樣子
[00:03:52] 那最後呢就是有一些參考文獻
[00:03:56] 好那再來一個很重要的就是
[00:03:57] 好那再來一個很重要的就是有一些參考文獻
[00:03:57] 好那再來一個很重要的就是有一些參考文獻
[00:03:57] 好那再來一個很重要的就是有一些參考文獻
[00:03:58] 請第三點喔請到這個網址
[00:04:04] 你的分組名單來這個網址你點進去
[00:04:15] 這裡呢你就是要填入你想要做的題目
[00:04:19] 你是什麼學校你的學校是什麼你叫什麼名字
[00:04:24] ok你填了之後
[00:04:26] 對不起你填
[00:04:28] 你填了之後呢你就會
[00:04:33] 有一個你能組的編號
[00:04:36] 好現在變成一大堆了
[00:04:38] 你們就得到一個組的編號
[00:04:41] ok所以呢我們會要求大家在報告裡面就要寫出你的編號
[00:04:48] 好所以請大家我再重開一次
[00:04:53] 好請大家依照有幾個原則喔
[00:04:58] 你不要在那邊亂填
[00:05:00] 因為這是所有人都可以寫入的
[00:05:02] 所以你不要去改到別人的
[00:05:05] 你不要去改到別人的
[00:05:06] 任何的資料
[00:05:08] 然後呢你也不要去弄一些有的沒有的
[00:05:12] 比如說現在這裡就有人在那邊亂寫
[00:05:15] 不知道在幹嘛
[00:05:17] 好然後按照順序寫
[00:05:21] 比如說你不要在那邊弄一些有的沒的
[00:05:25] 你說我不想當一號
[00:05:27] 這個第一編號一號的組別
[00:05:30] 我就一直拉拉拉
[00:05:32] 我就是要當編號253號
[00:05:34] 253號是我信心之母
[00:05:36] 我跟你講你這樣子搞
[00:05:38] 到時候就會漏掉
[00:05:40] 所以呢這只是一個組別的編號
[00:05:43] 不是你報告的數據
[00:05:45] 所以請大家老老實實的
[00:05:48] 如果一號有人填了你就填二號
[00:05:50] 二號有人填了就填三號
[00:05:52] 以此類為
[00:05:54] 中間不要空格
[00:05:56] 不要空
[00:05:58] 好中間不要空
[00:06:00] 不要做一些有的沒的事情
[00:06:02] 好那比如說
[00:06:04] 我最後填到編號453號
[00:06:06] 10號這一組
[00:06:08] 那回到你要講的那個報告
[00:06:10] 報告完成之後呢
[00:06:12] 你的檔名
[00:06:14] 就是homework1底線分組編號
[00:06:19] 就是底線10
[00:06:21] 假設你編號10號
[00:06:23] 或者編號27
[00:06:24] 或者怎麼樣
[00:06:25] 那當然你也可以把你的組別編號
[00:06:29] 寫在你的報告裡面
[00:06:32] 比如說寫在你的title底下
[00:06:35] 你是第27組這樣子
[00:06:37] ok好
[00:06:39] 為什麼要講那麼慢
[00:06:41] 這麼簡單的事情要這樣講那麼慢
[00:06:43] 因為就是會有人沒在聽
[00:06:45] 不符合規則
[00:06:46] 我就不知道為什麼
[00:06:47] 都長這麼大了
[00:06:49] 好那格式的話呢
[00:06:52] 就是CPPR的格式
[00:06:54] ok基本上第一個作業呢
[00:06:57] 就是讓大家寫一到兩頁的體驗報告
[00:07:01] 就好了
[00:07:02] 好那角角的期限
[00:07:04] 從今天開始就可以開始講
[00:07:06] 截止的日期是10月1號晚上11點59分
[00:07:16] 結束之後
[00:07:17] 系統就會自動關掉
[00:07:19] 好就兩個禮拜的時間
[00:07:22] 事實上這個作業我們在上週都已經透露給大家知道了
[00:07:26] 所以理論上
[00:07:27] 如果你要修正輪課
[00:07:29] 你應該都已經動起來
[00:07:32] 在找組員了
[00:07:34] 好然後開始
[00:07:35] 很快來看一下slide
[00:07:52] 有一些學校的同學
[00:08:12] 在反映說
[00:08:14] 要加簽
[00:08:16] 首先我先講
[00:08:17] 成大的名額都已經用完了
[00:08:21] 就是說都已經加滿了
[00:08:23] 不要再加簽了
[00:08:24] 我不會再加了
[00:08:25] 那如果其他同校
[00:08:26] 其他學校的同學
[00:08:28] 其實不同
[00:08:29] 應該是幾乎每個學校大概是50個名額
[00:08:32] 好那反正
[00:08:34] 各校就依照各校
[00:08:36] 自己的加簽程序下去做
[00:08:38] 那有同學說
[00:08:43] 他們學校加簽
[00:08:45] 是需要
[00:08:46] 什麼授課老師簽名同意的
[00:08:49] 那我覺得
[00:08:51] 請各校的同學自己去問清楚
[00:08:55] 教務處
[00:08:56] 如果今天這門課是拍卡的課的話
[00:09:00] 難道也需要我一個一個去簽嗎
[00:09:03] 那如果全國60幾間學校
[00:09:06] 每一個要加簽的
[00:09:07] 都要我去簽名
[00:09:09] 這樣子是不是很沒有效率
[00:09:11] 會不會
[00:09:12] 比如說針對臺卡聯盟的課
[00:09:14] 其實是
[00:09:16] 教務處
[00:09:17] 你們貴校的教務處
[00:09:18] 有自己的做法
[00:09:19] 所以請去問清楚
[00:09:21] 回應一下
[00:09:26] 這個相關的問題
[00:09:29] 線上課的人怎麼分組
[00:09:31] 你們自己去分組吧
[00:09:32] 我們上次有回答過
[00:09:35] 就是你們反正自己
[00:09:36] 找自己學校裡面的人分組
[00:09:38] 線上揪團分組
[00:09:40] 你們可以自己在MTU
[00:09:42] COOL的類似討論區裡面
[00:09:44] 徵求組員whatever
[00:09:46] 然後你們自己去約
[00:09:47] 自己去分組
[00:09:48] YouTube會留直播的錄影啊
[00:09:53] 有啊這顯然上週沒有上課
[00:09:55] 我們上週直播就有錄影
[00:09:59] 然後我們還附旁白咧
[00:10:03] 我可以再強調一次
[00:10:11] 但是以後不要再問這個問題
[00:10:13] 12月10號實體考試
[00:10:16] 沒有錯
[00:10:18] 線上上課的同學
[00:10:19] 也是實體考試
[00:10:21] 比如說隨便亂講
[00:10:23] 臺南大學的同學
[00:10:25] 你現在在線上上課
[00:10:27] 到時候12月10號
[00:10:29] 你就在臺南大學考試
[00:10:32] 好理論上根據我們
[00:10:34] 往年的執行的經驗
[00:10:36] 你們學校會幫你借一間電腦教室
[00:10:42] 然後可以讓你只能連上MTU COOL
[00:10:51] 然後你就在那一間考試
[00:10:52] 然後
[00:10:53] 學校會派監考人員去進行監考
[00:10:56] 所以超過4個人
[00:11:00] 剛剛規則已經講過了
[00:11:02] 這種事情就不要再問了
[00:11:04] 這個分組的事情不要再回答
[00:11:09] 這個也不用回答了
[00:11:10] 沒有點名
[00:11:14] 這個自己有意願的自己想辦法
[00:11:17] 什麼IG啊
[00:11:19] 這個回答過了
[00:11:20] 好
[00:11:25] 我第一次遇到有這種問題
[00:11:28] 不要擔
[00:11:32] 你們自己分組的自己去想辦法
[00:11:39] 大家都長大了
[00:11:40] 你們是大人了
[00:11:41] 你們自己去處理
[00:11:43] 線上組隊的
[00:11:46] 這個謝謝剛剛應該是有同學反映
[00:11:50] 我們剛剛直播畫面有問題
[00:11:52] 謝謝的確我們現在已經進入到第三次的直播
[00:11:56] 現在終於
[00:11:57] 大家糾團的這個就不用再slide啦
[00:12:07] 這是要問我的問題
[00:12:08] 不是要問同學們的問題
[00:12:10] 助教的共同信箱剛剛畫面裡面沒有看到
[00:12:17] 你到intucor就可以看到了
[00:12:19] 你可以再秀一次
[00:12:22] 這個不是聊天室
[00:12:53] 這是在問我
[00:12:55] 好
[00:12:56] 題目當然是自己定的
[00:13:01] 簡短的回答到這邊
[00:13:04] 要糾團的你們自己想辦法去糾
[00:13:07] 再來就要進入到我們的課程
[00:13:11] 來再來我們開始正式的上課
[00:13:28] 我們今天要很快的把第二章講完
[00:13:32] 第二章講的是Intelligent Agents
[00:13:35] 那很快復習
[00:13:37] 什麼叫一個agent呢
[00:13:39] agent就是一個東西
[00:13:41] 這個東西可以透過sensor感測到一些資訊
[00:13:48] 然後根據感測到的資訊
[00:13:50] 可以做一些動作
[00:13:52] 做一些事情
[00:13:53] 透過這個所謂的accurator
[00:13:55] 去做一些事情
[00:13:57] 那他做完這件事情之後
[00:13:59] 可能會影響到這個環境
[00:14:02] 所以他可能可以從環境裡面
[00:14:04] 感測到一些資訊
[00:14:06] 那我可以做一些動作
[00:14:08] 那我做完動作之後呢
[00:14:09] 也有可能會改變這整個環境的狀態
[00:14:13] 好
[00:14:14] 那在這邊大家要注意的是
[00:14:16] 這裡講的感測器
[00:14:17] 不見得一定是什麼IoT的
[00:14:19] 什麼物聯網感測器
[00:14:21] 溫度時度感測器喔
[00:14:22] 不是喔
[00:14:23] 他是很廣泛的一種講法
[00:14:25] 基本上就是他可以收到一些資料的意思
[00:14:28] 然後呢
[00:14:30] 我收到一些資料之後
[00:14:32] 做了某一些判斷跟決定之後
[00:14:34] 我會做某一些事情
[00:14:36] 那這些事情呢
[00:14:38] 也不見得一定是
[00:14:40] 真正的實體世界當中
[00:14:42] 動物
[00:14:43] 比如說
[00:14:44] 往右走
[00:14:45] 往左走
[00:14:46] 機器手臂舉起來
[00:14:48] 或者是什麼
[00:14:49] 他也有可能只是
[00:14:50] 我傳送一個什麼資料出去
[00:14:52] 傳送一個
[00:14:55] 什麼樣子的聲音出去
[00:14:57] 都有可能
[00:14:58] 為了做某一個動作
[00:14:59] 所以agent的定義是很廣很廣的
[00:15:02] 好
[00:15:03] 那我們上次呢
[00:15:05] 就提到說
[00:15:06] 當我們在談論一個agent的時候
[00:15:09] 一個完整的談論法
[00:15:11] 其實是這個定義的
[00:15:13] 我們稱呼它叫做一個
[00:15:15] Task Environment
[00:15:17] 那講到Task Environment呢
[00:15:19] 就會牽涉到四個元素
[00:15:23] PEAS
[00:15:25] Performance Environment Actuator
[00:15:27] 跟Sensors
[00:15:29] Performance指的就是
[00:15:31] 我如何去評判
[00:15:33] 這一個agent他的效能好不好
[00:15:35] 所以這裡舉了一個例子
[00:15:37] 我們上次提到
[00:15:38] 最後提到的是
[00:15:39] 比如說計程車司機
[00:15:41] 他的Performance好不好
[00:15:42] 我們可能有很多種
[00:15:44] 比如說
[00:15:46] 他能夠讓我
[00:15:47] 優快抵達目的地越好
[00:15:49] 或者是說
[00:15:50] 他開的路線
[00:15:51] 道路最平穩
[00:15:53] 或者是說
[00:15:54] 我花的錢越少越好
[00:15:56] 這都是屬於一種Performance
[00:15:58] 那就看你的需求而定
[00:16:00] 你可以有不同的Performance的定義
[00:16:02] 那計程車司機所處在的環境
[00:16:06] 當然就是道路嘛
[00:16:08] 所以一般的道路平面
[00:16:10] 然後道路有顛簸的
[00:16:12] 有石頭路
[00:16:14] 有柏油路
[00:16:15] 然後呢
[00:16:16] 道路上面可能會有交通耗製
[00:16:19] 可能有其他的行人
[00:16:21] 騎腳踏車的
[00:16:22] 這個都是他所謂的環境因素
[00:16:24] Actuator
[00:16:26] 就是他可以做什麼事
[00:16:28] 比如說以計程車司機來講
[00:16:30] 他可以加速煞車
[00:16:32] 往右轉往左轉
[00:16:34] 按喇叭
[00:16:35] 這些都是他可以做的事
[00:16:36] 那Sensor呢
[00:16:38] 身為一個計程車司機
[00:16:40] 他接收到訊號的來源
[00:16:43] 如果是人的話
[00:16:44] 可能就是耳朵聽得到
[00:16:45] 眼睛看得到
[00:16:46] 如果是自駕車
[00:16:48] CyberCab
[00:16:49] 他可能有攝影機
[00:16:51] 那或者說其他的自駕車的Solution
[00:16:54] 可能有聲浪、光達等等等等的
[00:16:56] 這些都是所謂的Sensor
[00:16:59] 所以在傳統定義上
[00:17:02] 當我們在講一個Asian的時候
[00:17:04] 我們就是要定義好
[00:17:05] 他的PEAS
[00:17:07] 好
[00:17:08] 那Asian這個詞呢
[00:17:10] 其實大家在今年
[00:17:11] 應該聽了非常多次了
[00:17:13] 對不對
[00:17:14] 今年Asian大爆發嘛
[00:17:17] 但是我們必須跟大家講
[00:17:19] Asian的這個概念
[00:17:21] 其實在過去幾十年的
[00:17:23] 人工智慧的開發當中
[00:17:25] 老早人家就定義好Asian就是
[00:17:29] 就是這樣子的東西
[00:17:31] 那不過以現在這個年代來講
[00:17:33] 其實啊
[00:17:34] PEAS這樣的地理還
[00:17:37] 缺了一個很重要的東西
[00:17:39] 就是大腦
[00:17:41] 這個Asian的大腦是什麼
[00:17:44] OK
[00:17:45] 好
[00:17:46] 那在過去傳統的AI裡面
[00:17:49] 比較避免
[00:17:50] 比較沒有在談大腦這件事
[00:17:53] 因為大腦有各式各樣不同的做法
[00:17:56] 那當然以現在
[00:17:57] Right now這個時間點
[00:17:58] 2026年來講
[00:18:00] 很重要的就是說
[00:18:01] 我們用LLM
[00:18:02] 來當成是Asian的大腦
[00:18:04] 由它來決定
[00:18:06] 我收到什麼樣的訊息
[00:18:07] 我要做哪些動作
[00:18:11] 好那後續呢
[00:18:12] 當然有很多其他的例子啦
[00:18:14] 比如說醫療診斷系統
[00:18:16] 也可以是一個Asian啊
[00:18:17] 然後這個衛星影像的分析系統
[00:18:21] 也可以是一個Asian啊
[00:18:23] 或者是互動式的英語教學
[00:18:27] 也可以是一個Asian啊
[00:18:29] 所以任何的東西
[00:18:30] 只要符合有這個PEAS的
[00:18:32] 都可以視為是一種Asian
[00:18:34] 那整個Task也就是
[00:18:37] Task Environment
[00:18:38] 有幾種特性
[00:18:39] 其實當你的Task Environment變的時候
[00:18:43] 我們去設計Agent的做法
[00:18:46] 可能就會不一樣
[00:18:47] 因為它的狀態
[00:18:48] 它的條件就不一樣
[00:18:50] 所以有幾個不同的角度
[00:18:52] 來去分類你的這個Task Environment
[00:18:56] 第一個角度叫做
[00:18:58] Fully Observable
[00:18:59] 還是Partially Observable
[00:19:01] 今天你這個環境裡面的資訊
[00:19:04] 是可以全然透明的
[00:19:07] 被看到的
[00:19:08] 還是隻有部分被看到的
[00:19:10] 所以比如說
[00:19:11] 今天如果是下圍棋
[00:19:13] 這個資訊一定是全然可以被看到的
[00:19:17] 整個盤面你不可以
[00:19:19] 蓋住某一部分的棋盤
[00:19:21] 不讓對手看到
[00:19:22] 不行嘛
[00:19:23] 那什麼叫部分可被看到
[00:19:25] 比如說
[00:19:28] 比如說我們打電動
[00:19:30] 世紀帝國
[00:19:31] 還是什麼
[00:19:33] LOL
[00:19:34] 有LOL這種東西嗎
[00:19:35] 對LOL這種
[00:19:37] 一開始地圖
[00:19:38] 一開始的時候大部分都黑的嘛
[00:19:39] 對不對
[00:19:40] 你只有一小部分
[00:19:41] 是你視野可及的範圍
[00:19:43] 其他地方發生什麼事你都不知道
[00:19:45] 那你要在這種情況之下
[00:19:47] 你要做決定
[00:19:48] 這是Partially Observable
[00:19:50] 這是第一種觀察的角度
[00:19:53] 第二種就是說你的Task Environment裡面
[00:19:56] 你是單一的Agent
[00:19:58] 還是會有多個Agent互動
[00:20:00] 所以比如說下棋
[00:20:02] 你就是有兩個
[00:20:04] 下圍棋你就有兩個對手
[00:20:06] AAB兩個對手
[00:20:07] 你要根據對方下了一個什麼棋
[00:20:09] 下了一個什麼位置
[00:20:10] 你再下一個什麼位置
[00:20:11] 所以它就是Multi-Agent的形式
[00:20:15] 那如果你這個
[00:20:18] 這個環境裡面只有一個Agent在動作
[00:20:21] 那就是Single Agent
[00:20:23] 所以比如說我們上次課程裡面談到的
[00:20:26] 如果今天這整個世界
[00:20:28] 就只有兩塊地磚
[00:20:29] 然後我有一臺吸塵器
[00:20:31] 這樣子的Task Environment就是Single Agent
[00:20:35] 然後再來另外一個角度是
[00:20:38] 你這個Environment
[00:20:40] 你這個動作是Deterministic
[00:20:42] 還是Socastic
[00:20:44] 所謂的Deterministic是說
[00:20:46] 當我叫它做某一個動作的時候
[00:20:49] 它對於環境的影響
[00:20:52] 就一定是
[00:20:54] 你做了那個動作之後會發生的影響
[00:20:57] 比如說吸塵器那個例子
[00:20:59] 我叫它往右邊的那塊地磚走
[00:21:03] 我做完這個動作之後
[00:21:05] 它的環境一定就變成是
[00:21:07] 吸塵器跑到右邊的那塊地磚
[00:21:10] 這是肯定的
[00:21:11] 這叫Deterministic
[00:21:13] 那有一些環境是Socastic
[00:21:17] 就是說你覺得比如說
[00:21:19] Taxi Driving就是Socastic
[00:21:22] 你叫它
[00:21:25] 就是說你身為一個Taxi Driver
[00:21:28] 你覺得往右轉
[00:21:31] 一定就是
[00:21:35] 你的整個路面就一定是
[00:21:37] 一定是
[00:21:39] 變成一個你所預期的一個狀況
[00:21:42] 這件事情大部分的時間是對的
[00:21:44] 但為什麼會有車禍發生
[00:21:46] 就是偶爾就是會有不確定性發生
[00:21:50] 你再往右轉
[00:21:52] 你轉過去之後
[00:21:54] 突然有一個什麼東西掉下來
[00:21:56] 或一個行人衝出來
[00:21:57] 所以它是有一些不確定性的
[00:22:00] 這種就叫Socastic
[00:22:02] 有隨機性
[00:22:04] 另外一個觀點叫做
[00:22:06] Episodic跟Sequential
[00:22:08] 就是你是情節不連貫的
[00:22:11] 還是連貫的
[00:22:12] 比如說
[00:22:15] 比如說下騎跟開車都是連貫的
[00:22:19] 你的下一個狀態一定都是
[00:22:22] 源自於你上一個狀態的
[00:22:24] 上一個狀態的一個連結
[00:22:26] 它一定是一個連貫的一個情況
[00:22:28] 那某一些情境它是不連貫的
[00:22:33] 它沒有Depends on the actions taken in previous episodes
[00:22:41] 那再來就是說Static跟Dynamic
[00:22:47] 這意思是說當你的Agent
[00:22:50] 你收到訊息
[00:22:52] 你正在轉化成你動作的這段期間
[00:22:57] 你的環境會不會動
[00:22:59] 會不會變動
[00:23:01] 也就是說你收到訊息
[00:23:03] 你總是需要一點時間思考
[00:23:05] 來進行決策
[00:23:07] 假設你只思考了兩秒
[00:23:10] 一秒好了
[00:23:11] 一秒好
[00:23:12] 你在這一秒之內
[00:23:13] 你的環境說不定已經變動了
[00:23:15] 還是沒變
[00:23:17] 所以你看
[00:23:18] 下騎就是我想個五分鐘
[00:23:21] 盤面還是沒變
[00:23:23] 那它就是Static
[00:23:24] 可是如果是開車
[00:23:26] 其實開車道路上的訊息
[00:23:29] 隨時都在變
[00:23:31] 所以即使我只花0.5秒
[00:23:34] 我收到一句
[00:23:35] 只花一個0.5秒
[00:23:37] 在進行決策
[00:23:38] 可能路面的情況都會在變
[00:23:40] 比如說後面的那臺車
[00:23:42] 那臺車又跟得更近了
[00:23:44] 前面有一個什麼人
[00:23:46] 又突然要衝出來
[00:23:48] 又變出來了這樣子
[00:23:51] 然後Discrete或Continuous
[00:23:53] 今天你的環境的變動
[00:23:56] 是Continuous變動
[00:23:58] 還是離散的變動
[00:24:00] 比如說下騎就是離散的
[00:24:02] Taxi Driving就是連續的
[00:24:04] 因為這個是一個
[00:24:05] 實體的一個世界
[00:24:07] 然後再來呢
[00:24:08] None or Unknown
[00:24:10] 你今天在這個環境裡面
[00:24:12] 你是知道它這個環境背後的
[00:24:16] 運作的原理嗎
[00:24:18] 比如說假設是實體世界
[00:24:20] 你是已經知道在這個世界裡面
[00:24:23] 整個所有資訊
[00:24:25] 變動的
[00:24:27] 它背後的物理原理嗎
[00:24:29] 你知道這個規則嗎
[00:24:31] 你是已經知道
[00:24:32] 還是你不知道
[00:24:34] 這個就是None跟Unknown
[00:24:36] 所以底下呢
[00:24:38] 這邊舉的例子就是說
[00:24:39] 你各式各樣不同的Task Environment
[00:24:42] 它在這些角度裡面
[00:24:45] 個別是什麼樣子的屬性
[00:24:48] 所以完全就看說
[00:24:50] 你要處理的問題
[00:24:52] 可能是屬於哪一種
[00:24:54] 你可能你的應對的策略
[00:24:56] 就不一樣
[00:24:57] 在開發Agent的時候
[00:25:03] 事實上我們整體而言
[00:25:05] 其實我們可以說AI
[00:25:07] 人工智慧
[00:25:09] 其實就是要去設計Agent
[00:25:13] 那尤其呢
[00:25:14] 我們要設計的是Agent Program
[00:25:18] 這個Agent Program的用途就是
[00:25:22] 當它收到一些資訊的時候
[00:25:25] 它要透過這個Agent Program
[00:25:28] 來決定它要做什麼動作
[00:25:31] 它要做什麼動作
[00:25:33] 這中間的這個就叫做Agent
[00:25:35] 那如果說
[00:25:38] 你跟一些Computing Device
[00:25:42] 連結在一起
[00:25:43] 或者說跟一些物理上的一些
[00:25:46] 馬達啦
[00:25:47] 或者說感測器
[00:25:49] 連結在一起的話
[00:25:51] 這些所謂的物理性的感測器
[00:25:54] 跟制動器
[00:25:55] 馬達啊
[00:25:56] 動作機器手臂啊
[00:25:58] 輪子啊
[00:25:59] 這些東西
[00:26:00] 它是實體的
[00:26:01] 我們就稱為它是Architecture
[00:26:03] 它是實體的結構
[00:26:04] 因此整體而言
[00:26:06] 一個Agent
[00:26:08] 其實包含了Architecture加上Program
[00:26:11] Program比較像是軟體的部分
[00:26:13] 它是負責決策的
[00:26:16] Architecture就是
[00:26:18] 可能是感測資料的
[00:26:20] 或者負責做動作的
[00:26:22] 所以整個Agent的部分
[00:26:24] 你可以把它想像成
[00:26:25] 它其實就包含硬體跟軟體
[00:26:27] 那當然啊
[00:26:28] 很多時候我今天
[00:26:30] 我也沒有說
[00:26:32] 一定要驅動一個什麼實體的機器人
[00:26:34] 在做什麼事情
[00:26:35] 我完全在虛擬空間當中
[00:26:37] 去進行虛擬
[00:26:39] 來做一些事情
[00:26:40] 模擬一些事情
[00:26:41] 也可以說是一個Agent
[00:26:43] 也可以說是一個Agent
[00:26:44] 因為在那個模擬的空間裡面
[00:26:47] 它的Sensor其實就是
[00:26:50] 可能就是
[00:26:52] 我輸入的資料
[00:26:54] 我就已經感測到
[00:26:56] 我直接輸入那些資料
[00:26:58] 給我的Agent Program
[00:26:59] 然後呢
[00:27:00] 我的Agent Program
[00:27:01] 可能操縱一個虛擬的人物
[00:27:03] 往右走往左走
[00:27:04] 所以它不見得一定是要
[00:27:06] 搭配實體世界的
[00:27:09] 這個真正的東西
[00:27:12] 所以In that case
[00:27:14] 在虛擬世界當中呢
[00:27:16] Architecture其實就是
[00:27:17] 譬如說好像我們玩電玩
[00:27:20] 我們所操縱的那個虛擬人物
[00:27:22] 它其實就是你的Architecture
[00:27:24] 好
[00:27:27] 那我們先從一個最簡單的
[00:27:29] 假設我們要開發一個Agent Program
[00:27:32] 一個最簡單的做法就是
[00:27:34] 我就寫規則嘛
[00:27:36] 或者我寫一個表格嘛
[00:27:37] 對不對
[00:27:38] 我今天當我遇到一個什麼樣資料的時候
[00:27:42] 我就做一個動作
[00:27:44] 遇到什麼樣資料我就做一個動作
[00:27:46] 或者連續我接收到哪些資料的情況下
[00:27:51] 我就做什麼樣的動作
[00:27:53] 就用查表的方式
[00:27:55] 這是Very Very Trivial的Agent Program
[00:27:58] 但是我們很快就知道說
[00:28:00] 這個東西一定不可行吧
[00:28:03] 因為我們不可能列舉所有的狀況
[00:28:07] 然後把這個Table寫得很長很長
[00:28:09] 對不對
[00:28:10] 然後不可能是用這樣子來做
[00:28:17] 比較具體可行的一個最簡單的做法呢
[00:28:19] 叫做Simple Reflex Agent
[00:28:22] 那它簡單來講就是說
[00:28:24] 我也不要看很長時間的資料
[00:28:27] 我就是隻看單一一個瞬間
[00:28:29] 然後呢我去寫一個規則
[00:28:31] 來做動
[00:28:33] 這個就是我最最簡單的Agent Program
[00:28:36] 所以譬如說
[00:28:37] 之前的那個吸塵器的例子
[00:28:40] 欸如果現在我所在的地磚
[00:28:42] 是髒的
[00:28:44] 那我就吸塵嘛
[00:28:46] OK
[00:28:47] 如果
[00:28:48] 我所在的地方是乾淨的
[00:28:51] 然後我就會進入到這裡嘛
[00:28:52] 我如果現在的位置在A
[00:28:55] 那我就往右走
[00:28:56] 我如果現在這個地磚是乾淨的
[00:28:58] 然後我的位置在B
[00:28:59] 那我就往左走
[00:29:00] 就這樣
[00:29:01] 就這麼簡單的規則
[00:29:03] 它就是一個最最簡單的Agent Program
[00:29:07] 只考慮單一一個瞬間
[00:29:10] 收到的資料
[00:29:11] 然後我去做一個反射性的動作
[00:29:15] OK
[00:29:16] 這是最簡單的Agent
[00:29:17] 好那畫成示意圖的話
[00:29:21] 可以長成像這樣嗎
[00:29:23] 就在環境裡面
[00:29:25] 我透過Sensor
[00:29:27] 我取得了一些資料
[00:29:30] 然後呢
[00:29:32] 我看了這個資料之後
[00:29:33] 我根據這裡的規則
[00:29:35] 寫出來的規則
[00:29:36] 來去決定我要做什麼動作
[00:29:39] 這樣子
[00:29:40] 好就這麼簡單
[00:29:42] 那你說那可不可以進步一點呢
[00:29:45] 有
[00:29:46] 下一個再進步一點的
[00:29:47] 叫做Model Based Agent
[00:29:50] 它的意思是說
[00:29:52] 我今天
[00:29:53] 我每次我收到訊息之後
[00:29:56] 收到資料之後
[00:29:57] 我也許這個資料
[00:29:59] 不完整
[00:30:01] OK不完整
[00:30:02] 我可能先往左邊看
[00:30:04] 我看到左邊的資料圖
[00:30:06] 那我右邊還沒有看到嘛
[00:30:08] 可是我如果今天我先往左邊看
[00:30:10] 看到左邊的資訊
[00:30:12] 我能不能夠累積
[00:30:15] 我所看到的資訊
[00:30:17] 然後我再統一做一個
[00:30:19] 比較好的一個反應
[00:30:21] 好所以Model Based Agent
[00:30:23] 跟那種簡單反射式的Agent
[00:30:25] 就是說
[00:30:26] 它有一個Internal State
[00:30:28] 或者是有Memory的這個概念
[00:30:31] 你Sense到資料進來之後
[00:30:34] 它會儲存
[00:30:37] 過程的資料
[00:30:40] 它會儲存
[00:30:42] 過去它看過的這些資料
[00:30:45] 所以說它可以理解說
[00:30:47] 我目前這個Involvement
[00:30:49] 狀態是怎麼變動的
[00:30:51] 那我現在看到了什麼
[00:30:54] 然後我不只是這樣
[00:30:56] 我還剛剛前面那個瞬間
[00:30:58] 狀態是什麼樣
[00:31:00] 我在剛剛那個瞬間
[00:31:01] 我做了什麼動作
[00:31:02] 以及我在現在這個瞬間
[00:31:04] 我看到了哪些資料
[00:31:07] 我一起統整來去決定
[00:31:10] 我要做什麼動作
[00:31:12] 來去決定我要做什麼動作
[00:31:15] 那在這裡呢
[00:31:16] 決定做什麼動作
[00:31:17] 依舊是一些規則
[00:31:19] 所以它相當於是
[00:31:21] 考慮到更多情況之下
[00:31:24] 然後還是根據規則來進行
[00:31:26] 你的動作的判斷
[00:31:28] 這叫Model Based Agent
[00:31:31] 好那所以呢
[00:31:34] 這個依舊是相當的簡單
[00:31:37] 那在下一個部分
[00:31:39] 就是說很多時候呢
[00:31:41] 我看到我目前
[00:31:44] 的環境的狀態是如何
[00:31:47] 讓我們很有效率的
[00:31:50] 去運作這個Agent
[00:31:53] 所以事實上呢
[00:31:55] 這個Agent呢
[00:31:56] 有時候是需要一些目標的
[00:31:59] 你告訴他目標
[00:32:01] 當我在進行決策的時候
[00:32:03] 他要決定的事情是
[00:32:05] 我做哪一個決策
[00:32:06] 會離我的目標
[00:32:08] 更快接近我的目標
[00:32:10] 那這一類的Agent
[00:32:11] 就叫做Goal Based Agent
[00:32:13] OK Goal Based Agent
[00:32:15] 那Goal Based Agent的行為呢
[00:32:18] 為什麼
[00:32:20] 這個會比Model Based來得更好
[00:32:23] 因為它可以
[00:32:25] 當你的目標變了
[00:32:28] 我其實中間的那個
[00:32:30] 他會採用的行為也就變了
[00:32:33] 所以說呢
[00:32:34] 他的Behavior can easily be changed
[00:32:36] to go to different destination
[00:32:39] Simply by specifying the destination as the goal
[00:32:42] 那隨著你的目標變動
[00:32:44] 你已經運作到一半了
[00:32:46] 你目標如果突然變了
[00:32:48] 他有辦法
[00:32:49] 即時的
[00:32:50] 現在因應性的目標
[00:32:52] 做出新的動作決策
[00:32:55] 所以說
[00:32:57] 跟前面兩種
[00:33:00] Condition and Action Rule
[00:33:02] 這種做法不一樣的地方是說
[00:33:04] 他要考慮到未來
[00:33:06] 他不是隻考慮到
[00:33:07] 我過去看到哪些資料
[00:33:09] 然後根據某種規則來進行決策
[00:33:12] 而是我考慮到
[00:33:13] 我如果做了這個決策
[00:33:16] 我的未來會不會變得更好
[00:33:18] 會不會讓我更Happy
[00:33:20] 會不會讓我覺得更好
[00:33:22] 這個叫Goal Based Agents
[00:33:24] 所以說呢
[00:33:25] 你可以看到說
[00:33:26] 他不只有
[00:33:27] 過去這個世界怎麼變動的
[00:33:30] 過去我怎麼做動的
[00:33:32] 我另外在進行決策的時候
[00:33:35] 我要考慮到我的目標是怎麼
[00:33:38] 然後呢
[00:33:39] 我是要往目標去前進
[00:33:42] OK
[00:33:43] 而不是隻看
[00:33:44] 我過去已經送到的資料
[00:33:46] 這叫Goal Based Agents
[00:33:49] 然後那Goal Based Agents還不夠啊
[00:33:52] 他還沒有辦法做出高品質的行為
[00:33:56] 在有的時候沒有辦法
[00:33:59] 為什麼呢
[00:34:00] 因為有的時候你只告訴他
[00:34:01] 目標是不夠的
[00:34:03] 原因是有時候你有好幾個目標
[00:34:07] 而這幾個目標是衝突的
[00:34:10] 比如說我們去搭計程車
[00:34:12] 我們又希望
[00:34:14] 越快抵達目的地越好
[00:34:16] 然後又希望
[00:34:18] 你的整個行車的過程
[00:34:20] 越安全越好
[00:34:22] 這兩個目標有一點點衝突
[00:34:25] 你希望越快抵達
[00:34:27] 那就是司機要開比較快啊
[00:34:28] 可是司機開比較快
[00:34:30] 就可能越危險啊
[00:34:32] 對不對
[00:34:33] 那我們是不是兩個目標
[00:34:34] 我們都想達到
[00:34:35] 所以有的時候呢
[00:34:37] 我們的目標不只一個
[00:34:39] 我們有多個
[00:34:40] 而這多個
[00:34:41] 還彼此衝突
[00:34:42] 那所以在這種情況之下呢
[00:34:48] 我們就要考慮的是
[00:34:50] 所謂的
[00:34:51] Utility based agent
[00:34:53] Utility這個字呢
[00:34:54] 就是效益的意思
[00:34:57] 你做了某一個決策之後
[00:35:00] 他當然是要往目標前進
[00:35:02] 但是他往目標前進的
[00:35:05] 效益有多高
[00:35:07] 我要去取
[00:35:08] 我要去做出一個整體而言
[00:35:11] 效益最大化的
[00:35:13] 那個動作
[00:35:15] 因為我今天好幾個目標
[00:35:17] 我會彼此衝突
[00:35:18] 我只好權衡之下
[00:35:21] 選擇比如說
[00:35:23] 你今天是要越快抵達目標
[00:35:26] 目的地還是說要安全的
[00:35:28] 你可能想說
[00:35:29] 生命層可貴
[00:35:31] 對不對
[00:35:32] 我慢一點沒關係
[00:35:33] 我寧可我要安全一點
[00:35:36] 或者是說呢
[00:35:37] 今天我知道我這一路上
[00:35:39] 要經過的沒有什麼複雜的路口
[00:35:42] OK
[00:35:43] 那大概不會有什麼太多安全的疑慮
[00:35:47] 那我就是越快越好
[00:35:49] 這個你都是可以去進行
[00:35:51] 所以你的效益的定義
[00:35:53] 也會根據你的
[00:35:54] 這個不同的應用而定
[00:35:56] 所以說呢
[00:35:57] 我們這裡講說一個理性的
[00:35:59] Utility based agent
[00:36:01] 什麼叫理性的
[00:36:02] 我們上次有介紹過
[00:36:03] 一個理性的Utility based agent
[00:36:06] 他會最大化預期的效益
[00:36:10] 當我做一年
[00:36:12] 我在進行決策
[00:36:14] 要take某一個action的時候
[00:36:16] 他就是要去最大化
[00:36:18] 那個可能的預期的效益
[00:36:20] 好那這是一個示意圖啦
[00:36:24] 就是說我不只知道過去的
[00:36:27] 這個行為模式跟狀態的變化
[00:36:30] 我還要去預估說
[00:36:33] 現在的這幾個目標整體而言
[00:36:36] 我如果做了某一個決策
[00:36:39] 我帶來的效益有多高
[00:36:41] 然後我可能
[00:36:42] 我可以
[00:36:43] 比如說我可以
[00:36:44] 往右走
[00:36:45] 我可以往左走
[00:36:46] 我可以往前
[00:36:47] 我可以多加速一點
[00:36:49] 或者說我要煞車一點
[00:36:51] 整體而言
[00:36:53] 在這麼多種可能性裡面
[00:36:55] 選擇一組最好的參數
[00:36:58] 來最大化
[00:37:00] 我可能達到的效益
[00:37:01] 這個就是所謂的
[00:37:02] Utility based agent
[00:37:04] OK
[00:37:06] 好那最後一個
[00:37:08] 就是Learning agents
[00:37:10] 我們當然希望說
[00:37:12] 你能夠評估效益
[00:37:14] 那你最好
[00:37:16] 你這個agent
[00:37:17] 你在進行決策的這整個的過程
[00:37:20] 不要由我們人來設計
[00:37:23] 而是你自動從資料裡面去學會
[00:37:27] OK那這個就是Learning agent
[00:37:29] Learning agent is responsible for making improvement
[00:37:32] 我們希望他越做越好
[00:37:34] OK好
[00:37:35] 然後最好是
[00:37:38] 你根據過去的
[00:37:40] 你所收到的資料
[00:37:43] 你做過的行為
[00:37:44] 那我們現在也可以評估效益了吧
[00:37:47] 那我們就發現說
[00:37:50] 今天在下午三點的時候
[00:37:53] 我走某一條路
[00:37:55] 時數開多少
[00:37:59] 我上次是這麼開
[00:38:00] 效果不錯
[00:38:02] 那我下一次
[00:38:03] 在差不多三點的時候
[00:38:04] 又有同樣的客人
[00:38:06] 需要我做
[00:38:07] 去某一個目的地的時候
[00:38:09] 我是不是有
[00:38:11] 有那個能力知道說
[00:38:13] 我上次的那個很不錯
[00:38:15] 那我這一次呢
[00:38:17] 就繼續用這樣的模式來走
[00:38:19] 譬如說上次我走某一條路很不好
[00:38:22] 我是不是可以這一次
[00:38:23] 我就避免做這件事
[00:38:25] 這個就是Learning的一個agent
[00:38:28] 要做的事情
[00:38:29] 所以你看到這個設計圖就是說
[00:38:31] 資料進來之後
[00:38:33] 你可以去評估我的效益
[00:38:35] 然後
[00:38:37] 當然你可以做一些
[00:38:38] 比如說監督室的學習
[00:38:41] 那來給他一些評判
[00:38:44] OK
[00:38:45] 這個上次做的某些agent
[00:38:47] 好或不好
[00:38:48] 你給他一些監督的訊號
[00:38:51] 然後呢讓他
[00:38:52] 反覆不斷的去變動
[00:38:54] 他的這個agent program
[00:38:56] 然後呢
[00:38:57] 越做越好越做越好
[00:38:59] 好
[00:39:00] 這個就是Learning agent
[00:39:01] OK
[00:39:02] 好
[00:39:03] 這個講起來非常非常的虛幻
[00:39:06] 有沒有
[00:39:07] 講得非常high level
[00:39:08] 那講完了
[00:39:09] 大家好像也不太知道
[00:39:10] 這到底在幹嘛
[00:39:11] 但事實上你可以想像得到
[00:39:12] 這個Learning agent呢
[00:39:14] 其實就是
[00:39:15] 後來我們慢慢的從
[00:39:17] 機率推論變成Machine learning
[00:39:20] 到現在過去這十幾年的Deep learning
[00:39:23] 其實基本上就是Learning agent
[00:39:26] 這整個過程
[00:39:29] 那以上講到這邊
[00:39:30] 這個就是第二章
[00:39:32] 我們說過第一章跟第二章
[00:39:34] 都是聊聊天的
[00:39:36] 講得非常非常的high level
[00:39:38] 非常非常的high level
[00:39:40] 好
[00:39:41] 第二章講到這邊
[00:39:43] 有沒有什麼問題
[00:39:49] 在slido上面
[00:39:50] 他說PPT不定時會狂散
[00:39:53] 我不知道助教有看到嗎
[00:40:00] 會散嗎
[00:40:12] 可以去NTU Google討論板
[00:40:17] 分組表格在哪裡
[00:40:18] OK
[00:40:19] 我剛剛說了
[00:40:20] 請好好上課
[00:40:22] OK
[00:40:23] 來
[00:40:24] 那我們就先休息一下
[00:40:26] 再回來休息十分鐘
[00:40:28] 再回來進行下一章
[00:41:03] 你說要做
[00:41:05] 要偏向研究的方面
[00:41:07] 會比較偏向去做改善
[00:41:10] 去研究
[00:41:11] 會更好
[00:41:14] 會更好
[00:41:15] 對
[00:41:16] 如果除了這個
[00:41:17] 你是想做什麼
[00:41:18] 因為前陣子Google有那個
[00:41:20] 蒼蠅那個model
[00:41:22] 什麼
[00:41:23] 蒼蠅的那個
[00:41:24] 蒼蠅
[00:41:25] 蒼蠅那個model
[00:41:26] 對
[00:41:27] 它可以拿來跑一些environment
[00:41:29] 我想要拿它跟一般的Iron
[00:41:31] 去做comparison
[00:41:33] 可以啊
[00:41:34] 我想說那這樣的話
[00:41:35] 這個算是一種study嗎
[00:41:37] 還是它算是
[00:41:38] 就單純比較
[00:41:39] 我沒有去針對它去做
[00:41:40] 不如我只想要做
[00:41:42] 比較說
[00:41:43] 這樣一種有什麼樣的差異
[00:41:45] 可以
[00:41:46] 可以啦
[00:41:47] 這樣就是可以的
[00:41:48] 可以啦
[00:41:49] 我們要求沒有到那麼高
[00:41:50] 畢竟是一門課
[00:41:51] 不是一個研究論文
[00:41:52] 然後說
[00:41:54] 我好想怎麼improve它
[00:41:56] 你能improve當然是更好啊
[00:41:58] 順便就當作是
[00:42:00] 你是研究生還是大學生
[00:42:02] 我是研究生
[00:42:03] 但是我的研究是
[00:42:04] 我是說
[00:42:05] 那你就要
[00:42:06] 你最好是想一個
[00:42:07] 你做出來之後
[00:42:08] 對你研究有幫助
[00:42:09] 會更好
[00:42:10] 你就不是為了修課的修課
[00:42:12] 你根本就是為了你的論文
[00:42:17] 對啊你這樣就是為了修課
[00:42:18] 所以你做一個跟你錄宏觀的
[00:42:20] 這樣比較不划算
[00:43:20] 好接下來呢
[00:53:20] 我們要開始第三章
[00:53:22] OK
[00:53:23] 我們先從一個
[00:53:25] 最簡單廣
[00:53:27] 來講說
[00:53:31] 我們如果利用search
[00:53:33] 我們把解決問一個
[00:53:41] 所以第三章呢
[00:53:42] 講的是solving problems by searching
[00:53:45] OK
[00:53:47] 沿襲我們之前所說的
[00:53:49] 這個goal based agent
[00:53:51] 角色呢
[00:53:52] 我們現在先不管後面更
[00:53:54] 所謂的utility based
[00:53:56] 或者是learning agent
[00:53:58] 我們先回到goal based agent這邊
[00:54:02] goal based agent呢
[00:54:04] 他考慮的是說
[00:54:05] 我今天收到一些訊息之後
[00:54:07] 我要做一些決策
[00:54:09] 然後看是不是能夠
[00:54:10] 離我的目標比較接近
[00:54:13] 那我們來考慮
[00:54:16] 我們考慮其中一種
[00:54:18] goal based agent的方式
[00:54:20] 這個叫做problem solving agent
[00:54:23] 那在這一章裡面呢
[00:54:24] 我們把我們的討論呢
[00:54:26] 侷限在最簡單的PEAS
[00:54:32] 其中呢
[00:54:33] 它的solution
[00:54:35] 都可以當成是一連串動作
[00:54:39] A sequence of action
[00:54:41] 或者是action sequence
[00:54:43] 我們的解答就是一連串的動作
[00:54:46] 這一類的問題
[00:54:48] 那我們呢
[00:54:52] 這一連串的動作呢
[00:54:54] 我們去找一連串的動作
[00:54:56] 來完成我們的目標
[00:54:59] 這件事情呢
[00:55:00] 我們稱呼它叫做search
[00:55:02] 我們要去搜尋出一連串的動作
[00:55:05] 來達到我們的目標
[00:55:07] 那我們的一個解答呢
[00:55:08] 其實就是
[00:55:09] 這一連串動作裡面的
[00:55:10] 某一串動作
[00:55:13] 那它可能能夠讓我們
[00:55:16] 達到我們的目標這樣子
[00:55:19] 好
[00:55:20] 那我們舉個例子
[00:55:21] 講了半天
[00:55:22] 虛擬的
[00:55:23] 我們直接舉一個實際例子
[00:55:24] 就像這一個
[00:55:26] 這個是一個羅馬尼亞的地圖
[00:55:30] 那上面的每一個點呢
[00:55:32] 代表的是羅馬尼亞的一個都市
[00:55:35] 那剛好
[00:55:36] 為什麼舉這個例子
[00:55:37] 因為恰好呢
[00:55:39] 這個都市的名稱的開頭
[00:55:41] 剛好就是ABCDE一直到Z
[00:55:44] 幾乎啦
[00:55:45] 所以它故意舉一個這樣的例子
[00:55:47] 假設我們有一個羅馬尼亞的地圖
[00:55:50] 然後呢
[00:55:51] 有ABCDE到Z的城市
[00:55:54] 比如說有
[00:55:55] Arab這個都市啦
[00:55:57] 然後有什麼Sibiu的這個都市啦
[00:56:00] 什麼等等等等
[00:56:01] 那某一些都市之間呢
[00:56:03] 有道路相連
[00:56:06] 那假設呢
[00:56:07] 我們也知道說
[00:56:08] 比如說從Arab到Sibiu
[00:56:11] 中間是離140公里
[00:56:15] 比如說單位叫公里
[00:56:17] 好
[00:56:18] 我們現在的目標是
[00:56:19] 我們現在給一個任務
[00:56:21] 這個任務是呢
[00:56:22] 要你從A
[00:56:24] 走到B
[00:56:26] Arab走到Bucharest
[00:56:29] Bucharest其實是羅馬尼亞的首都
[00:56:32] 我們現在給你一個任務
[00:56:33] 要你由A走到B
[00:56:36] 那你走哪一個路
[00:56:38] 你路徑要怎麼走會最好呢
[00:56:41] 這個就是我們現在要解的問題
[00:56:44] 好那所以來定義一下這個問題啦
[00:56:47] 一開始呢
[00:56:48] 我人是在A這個都市
[00:56:52] 那我在A這個都市
[00:56:53] 我可以做的動作是什麼呢
[00:56:55] 就是我走去S這個都市
[00:56:57] 或走去T
[00:56:58] 或者走去Z
[00:56:59] 因為為什麼
[00:57:00] 因為你看
[00:57:01] 從A可以走出去的路
[00:57:03] 一個是Z嘛
[00:57:05] 一個是S嘛
[00:57:06] 一個是T嘛
[00:57:08] 對不對
[00:57:09] 它可以做的動作
[00:57:10] 就是這三個動作的其中一個
[00:57:12] 看你是要走去哪一個都市
[00:57:15] 那Transition Model的意思就是說
[00:57:17] 你做了
[00:57:18] 你選了某一個動作之後
[00:57:21] 你做了那個動作
[00:57:23] 你的狀態會怎麼變動
[00:57:26] 這個叫做Transition Model
[00:57:28] 那In this case
[00:57:30] 就是說我本來在A這個都市
[00:57:32] 我假設要走去Z這個都市的話呢
[00:57:35] 我造成的結果就是
[00:57:37] 我後來人會跑到Z這個都市
[00:57:40] 好所以這裡回顧一下
[00:57:42] 我們剛剛上一節課講的
[00:57:44] 這樣子的環境
[00:57:47] 是Deterministic還是Stochastic
[00:57:51] 是Deterministic
[00:57:52] 因為我們是假設說
[00:57:54] 一旦我們說要從A走到Z
[00:57:56] 我們的下一個狀態就是
[00:57:58] 我們真的會到Z
[00:57:59] 這是一定的
[00:58:00] 所以它是Deterministic
[00:58:02] 然後呢
[00:58:03] 有沒有抵達終點呢
[00:58:05] 那就看說
[00:58:06] 我經過多次的走訪之後
[00:58:10] 我是不是身處於
[00:58:13] Butcher Ranch的這個都市
[00:58:15] 如果是
[00:58:16] 基本上我就達到了我的目標了
[00:58:20] 那我們要定義一下
[00:58:22] 我這樣子走
[00:58:24] 我要花的
[00:58:25] 我的花費
[00:58:26] 我的Pass Cost
[00:58:28] 是什麼呢
[00:58:29] 就是我每一條路徑
[00:58:31] 每一條路徑上面
[00:58:34] 你走的里程
[00:58:35] 我希望我走的里程
[00:58:36] 是越小越好
[00:58:38] 也就是說我花的
[00:58:40] 油錢
[00:58:41] 或者我花的相同數目之下
[00:58:44] 我花的時間最短
[00:58:46] 這個叫我的Pass Cost
[00:58:48] 這樣子
[00:58:49] 那這個問題裡面的一個
[00:58:51] 這個問題裡面的Solution
[00:58:53] 它其實可能有很多Solution
[00:58:55] 對不對
[00:58:56] 我可以這樣子
[00:58:57] A走到Z
[00:58:58] 走到O
[00:58:59] 再走到S
[00:59:00] 走到F
[00:59:01] 再走到B
[00:59:02] 這是一個
[00:59:03] 這是一個Solution
[00:59:04] 我也可以
[00:59:05] A走到S
[00:59:06] 走到R
[00:59:07] 走到P
[00:59:08] 再走到B
[00:59:09] 這也是另外一個Solution
[00:59:10] 對不對
[00:59:11] 所以其實
[00:59:12] 這個問題有很多的Solution
[00:59:14] 任何的一個Solution
[00:59:16] 怎麼表達呢
[00:59:17] 其實就是一連串的Action
[00:59:20] 對不對
[00:59:21] 走到Z是一個Action
[00:59:23] 再走到O是一個Action
[00:59:25] 再走到S是一個Action
[00:59:27] 對不對
[00:59:28] 所以
[00:59:29] 一個任何的一個
[00:59:31] 解答
[00:59:32] 都可以用一連串的Action來表達
[00:59:36] OK
[00:59:37] 那這個就是
[00:59:38] 這個問題的整體的地方
[00:59:42] 好那
[00:59:43] 這是一個我們之後會用的例子
[00:59:46] 我們順便也介紹其他
[00:59:49] 在往後不只這一章
[00:59:51] 在往後其他Chapter
[00:59:52] 也可能會用到的例子
[00:59:54] 其中一個例子是這個
[00:59:55] 叫做A puzzle problem
[00:59:57] 大家可能都玩過
[00:59:59] 好
[01:00:00] 這是一個九公格
[01:00:01] 上面有八個八塊
[01:00:04] 編號12345678
[01:00:06] 八塊
[01:00:07] 好
[01:00:08] 那其中有一格呢
[01:00:09] 是空的
[01:00:11] 好
[01:00:12] 那這一個問題呢
[01:00:14] 就是我隨機的把
[01:00:16] 編號1到8的方塊
[01:00:18] 擺在九公格裡面
[01:00:20] 然後要你去移
[01:00:22] 移動這些方塊
[01:00:24] 使得最後呢
[01:00:26] 你的方塊的
[01:00:28] 這個擺放會長這樣
[01:00:31] 最左上角是這個空格
[01:00:33] 然後呢12345678
[01:00:35] 照這樣子排好
[01:00:37] OK
[01:00:38] 好這個就是
[01:00:40] 這個問題的狀態是這樣
[01:00:42] 所以呢
[01:00:43] 每一個狀態
[01:00:44] 就是任何一個
[01:00:46] 在九公格裡面有擺一個
[01:00:48] 擺八塊
[01:00:50] 這個木塊
[01:00:51] 每一個排
[01:00:53] 每一個盤面
[01:00:54] 都是一個狀態
[01:00:55] 好
[01:00:56] 那Initial state呢
[01:00:57] 就是看你隨機
[01:00:58] 從什麼樣子的狀態開始吧
[01:01:00] 你的Action是什麼
[01:01:02] 這個問題裡面的Action
[01:01:04] 就是
[01:01:06] 實際上我們是去移動
[01:01:08] 那個有數字編號的木塊嘛
[01:01:11] 對不對
[01:01:12] 但是這樣子
[01:01:13] 你有好幾塊都可以移呀
[01:01:14] 所以我們把問題稍微趕一下
[01:01:16] 我們把空格這個
[01:01:18] 也想成是一個方塊
[01:01:20] 所以我們把它想像成是
[01:01:22] 我有這個空格這方塊
[01:01:24] 我這空格可以往左移
[01:01:25] 往右移
[01:01:26] 往上移
[01:01:27] 往下移
[01:01:28] 比如說你這個空格
[01:01:29] 往上移
[01:01:30] 就等於是你二號
[01:01:31] 往下移的意思嘛
[01:01:32] 好
[01:01:33] 所以我們把它的Action呢
[01:01:34] 想像成就是
[01:01:35] 我的空格這一塊
[01:01:37] 是可以上下左右移的
[01:01:39] 這樣
[01:01:40] 那你的Transition Model就是
[01:01:42] 比如說你空格
[01:01:43] 如果往上移
[01:01:44] 你現在一個狀態
[01:01:45] 就是你二號
[01:01:46] 跑到中間來
[01:01:47] 空格跑到上面來嘛
[01:01:48] 所以這也是一個
[01:01:49] Deterministic的一個Environment
[01:01:51] Environment
[01:01:52] 好
[01:01:53] Goal Test呢
[01:01:54] Goal Test就是
[01:01:55] 看看最後的盤面
[01:01:56] 是不是長這樣嘛
[01:01:57] 對不對
[01:01:58] 好
[01:01:59] 那你的Pass Cost呢
[01:02:01] 你這樣子移來CVA去
[01:02:03] 你所需花的費用是什麼
[01:02:08] 我們把它定義成
[01:02:09] 你要移多少次
[01:02:11] 我希望你移越少次
[01:02:13] 你越快達到
[01:02:14] 右上角這個Goal State越好
[01:02:17] 所以這個就是這個定義
[01:02:21] 好
[01:02:22] 那你這個
[01:02:24] 我用這個
[01:02:25] 我用一個
[01:02:26] 我用這個
[01:02:27] 我用這個
[01:02:28] 我用這個
[01:02:29] 我用這個
[01:02:30] 我的意思是
[01:02:31] 我的意思是
[01:02:32] 如果你有帶
[01:02:33] 我用這個
[01:02:34] 有這個
[01:02:35] 你其實我用這個
[01:02:36] 你直接可以
[01:02:37] 他就是
[01:02:38] 他有一個
[01:02:39] 有一個
[01:02:39] 有一個
[01:02:40] 有一個
[01:02:41] 有一個
[01:02:42] 有一個
[01:02:43] 有一個
[01:02:44] 有一個
[01:02:45] 有一個
[01:02:46] 有一個
[01:02:48] 我有一個
[01:02:49] 我買了一個
[01:02:50] 夠小的
[01:02:51] 很便宜
[01:02:52] 挺便宜的
[01:02:53] 皇后這個旗子呢
[01:02:55] 它會攻擊
[01:02:57] 跟它同一列
[01:02:59] 跟同一行
[01:03:00] 還有跟它同一個對角線上面的
[01:03:02] 所有的其他的旗子
[01:03:05] OK 好
[01:03:06] 所謂的八皇后問題呢
[01:03:08] 就是說在一個這樣的盤面
[01:03:11] 12345678
[01:03:13] 在一個八乘八的一個旗盤上面呢
[01:03:16] 要你擺八隻皇后
[01:03:19] 使得你擺完之後的結果呢
[01:03:22] 皇后們不會互相攻擊
[01:03:25] 比如說像這個例子
[01:03:27] 這個例子呢
[01:03:28] 其實有沒有符合八皇后的
[01:03:30] 沒有呢
[01:03:31] 其實很快就知道沒有
[01:03:33] 這一個會打到這一個
[01:03:35] 因為這是同一個對角線
[01:03:37] 對不對
[01:03:38] 這個還好
[01:03:39] 這個會打這裡
[01:03:40] 也會打這裡
[01:03:41] 然後它所有的對角線
[01:03:42] 都沒有打到
[01:03:43] 這個OK
[01:03:44] 所以所謂的八皇后問題的目標就是
[01:03:47] 你這八隻皇后應該要怎麼擺
[01:03:50] 會讓我最後擺完
[01:03:52] 然後盤面上的八隻皇后不會互相攻擊
[01:03:55] 這個就是這個問題的定義
[01:03:57] 所以它的State是什麼
[01:03:59] 它的State就是一個盤面
[01:04:02] 你可能放0隻皇后到8隻皇后
[01:04:05] 你一開始是什麼
[01:04:06] 你一開始是一個空白的旗的一個盤
[01:04:09] 旗盤
[01:04:10] 然後你要一隻一隻皇后把它放上去
[01:04:13] 某一個位置這樣子
[01:04:16] 你的Action是什麼
[01:04:17] 你的Action就是你把皇后放到某一個位置
[01:04:19] 這就是你的Action
[01:04:22] 傳記序Model就是什麼
[01:04:24] 比如說你要放在22這個位置
[01:04:27] 你把它放上去之後呢
[01:04:29] 那接下來盤面就是22那個位置
[01:04:32] 位於一隻皇后
[01:04:33] 就這樣
[01:04:34] 這個就是你的傳記序Model
[01:04:36] 那你的目標就是說
[01:04:38] 有8隻皇后在盤面上
[01:04:40] 彼此不互相攻擊
[01:04:42] 所以我們這裡介紹了三個不同的例子
[01:04:49] 接下來
[01:04:50] 世上還有很多很多
[01:04:52] 這個實際實體世界當中
[01:04:55] 有很多很多各種不同的問題
[01:04:59] 那這些問題呢
[01:05:00] 其實很多是資工系的同學
[01:05:03] 你在大二修演算法的時候
[01:05:06] 你可能都有碰過的問題
[01:05:07] 比如說
[01:05:09] Traveling salesperson problem
[01:05:12] 或者說你現在在做電路設計的
[01:05:13] 你會有Layout problem
[01:05:16] 或者說你現在在做自駕車的
[01:05:18] 會有Robot Navigation problem
[01:05:20] 這些
[01:05:21] 廣義來講
[01:05:23] 都屬於
[01:05:24] 像要介紹的這些問題
[01:05:31] 來得更為複雜
[01:05:32] 當然我們上課
[01:05:33] 我們就先從最簡單的開始講起
[01:05:35] 但從像話來看
[01:05:37] 它要解的
[01:05:38] 它都是一種Problem solving的agent
[01:05:40] 你要建構出一個Problem solving agent
[01:05:44] 好吧
[01:05:45] 那我們就先從地圖這個問題開始
[01:05:47] 我們要如何找到一個解答呢
[01:05:49] 我們要從A走到B
[01:05:53] 在這個問題裡面呢
[01:05:54] 我們有一種做法是
[01:05:55] 我們把
[01:05:57] 這整個行走的過程
[01:05:59] 它可以走的Action
[01:06:01] 它可以做的Action
[01:06:02] 或者說
[01:06:03] 它可以走過去的都市
[01:06:04] 整體而言表達成一個Search Tree
[01:06:08] 表達成一棵樹
[01:06:11] 這棵樹的Root
[01:06:13] 出發點就是A這個都市
[01:06:17] OK
[01:06:18] 那簡單的我們知道嘛
[01:06:19] 你從A這個都市出發
[01:06:21] 你可以走到S
[01:06:22] 你可以走到T
[01:06:23] 你可以走到Z
[01:06:25] 那同樣的
[01:06:26] 你如果走到S的話呢
[01:06:28] 你可以走到
[01:06:29] 你可以走回A
[01:06:31] 或者走到F
[01:06:32] 或者走到O
[01:06:33] 或者走到R
[01:06:35] 依此類推
[01:06:36] 所以你是不是可以把
[01:06:38] 你要從A走到B的這整個的過程
[01:06:41] 你可以展開成一棵樹
[01:06:46] 對不對
[01:06:47] 你可以展開成一棵樹
[01:06:48] 那這些事情顯然的
[01:06:52] 很容易用來表達
[01:06:55] 剛剛羅馬尼亞地圖這個問題
[01:06:58] 那其實可能也可以用來表達
[01:07:01] 這個九宮格的這個問題啊
[01:07:03] 比如說
[01:07:04] 我今天在這個Tree裡面呢
[01:07:07] 某一個Node
[01:07:08] 代表的是某一個盤面的意思
[01:07:10] 這個Node的Parent
[01:07:14] 其實就是
[01:07:16] 能夠造成
[01:07:18] 這種盤面的上一個步驟
[01:07:21] 會造成這個盤面的
[01:07:28] 有可能是我前一個盤面呢
[01:07:30] 4號在最右上角
[01:07:32] 空白在這裡
[01:07:33] 或者說前一個盤面
[01:07:35] 就是8號在最右上角
[01:07:37] 空格在這裡
[01:07:38] 那它有可能造成
[01:07:40] 我現在這個Node長這樣
[01:07:42] 所以它的Parent
[01:07:43] 有兩種可能
[01:07:45] 那同樣它的Child呢
[01:07:47] 它的Child可以是
[01:07:49] 我從這個盤面
[01:07:50] 可以繼續往下變動的情況
[01:07:53] 所以它的State
[01:07:54] 就是代表一個盤面
[01:07:55] 它的Parent就是能夠造成
[01:07:57] 這個盤面的上一個動作
[01:08:00] 那它可以做的Action就是
[01:08:02] 我今天如果把這個空白
[01:08:04] 往下移
[01:08:05] 那就8號跑到最上面
[01:08:09] 如果往左移
[01:08:10] 就是4號馬來村右上角
[01:08:12] 空白跑到這裡
[01:08:14] 那PassCross的其實就是
[01:08:17] 你在這個Tree裡面行走
[01:08:20] 你多走一個分支
[01:08:22] 多走一次分支
[01:08:23] 就代表
[01:08:24] 我這個空格
[01:08:25] 多移動一次的意思
[01:08:27] 對不對
[01:08:28] 就好像說
[01:08:29] 剛剛這個
[01:08:30] 從A走到B的這個Tree
[01:08:32] 我多走一個分支
[01:08:33] 我就要付出
[01:08:35] 我的里程數
[01:08:37] 那就是我的PassCross
[01:08:42] 所以我們剛才有把問題
[01:08:44] 像這一類的問題
[01:08:46] 我們可以把它描述成
[01:08:48] 在一棵樹上面來找尋
[01:08:52] 剛剛講P.E.A.S
[01:08:54] 我們要如何去評某一個演算法
[01:08:58] 我們還沒有跟大家講
[01:08:59] 你可以用什麼演算法
[01:09:01] 但是我們先來定義一下
[01:09:03] 我們如何去評判一個演算法
[01:09:05] 有幾種不同的指標
[01:09:09] 第一個Completeness
[01:09:12] 它的意思是說
[01:09:14] 如果這個系統有解的話
[01:09:16] 如果這個問題是有Solution的話
[01:09:18] 它是不是一定能夠找到Solution
[01:09:21] 比如說
[01:09:27] 我從A走到B
[01:09:29] 可能我有很多種走法
[01:09:31] 對不對
[01:09:32] 我有好多種Solutions
[01:09:35] 那評判一個演算法的第一種指標
[01:09:38] 可能是說
[01:09:39] 如果它有Solution
[01:09:41] 你是不是一定就能夠找到Solution
[01:09:44] 當然也有一些問題是沒有Solution的
[01:09:47] 那種就目前暫時
[01:09:49] 不在我們的考慮
[01:09:51] 如果它有Solution
[01:09:52] 是不是一定能夠找到Solution
[01:09:54] 這個叫做Completeness
[01:09:57] 這叫Completeness
[01:09:58] 第二個
[01:10:00] 如果它可以找到
[01:10:02] 找到了是不是最佳的Solution
[01:10:06] 這個叫做Optimality
[01:10:11] 這個搜尋的策略
[01:10:13] 是不是能夠找到最好的解
[01:10:15] 第三個Complicity
[01:10:19] 實踐複雜度是怎麼樣
[01:10:23] 你要花多久的時間來找到
[01:10:26] 解答
[01:10:28] OK
[01:10:29] 那這邊當然就會跟電機資工的同學
[01:10:33] 你可能會比較熟悉
[01:10:35] Time Completeness
[01:10:36] 如果你不是電機資工的
[01:10:38] 可能你自己要補充一點背景知識
[01:10:42] 那再來就是Space Completeness
[01:10:44] 就是你的這個演算法的運作
[01:10:47] 你要花多少Memory
[01:10:50] 你可以從這幾個不同的角度
[01:10:52] 來去評判一個演算法
[01:10:54] 那我們先來講一種最簡單的
[01:10:57] 做法
[01:10:58] 叫做Uninformed Search
[01:11:00] 又稱呼是Blind Search
[01:11:03] 就是盲目的搜尋
[01:11:05] 有一大類的演算法
[01:11:07] 是這種所謂的盲目搜尋
[01:11:10] 這個的意思是說呢
[01:11:12] 這種策略是說
[01:11:13] 我除了告訴你原本問題的定義之外
[01:11:17] 比如說除了這個羅馬尼亞的地圖
[01:11:23] 我告訴你羅馬尼亞的地圖
[01:11:25] 然後ABCD到Z的都市的都市
[01:11:27] 以及它個別的道路的連結
[01:11:30] 還有道路連結上面的里程數
[01:11:34] 我除了告訴你這個之外
[01:11:35] 我其他全部不告訴你
[01:11:37] 那你就依賴我告訴你這些資訊
[01:11:40] 去找出如何從A找到B這樣子
[01:11:45] 這種叫做Uninformed Search的這個分類
[01:11:49] All they can do is to generate successors
[01:11:54] and distinguish a goal state
[01:11:56] from a non-goal state
[01:11:58] 他能夠做的事情就是說
[01:11:59] 我從某個地方出發
[01:12:00] 然後往外走
[01:12:02] 然後走過去之後呢
[01:12:03] 判斷一下說
[01:12:04] 這是我的目的地
[01:12:06] 就這樣
[01:12:07] 他只能夠做這件事
[01:12:09] 那不同的搜尋策略
[01:12:14] 它如何進行不同的分類
[01:12:17] 我如果去區分它呢
[01:12:18] 那就跟我今天是用什麼樣子的順序
[01:12:22] 來搜尋這一棵樹是有差的
[01:12:26] 那相對來講呢
[01:12:28] 如果說我知道的比
[01:12:33] 剛剛問題的定義更多的話
[01:12:36] 比如說我大概知道
[01:12:39] 往哪個方向走
[01:12:41] 可能會離B這個城市更接近的話
[01:12:45] 如果我額外多知道這個資訊的話
[01:12:47] 那它就屬於是Informed Search
[01:12:50] 或者是Heuristic Search的範圍
[01:12:52] 那這個我們等一下再講
[01:12:54] 我們先來講Informed Search
[01:12:56] 其中一個最有名的
[01:12:58] 應該大家大一大二也都學過的演算法
[01:13:02] 就是BFS
[01:13:04] Bread First Search
[01:13:06] 寬度
[01:13:08] 廣度
[01:13:10] 廣度優先的搜尋演算法
[01:13:13] 那它其實概念很簡單
[01:13:16] 就是說呢
[01:13:17] 我就先從A
[01:13:19] 我從A出發嘛
[01:13:20] 那我去走去B
[01:13:22] 走去S看看
[01:13:23] 是不是我的目的地
[01:13:25] 如果不是
[01:13:26] 那我再去看
[01:13:27] 從A這邊我走去T
[01:13:30] 是不是我的目的地
[01:13:31] 不是
[01:13:32] 那再回過來
[01:13:33] 我把A可以走出去的所有分子
[01:13:35] 都先走一次
[01:13:39] 都走一次
[01:13:40] 然後呢
[01:13:41] 都不是我的目的地嘛
[01:13:42] 那接下來
[01:13:43] 我剛剛的第一個分子是S
[01:13:46] 我再試試看
[01:13:47] 我從S走出去的所有分子
[01:13:49] 看看有沒有走到我的目的地
[01:13:51] 就這樣
[01:13:52] 依此類推
[01:13:53] 一路這樣子往下展開
[01:13:54] 所以底下這是另外一個示意圖
[01:13:56] 從A
[01:13:57] 先check一下B
[01:13:59] 是不是目標
[01:14:00] 不是
[01:14:01] 回來
[01:14:02] 再走C
[01:14:03] 是不是目的地
[01:14:04] 不是
[01:14:05] 回來
[01:14:06] 再從B繼續往下走
[01:14:07] 它的分子
[01:14:08] D是不是
[01:14:09] 不是
[01:14:10] E是不是
[01:14:11] 不是
[01:14:12] 那一路這樣子展開
[01:14:13] 所以它是屬於
[01:14:14] 廣度優先的搜尋策略
[01:14:18] OK
[01:14:19] 就這麼簡單
[01:14:20] 它就這麼運作了
[01:14:22] 那BFS呢
[01:14:23] 你可以想像
[01:14:24] 稍微分析一下
[01:14:26] 假設啊
[01:14:27] 在這個tree裡面
[01:14:29] 每一個node
[01:14:31] 都有B這麼多個successor
[01:14:34] 也就是說都有B這麼多個分子可以走
[01:14:36] 好
[01:14:37] 所以呢
[01:14:38] 因你從root出發
[01:14:40] 你就有
[01:14:41] 在你往下的第一層
[01:14:43] 你就有B這麼多個分子
[01:14:45] 那每一個分子
[01:14:47] 另外又有B這麼多個分子
[01:14:49] 所以在第二層
[01:14:50] 就會有B平方
[01:14:51] 這麼多個node
[01:14:53] 再往下一層
[01:14:54] 就會有B的三次方
[01:14:55] 這麼多個node
[01:14:56] 因此
[01:14:58] 假設
[01:14:59] 你要把整顆tree
[01:15:01] 假設這一顆tree
[01:15:02] 它的深度是D
[01:15:04] 也就是說有D這麼多層的話
[01:15:06] 你會展開出多少個node呢
[01:15:09] 就是B加上B平方
[01:15:11] 加B正方
[01:15:12] 加上B的D次方
[01:15:14] 對不對
[01:15:15] 好
[01:15:16] 那這個東西呢
[01:15:17] 就這個time complexity來講
[01:15:20] 它就是BIG OF B的D次方
[01:15:23] 好
[01:15:24] 那抱歉
[01:15:25] 如果說你沒有學過BIG OF的話
[01:15:27] 同學你可能要自己去查一下
[01:15:29] 我們假設你來修正門課
[01:15:32] 你其實是有這些幾個素養的
[01:15:35] 這其實是
[01:15:37] 子宮可能大二的時候
[01:15:39] 會介紹的對不對
[01:15:41] time complexity的一個說明
[01:15:45] 所以它其實它的time complexity
[01:15:48] 以及它的memory的需求其實很大的
[01:15:51] 這是BFS
[01:15:52] 好
[01:15:53] 那我們來看一下
[01:15:54] 這是一個範例
[01:15:55] 這個多大呢
[01:15:56] 有那麼嚴重嗎
[01:15:57] 假設今天
[01:15:58] 我平均每一個node都有十個分支
[01:16:04] 假設我走訪
[01:16:05] 我去check一個node
[01:16:06] 我去generate一個node
[01:16:08] 所需花的時間呢
[01:16:11] 是
[01:16:12] 假設我一秒鐘就可以check
[01:16:14] 一百萬個node好了
[01:16:16] 一秒鐘
[01:16:17] 好
[01:16:18] 那假設每個node呢
[01:16:20] 是1K
[01:16:23] 1千
[01:16:24] 對1K
[01:16:25] 好
[01:16:26] 1千個byte
[01:16:27] 好
[01:16:28] 那今天
[01:16:29] 你的這棵樹的深度
[01:16:31] 如果是兩層的話
[01:16:33] 你就為110個node
[01:16:35] 你要花0.11個minisecond
[01:16:37] 你要花107K kilobyte
[01:16:41] 如果你的深度變成十層
[01:16:43] 你就為十個十次方個node
[01:16:46] 你就要花三個小時
[01:16:49] 去generate這些node
[01:16:51] 你所需的memory就會十個terabyte
[01:16:53] 如果是十六層
[01:16:55] 你就要花三百五十年
[01:16:58] 去generate這些node
[01:17:00] 然後呢
[01:17:01] 你的memory是十個exabyte
[01:17:04] 所以事實上我們可以知道說
[01:17:06] 當你的這個tree的深度
[01:17:09] 增加的時候
[01:17:11] 你所需的時間跟所需的空間
[01:17:14] 會急劇的增加
[01:17:16] 這是BFS
[01:17:18] 好
[01:17:20] 好
[01:17:21] 那
[01:17:23] 另外一個聰明一點
[01:17:24] 一樣是
[01:17:25] Informed Search的一個策略
[01:17:27] 大家
[01:17:28] 可能有一些同學也都學過了
[01:17:31] 就叫做Dijkstra Algorithm
[01:17:34] 這個是在理論
[01:17:37] Theoretical Computer Science這個領域裡面
[01:17:39] 這個去稱呼它
[01:17:41] 在AI這個領域呢
[01:17:42] 其實因為當年幾十年前
[01:17:44] 大家其實都各自發展嘛
[01:17:45] 有時候
[01:17:46] 也搞不清楚別人已經提過同樣的東西了
[01:17:49] 在AI這個領域
[01:17:50] 當時提出來的時候
[01:17:51] 它叫做Uniform Cost Search
[01:17:54] 但其實它跟Dijkstra Algorithm
[01:17:56] 是一樣的意思
[01:17:58] 它的意思是說呢
[01:18:00] Uniform Cost Search
[01:18:01] expand the node n with the lowest pass cost g n
[01:18:07] 也就是說每次我在展開
[01:18:09] 我要決定我要往哪一個分子走的時候
[01:18:13] 像剛剛的BFS是
[01:18:15] 我管它的
[01:18:16] 我就每一個分子
[01:18:17] 我所有可以走的分子
[01:18:18] 我就走一遍嘛
[01:18:19] 對不對
[01:18:20] 好
[01:18:21] 那它現在有一個選擇性
[01:18:23] 它利用到
[01:18:25] 我走過去之後
[01:18:29] 需要花的里程這個資訊
[01:18:31] 因為這個也算是我一開始的問題
[01:18:35] 一開始問題在定義的時候
[01:18:36] 就已經有給過的資訊
[01:18:39] The algorithm tests for goals
[01:18:41] only when you expand a node
[01:18:43] not when you generate a node
[01:18:45] 好
[01:18:46] 所以這裡舉個例子
[01:18:47] 假設我現在已經走到S了
[01:18:49] 我接下來可以走到R也可以走到F
[01:18:52] 那我走到
[01:18:53] 走去哪裡呢
[01:18:54] 那我們看一下吧
[01:18:55] 我如果走到R
[01:18:57] 我如果去走到R
[01:19:03] 我會花80
[01:19:06] 那你從R再繼續往下走
[01:19:09] 你如果真的expand的時候
[01:19:11] 你expand
[01:19:13] 你真的走過來的
[01:19:15] 你真的走過來
[01:19:16] 那接下來呢
[01:19:18] 你去check一下
[01:19:20] 這是我的目標
[01:19:21] 不是R
[01:19:22] 這個都是不是我的目標
[01:19:23] 我的目標是
[01:19:24] ButcherRest這個嘛
[01:19:26] 所以呢
[01:19:27] 我走來這裡了
[01:19:29] 我花了80
[01:19:30] 然後呢
[01:19:31] 我去Generate
[01:19:33] 它可以走出去的分支
[01:19:36] 它走出去的分支就P嘛
[01:19:39] 那P的話呢
[01:19:41] 其實我已經知道說
[01:19:42] 我如果是走P
[01:19:43] 我如果走P這條路
[01:19:45] 我要再加97
[01:19:47] 這麼多個cost
[01:19:48] 所以我就知道了
[01:19:50] 我走到這裡來呢
[01:19:52] 我的cost已經知道
[01:19:54] 就會是80加97啦
[01:19:57] 好
[01:19:58] 那接下來
[01:20:00] 我現在如果是走這一條的話
[01:20:02] 我會需要花177的cost
[01:20:05] 那接下來我看一下
[01:20:06] 另外一個分支
[01:20:08] 我另外這個分支
[01:20:09] 這裡只要99耶
[01:20:11] 那我走過來看看
[01:20:13] 那我走過來了
[01:20:14] 但是因為這個過來之後呢
[01:20:17] 它接下來也只有一條路
[01:20:19] 這一條路我Generate出來是211
[01:20:21] 那我就知道說
[01:20:22] 99加21
[01:20:23] 所以其實我如果走這一條路啊
[01:20:25] 我要刷3110
[01:20:27] 那我就相較之下
[01:20:32] 那我就知道說
[01:20:33] 其實這個也不是那麼好
[01:20:35] 所以我就回過頭來走這個1
[01:20:38] 然後expand到P
[01:20:40] 然後呢再Generate到101
[01:20:43] 那怎麼加起來呢
[01:20:44] 是278
[01:20:45] 所以相較之下呢
[01:20:47] 這個278
[01:20:49] 是一個比較好的一個路徑
[01:20:52] 所以它到現在
[01:20:55] 這個Gystra Algorithm呢
[01:20:56] 它就是一個
[01:20:58] 有利用到你的Cost
[01:21:02] 有考慮到Pass Cost的一個演算法
[01:21:05] 這樣
[01:21:06] 好
[01:21:07] 所以這裡要釐清一個點
[01:21:08] 就是說Uninformed
[01:21:10] 你看字面上的意義
[01:21:11] Uninformed的意思就是說
[01:21:13] 沒有被通知
[01:21:15] 沒有被告知的意思
[01:21:17] 所以這裡Uninformed的意思
[01:21:19] 不是說完全沒有任何資訊
[01:21:22] 它不是這個意思
[01:21:24] 就是說它沒有用到任何
[01:21:26] 關於目標有多元的額外資訊
[01:21:31] 好
[01:21:32] 好
[01:21:33] 那所以說呢這個Uniform Search
[01:21:37] 基本上呢
[01:21:38] It's optimal in general
[01:21:40] 什麼意思
[01:21:41] 回到剛剛我們講
[01:21:42] 評判一個演算法好不好
[01:21:43] 就是說
[01:21:44] 你如果可以找到解的話
[01:21:46] 你找到的是不是最佳解
[01:21:48] 好
[01:21:49] 他說呢這個Uniform Cost Search呢
[01:21:51] 基本上
[01:21:52] 可以找到最佳解
[01:21:54] 其實BFS也可以找最佳解啦
[01:21:57] 你去全部都掃一遍
[01:21:59] 然後找到Cost的最低那個
[01:22:01] 就是你的最佳解
[01:22:02] 好
[01:22:03] 那Uniform Cost Search呢
[01:22:06] Expand node in order of their optimal Pass Cost
[01:22:10] 不過它在Expand node的時候
[01:22:12] 是有稍微聰明一點
[01:22:14] 稍微聰明一點
[01:22:16] 那他說呢它是Guided by Pass Cost
[01:22:19] Relative Depth
[01:22:20] 所以你在展開的時候啊
[01:22:23] 是根據你走到目前這邊為止
[01:22:27] 你所需花的Cost
[01:22:29] 來進行展開的確定
[01:22:33] 跟BFS不一樣
[01:22:34] BFS是
[01:22:36] 我就先展開第一層
[01:22:38] 再來展開第二層
[01:22:40] 再來展開第三層
[01:22:42] 所以它是Order by Depth
[01:22:44] BFS是Order by Depth
[01:22:46] 然後呢Uniform Cost Search
[01:22:48] 是Order by Pass Cost
[01:22:52] OK
[01:22:54] 這是最主要的一個差別
[01:22:56] 那到時候步驟
[01:22:58] 如果假設今天
[01:23:00] 你不管走哪一個分支
[01:23:02] 你的Cost都一模一樣的時候呢
[01:23:04] 其實Uniform Cost Search呢
[01:23:06] 就類似像是BFS一樣
[01:23:09] 這當然這是一個特例
[01:23:13] 好
[01:23:14] 那所以大家也算有學過BFS
[01:23:17] 廣度優先的搜尋
[01:23:19] 那你也學過DFS啊
[01:23:21] 深度優先的搜尋
[01:23:23] 我想很多人也都知道了
[01:23:25] 那就是說呢
[01:23:26] 我一條路走到黑
[01:23:30] 我第一從Root出發
[01:23:32] 我展開第一層
[01:23:34] 那接下來呢
[01:23:35] 第一層的第一個Node
[01:23:36] 我再展開它的分支
[01:23:39] 的第一個分支
[01:23:41] 然後呢
[01:23:42] 我再走第一個分支的
[01:23:44] 第一個分支的第一個分支
[01:23:45] 一路我把走到最深層為止
[01:23:49] 如果走到Edge這裡
[01:23:51] 不是我的目的地
[01:23:53] 那我就回過頭來到上一層
[01:23:55] 再走上一層的
[01:23:57] 另外一個分支
[01:23:58] 看一下I
[01:23:59] I也不是我的目的地
[01:24:00] 那我再回到上面的D
[01:24:02] 再回到上面的B
[01:24:04] 然後再去展開這個E
[01:24:06] 然後依此類推
[01:24:07] E再往下展開
[01:24:09] 然後呢
[01:24:10] K再展開
[01:24:12] 依此類推
[01:24:13] 這叫深度優先的搜尋
[01:24:17] 那DFS呢
[01:24:20] 它的Time Complexity呢
[01:24:23] 是Bounded by the Size of
[01:24:25] State Space
[01:24:30] In general may generate all of the
[01:24:32] big ol' B的M字吧
[01:24:34] 其中M呢是Mesmer Depth
[01:24:38] M呢
[01:24:39] 對
[01:24:40] 就是說假設今天
[01:24:42] 你每一個Node
[01:24:44] 都有B這麼多個分支
[01:24:48] 然後假設你的深度
[01:24:51] 是
[01:24:52] 深度是
[01:24:56] 最深的那個
[01:24:59] 最深的那個層數
[01:25:04] 比如說
[01:25:05] 我今天這個數可能長得歪歪的
[01:25:07] 雖然我們這裡的數
[01:25:08] 看起來都好像是左右非常的平衡
[01:25:11] 但是其實有可能是
[01:25:13] 左邊這個數啊
[01:25:14] 一路往下長
[01:25:15] 長十層
[01:25:16] 然後右邊這個分支的數
[01:25:18] 可能只長三層
[01:25:20] 所以呢
[01:25:21] 這裡的M指的是
[01:25:23] 最深的那一層的深度
[01:25:26] 這樣
[01:25:27] 在最糟的情況之下呢
[01:25:29] DFS呢
[01:25:30] 有可能會生出
[01:25:31] big ol' B的M字吧
[01:25:36] 其中呢
[01:25:37] M可能遠大過於D
[01:25:40] D指的是
[01:25:41] The Depth of the Shadowless Solution
[01:25:43] 你說不定啊
[01:25:44] 你真正的正解
[01:25:46] 是在右邊的那個指數的一個比較淺的地方
[01:25:50] 就已經是你的解了
[01:25:52] 可是你
[01:25:53] 如果你是深度優先的展開的話
[01:25:56] 你會花很多的時間
[01:25:58] 去展開左邊很深的數
[01:26:01] 好
[01:26:03] 然後
[01:26:04] 殊不知
[01:26:05] 展開完之後
[01:26:08] 這個根本就是
[01:26:11] 你真正要的解答
[01:26:13] 其實就是在
[01:26:14] 右邊的這個指數的一個很淺的地方就有了
[01:26:18] OK
[01:26:20] 那
[01:26:21] 這個就是最糟的情況
[01:26:23] 這DFS
[01:26:25] 但是DFS的
[01:26:27] 優點是說
[01:26:28] 它的Space Complexity
[01:26:31] 是比較低的
[01:26:32] 比如說
[01:26:33] 它只需要儲存
[01:26:34] 它目前展開維持的
[01:26:36] 這一條路徑上面的這些Node就好了
[01:26:40] 其他都不用記
[01:26:42] 其他都不用記
[01:26:44] 當然要記一下
[01:26:45] 我目前展開的最深的這個
[01:26:47] 它的兄弟的Node是誰吧
[01:26:51] 所以它的Space Complexity是
[01:26:53] 遠低於BFS的
[01:26:55] 我們剛剛說過說
[01:26:57] 那個廣度優先的搜尋
[01:26:59] 又花時間又花Memory
[01:27:01] 那DFS呢
[01:27:03] 至少不太花Memory
[01:27:04] 因為你光看這個
[01:27:05] 其實它在展開左邊的指數到最深的時候
[01:27:09] 它只需要記錄下這個啦
[01:27:11] A B D I
[01:27:13] 還有這個E
[01:27:15] 這裡而已啊
[01:27:17] 右邊的這個
[01:27:18] 這個這裡都不需要記啊
[01:27:20] 這裡都不需要記
[01:27:22] 那反正這個如果不是我的目標
[01:27:24] 我就回過頭來
[01:27:26] 我只要
[01:27:27] 這都丟掉了嘛
[01:27:28] 這反正不是我的目的地嘛
[01:27:30] 所以它一次只要處理一個Pack
[01:27:33] 幾乎是一個Path
[01:27:35] 上面的Node就好
[01:27:37] 我只要記這些就好
[01:27:39] 這是DFS的優勢
[01:27:42] 所以理論上來講呢
[01:27:44] State Space
[01:27:46] 它的Branch是B
[01:27:48] 然後呢它最高深度是M的話呢
[01:27:50] 它大約只需要儲存
[01:27:52] Big O BxM
[01:27:57] 所以它所需的Memory是小很多的
[01:28:00] OK
[01:28:01] 好
[01:28:02] 這個理論上大家應該都學過了
[01:28:04] 都應該學過了
[01:28:06] 好那當然我們知道啦
[01:28:08] 這個DFS呢
[01:28:09] 它有它的缺點嘛
[01:28:10] 如果說今天要是很衰
[01:28:12] 我左邊的指數很深
[01:28:15] 那但是我根本我的解答
[01:28:17] 就在右邊指數的很淺的地方
[01:28:19] 那就很衰嘛
[01:28:20] 我花那麼多時間在展開左邊指數
[01:28:24] 那所以要如何取得一個平衡呢
[01:28:27] 有一種做法叫做
[01:28:29] Depth Limit Search
[01:28:32] Depth Limit Search
[01:28:34] 意思是說
[01:28:42] 你是跑DFS沒有錯
[01:28:44] 但是呢你給它一個限制
[01:28:48] 你往下搜尋
[01:28:50] 你最多就搜尋L這麼多層
[01:28:54] 你在左邊指數你搜尋最深到L這麼多層
[01:28:58] 搜尋不到你就要回來了
[01:29:00] 你要去看一下右邊的指數
[01:29:03] 這樣大家懂我意思嗎
[01:29:05] 其實這樣子的邏輯
[01:29:07] 我剛剛突然想到
[01:29:09] 這到現在這個邏輯
[01:29:12] 一樣是通的喔
[01:29:14] 我們現在不是你跑過
[01:29:16] 那個GPD-6 ASTRON沒有
[01:29:19] 他幫你做一些工作嘛對不對
[01:29:22] 所以你假設你今天交付給他一個工作
[01:29:25] 這個工作可能有幾種方法可以完成
[01:29:31] 但是哪一種方法可以完成他不知道
[01:29:33] 好有三種方法可以完成
[01:29:36] 如果今天他是用類似
[01:29:38] 比如說第一個方法
[01:29:41] 又可以拆開成三種不同的策略或子方法
[01:29:47] 那每一個子方法又有三種不同的input方式對不對
[01:29:51] 然後呢每一個input方式又有三種不同的參數設定
[01:29:55] 所以你看你想像一下
[01:29:58] even到今天你在跑GPD-6 ASTRON
[01:30:03] 你叫他做代理
[01:30:05] 他如果是笨笨的
[01:30:07] 一路都把
[01:30:09] 第一個方法裡面的
[01:30:11] 第一種input方式裡面的
[01:30:13] 第一種參數設定完再怎麼樣
[01:30:16] 都弄完了
[01:30:18] 然後再回過頭來看一下第二個方法
[01:30:20] DFS的話
[01:30:22] 我相信你們應該很快就會覺得說
[01:30:25] 他怎麼跑那麼久
[01:30:27] 所以我相信呢
[01:30:28] 當然我不知道他是怎麼做的
[01:30:30] 但是他們一定有某些策略是讓
[01:30:33] 有效尤其在之前比較早期
[01:30:37] 在我們A群
[01:30:38] 會產生鬼搭牆
[01:30:40] 一直跑步不斷的
[01:30:42] 在那邊繞
[01:30:43] 然後走進一個死胡桃
[01:30:44] 所以這裡就有點類似像這樣
[01:30:48] 你可以做所謂的Depth Limit Search
[01:30:51] 你讓他深度最多
[01:30:53] 你要求他最多就是走到L位置
[01:30:57] 那你也許可以避免掉
[01:31:00] 那麼衰
[01:31:01] 花很多時間在
[01:31:03] 處理左邊的某一個指數
[01:31:06] 明明答案就在右邊的一個比較淺的地方
[01:31:11] 但是這裡有另外一個問題
[01:31:13] 那說不定我真正的答案
[01:31:15] 就是在左邊指數很深的地方
[01:31:18] 對不對
[01:31:19] 所以你如果只限定他說
[01:31:21] 我的深度最多可以到L
[01:31:23] 那他可能就找不到解了
[01:31:26] 所以如果是Depth Limit Search
[01:31:29] 他就是Incomplete
[01:31:31] Complete的定義就是說
[01:31:34] 如果這個問題有解的話
[01:31:36] 你一定可以找得到解
[01:31:39] 那如果你設定了一個
[01:31:41] Upper bound L的話
[01:31:43] 那有可能找不到解
[01:31:45] 然後你找到的解
[01:31:46] 也有可能不是最佳解
[01:31:49] 那他說有的時候
[01:31:52] 這個Depth Limit的演算法
[01:31:55] 其實如果你對於這個問題
[01:31:58] 你有一個整體的
[01:32:00] Extra的Prior Knowledge的話
[01:32:03] 有一些事前的領域知識的話
[01:32:07] 其實搭配起來
[01:32:10] 可能是可以更有效率來解決你的問題的
[01:32:12] 比如說
[01:32:13] 在這個羅馬尼亞的地圖裡面
[01:32:16] Somehow你知道說
[01:32:19] 從任何某一個都市走到另外一個都市
[01:32:22] 絕對不會走超過9條
[01:32:25] 不同的
[01:32:26] 超過9步
[01:32:28] 那你如果是這樣的話
[01:32:30] 你就可以把你的深度的限制設定成9
[01:32:35] 因為你最多不可能走超過9步
[01:32:41] 如果你有這個知識的話
[01:32:43] 你就可以設定這個L
[01:32:44] 那既然L
[01:32:49] 你設定了一個L
[01:32:51] 你怎麼知道這個L要怎麼設定呢
[01:32:53] 除非你有這個知識
[01:32:55] 那你如果沒有這個事先的領域知識的話
[01:32:58] 有另外一種策略叫做
[01:33:00] Iterative Depth DFS
[01:33:02] 那就是我逐步的增加我的深度
[01:33:06] 所以一開始我允許你展開一層
[01:33:12] DFS做一層
[01:33:14] 最多
[01:33:15] 往下深入一層
[01:33:17] 如果都沒有找到解答
[01:33:19] 那我就允許你最多深入兩層
[01:33:23] 再沒有找到答案
[01:33:24] 我最多允許深入三層
[01:33:27] 一步一步的增加我的那個Libid L
[01:33:31] 逐步的增加那個L
[01:33:33] 這樣
[01:33:35] 好
[01:33:36] 那如果是這樣子的話呢
[01:33:38] 它其實這種做法呢
[01:33:40] 就有點混合了DFS跟BFS的好處
[01:33:45] 那比如說就像DFS
[01:33:47] 它的Memory Requirement是低的啊
[01:33:51] 所需的Memory是低的啊
[01:33:53] 那就好像BFS
[01:33:54] 它在限定之內
[01:33:56] 它真的是把所有可能的狀況都掌握了啊
[01:34:01] 好
[01:34:02] The branch factors is finite and optimal
[01:34:05] when pass cost is a non-decreasing function of depth
[01:34:08] 當然你的pass cost是
[01:34:10] 你多走一步你的cost就會增加
[01:34:12] 它是一個non-decreasing
[01:34:14] 就是不會多走一步
[01:34:16] 你的cost不會降低
[01:34:17] 一定是往上增加的
[01:34:18] 這叫non-decreasing
[01:34:20] 好
[01:34:21] 好所以這個概念就像這樣啊
[01:34:23] 我允許你一開始呢
[01:34:25] 我的深度限制是1
[01:34:27] 那你就是一次
[01:34:28] 你一定就是展開一層
[01:34:30] 沒找到答案
[01:34:32] 我讓你深度限制是2
[01:34:35] 沒找到答案
[01:34:36] 我讓你深度限制是3
[01:34:38] 這樣
[01:34:39] 一步一步的放鬆我的管制
[01:34:43] 直到你找到你的答案為止
[01:34:45] 這樣子
[01:34:46] 好
[01:34:47] 可是你聽到這裡
[01:34:49] 有沒有覺得
[01:34:50] 這樣好嗎
[01:34:52] 你不會覺得說這樣子好像
[01:34:55] 浪費了很多
[01:34:57] 有些地方好像重複的去展開啦
[01:35:01] 比如說你看啊
[01:35:02] 我假設允許
[01:35:04] 你的深度最多到三層
[01:35:08] 你看啊
[01:35:09] 在展開到第三層之前
[01:35:11] 這裡
[01:35:12] 四層相似
[01:35:16] 這裡不是剛剛這裡有做過嗎
[01:35:18] 包括這裡有做過嗎
[01:35:20] 所以你會覺得說
[01:35:22] 當你把你的limit提升到三層的時候
[01:35:25] 感覺從這裡到這裡的這個動作
[01:35:28] 這裡到這裡的動作
[01:35:30] 剛剛這裡有做過啊
[01:35:32] 那我不就浪費了很多的時間
[01:35:35] 我浪費時間在重複做同樣的動作
[01:35:37] 會有這種感覺
[01:35:39] 的確
[01:35:40] 直觀上你會有這種感覺
[01:35:42] 但他這裡告訴你
[01:35:43] 對的確是有一點浪費
[01:35:46] 但是沒有到你想像中的那麼浪費
[01:35:49] 好
[01:35:50] It turns out this is not too costly
[01:35:53] 為什麼呢
[01:35:54] 因為啊
[01:35:55] 這個樹呢
[01:35:57] 他大部分的node
[01:35:59] 甚至超過一半以上的node
[01:36:03] 其實都是在
[01:36:05] 你展開的最深的那一層
[01:36:08] 這裡
[01:36:11] 也就是說
[01:36:12] 雖然你今天你的limit從二
[01:36:15] 提升到三
[01:36:17] 可是你如果仔細看一下
[01:36:19] 你limit如果是二
[01:36:20] 你這裡展開的node分別幾個
[01:36:21] 一二三四五六
[01:36:22] 如果不算 root的話
[01:36:24] 就六個嘛
[01:36:25] 可是你如果今天展開到三層
[01:36:28] 你看三層的最底端
[01:36:30] 就有一二三四五六七八
[01:36:33] 光這裡就有八個node耶
[01:36:35] 所以呢
[01:36:37] 你不要那麼在意
[01:36:39] 三層以前的
[01:36:43] 這裡一二三四五六
[01:36:45] 這才六個node
[01:36:48] 對
[01:36:49] 你可以說
[01:36:50] 欸那我第二層
[01:36:51] 第一層到第二層的
[01:36:53] 這六個node
[01:36:54] 我是又重複展開一次啦
[01:36:56] 對不對
[01:36:57] 對這部分的確是有一點浪費
[01:37:00] 但他的浪費沒有浪費到你
[01:37:02] 你覺得超浪費耶
[01:37:05] 我在講什麼
[01:37:06] 因為為什麼
[01:37:07] 原因就在於說
[01:37:08] 你越
[01:37:09] 如果你這個tree越深
[01:37:11] 你最底層的
[01:37:13] 最細的最底層的這些node的數量
[01:37:17] 一下子就會遠遠超過
[01:37:19] 往上一層的所有的總和
[01:37:22] in this case
[01:37:23] 他就是超過的嘛
[01:37:24] 像這個就已經是包含了
[01:37:26] 一二三四五六七八
[01:37:28] 八個node
[01:37:29] 而
[01:37:31] 第二層加第一層的
[01:37:32] 總共展開的node也才六個
[01:37:35] 這件事情在你深入越深的時候
[01:37:38] 那個差距會越大
[01:37:40] 所以
[01:37:41] 的確有點浪費
[01:37:42] 但沒有浪費到
[01:37:44] 你想像中
[01:37:45] 你直覺想的
[01:37:46] 那麼誇張
[01:37:48] 這個就是所謂的
[01:37:49] Iterative Dimple DFS
[01:37:56] 那我們把這部分講完
[01:37:58] 我們再講下一個
[01:38:00] 再休息
[01:38:01] 好啦
[01:38:02] 那所以呢
[01:38:03] 我們剛剛前面講過BFS跟DFS
[01:38:06] 對不對
[01:38:07] 好
[01:38:08] 那聰明的人就想說
[01:38:09] 那我要
[01:38:10] 我其實在搜尋的時候
[01:38:12] 我當然目標就是說
[01:38:14] 最好是
[01:38:15] 越快找到答案越好
[01:38:18] 那我所說的
[01:38:19] 我需要的
[01:38:20] 記憶體能夠越少越好
[01:38:22] 好那所以呢
[01:38:23] 就有人想說
[01:38:24] 欸
[01:38:25] 反正我從一個地方出發
[01:38:28] 我要走到我的目標也
[01:38:30] 如果只有一個的話
[01:38:32] 我可不可以把目標
[01:38:34] 也當成是一個出發點
[01:38:36] 對不對
[01:38:37] 我從A要走到B嘛
[01:38:40] 我從A出發一路這樣展開
[01:38:43] 然後呢我也從B這個地方出發
[01:38:45] 一路往回推
[01:38:47] 欸要是走走走走走走到中間
[01:38:49] 某一個地方
[01:38:50] 剛好交匯到了
[01:38:51] 我就把它整個串起來
[01:38:53] 好不好
[01:38:58] 對不對
[01:38:59] 這就好像說這個
[01:39:00] 我們在蓋那個血稅的時候
[01:39:02] 臺北到宜蘭血稅的時候
[01:39:04] 當時蓋啦
[01:39:05] 是兩端同時
[01:39:08] 兩端同時
[01:39:09] 從宜蘭往臺北方向
[01:39:10] 臺北往宜蘭方向
[01:39:11] 兩端同時蓋
[01:39:12] 然後最後接起來這樣子
[01:39:15] 欸
[01:39:16] 對嘛
[01:39:17] 這個現實
[01:39:18] 這個概念上是這樣沒有錯
[01:39:20] 你可以從start
[01:39:21] 出發點
[01:39:22] 一路往外展開
[01:39:23] 然後呢
[01:39:24] 目的地一路往外展開
[01:39:27] 那在完美的情況下呢
[01:39:29] 概念上呢
[01:39:30] 你可能只需要
[01:39:32] 展開
[01:39:34] Big O B的二分之D次方
[01:39:36] D是指深度
[01:39:39] 那你有兩個Big O二的
[01:39:41] 二分之D次方
[01:39:42] 其實就是Big O
[01:39:45] B的二分之D次方
[01:39:48] 這個數值呢
[01:39:49] 遠遠小於B的D次方
[01:39:54] 這個叫Bidirectional Search
[01:39:56] 雙向的搜尋
[01:39:58] 那Bidirectional Search
[01:39:59] Is implemented by
[01:40:00] repressing the goal test
[01:40:01] with the check
[01:40:02] to see whether
[01:40:03] the frontier of two search
[01:40:05] interact
[01:40:06] intercept
[01:40:08] 它不是在找說
[01:40:09] 欸
[01:40:10] 我是不是已經抵達
[01:40:11] 某一個目的地了
[01:40:12] 它反而是在確認說
[01:40:13] 欸
[01:40:14] 我兩條支線
[01:40:16] 有沒有交匯
[01:40:18] 有沒有交匯
[01:40:19] 如果有交匯
[01:40:20] 那我就找到一個解答了
[01:40:22] 那這裡面呢
[01:40:25] 真的要做到這件事
[01:40:27] 其實並不容易啊
[01:40:28] 因為你從
[01:40:30] 你的目的地出發
[01:40:32] 往回找這件事情
[01:40:34] 不見得容易
[01:40:36] 好 不見得容易
[01:40:37] 以這個地圖來講
[01:40:40] 相對是容易的
[01:40:43] 因為
[01:40:44] 你就看著那個地圖嘛
[01:40:45] 對不對
[01:40:46] 你從B這個城市出發
[01:40:48] 你往外可以走哪裡
[01:40:50] 是很明確的
[01:40:51] OK
[01:40:52] 所以你如果以
[01:40:53] 羅馬尼亞的這個問題來講
[01:40:55] 你可以用白的Rational Search
[01:40:57] 好
[01:40:58] 可是呢
[01:40:59] 你如果
[01:41:00] 然後你如果是從
[01:41:02] A puzzle problem
[01:41:04] 就是那個
[01:41:05] 從那個
[01:41:11] 九宮格的那個問題
[01:41:13] 也相對容易
[01:41:15] 你的目的地在哪裡
[01:41:16] 然後呢
[01:41:17] 一路你去移動你那個空格
[01:41:19] 好
[01:41:20] 所以往回找上一步是什麼
[01:41:22] 這是相對容易的
[01:41:23] 但是如果說
[01:41:25] 你的目標是一個
[01:41:26] 比較抽象的描述
[01:41:28] 比如說八皇後的問題
[01:41:30] 八皇後的問題是什麼
[01:41:31] 就是沒有任何一隻皇后
[01:41:33] 會攻擊其他皇后
[01:41:36] 你的目標組是這一種的話
[01:41:39] 那白的Rational Search
[01:41:41] 就很難implement
[01:41:43] 就很難說
[01:41:47] 某一個盤面的前一個動作
[01:41:50] 一定是怎麼樣
[01:41:52] 那這是白的Rational Search
[01:41:54] OK
[01:41:56] 好
[01:41:57] 那所以呢
[01:41:58] 第三章這裡呢
[01:41:59] 其實我們講完一半了
[01:42:01] 它主要就分兩個
[01:42:03] 兩大塊
[01:42:05] 一塊叫做On Informed Search
[01:42:08] 就是沒有額外知道
[01:42:10] 目標資訊的搜尋法
[01:42:13] 那下一個
[01:42:14] 下半部分我們要講的就是
[01:42:16] Informed Search
[01:42:17] 你如果知道
[01:42:19] 一些額外的資訊的話
[01:42:21] 你的找到解答的
[01:42:23] 這個效率會很高
[01:42:25] OK
[01:42:26] 好 講到這邊
[01:42:27] 有沒有什麼問題
[01:42:32] 我們看一下線上
[01:42:33] 請好好上課
[01:42:46] 這個我也
[01:42:48] 獨宗家族園可以嗎
[01:42:59] 只要不要超過四位
[01:43:01] 是可以的
[01:43:02] 我們過去也曾經遇到過
[01:43:04] 就是說
[01:43:05] 誒 本來比如說
[01:43:07] 三個人一組好了
[01:43:09] 後來
[01:43:11] 這個課修到一半的時候
[01:43:13] 撐不下去
[01:43:14] 退選了
[01:43:15] 落跑了
[01:43:17] 然後就只剩下一個人
[01:43:19] 自己一個人一組
[01:43:20] 那他就覺得他撐不住
[01:43:22] 他就問說
[01:43:23] 那我可不可以去救命其他組
[01:43:25] 這樣子
[01:43:26] 那如果你找得到
[01:43:27] 的話
[01:43:28] 是可以的
[01:43:29] 當然了前提是
[01:43:30] 另外那一組
[01:43:31] 還沒有滿四個人
[01:43:32] 反正不管怎麼樣
[01:43:34] 變來變去動來動去
[01:43:35] 就是最多四個人一組
[01:43:37] 好
[01:43:38] OK
[01:43:40] 還沒有其他問題
[01:43:41] 我的話我們休息一下
[01:43:47] 再回來
[01:43:48] 這對這個作業
[01:44:44] 有一點問題
[01:44:45] 因為就是
[01:44:46] 我感覺上整個作業
[01:44:47] 它就是有一點像
[01:44:48] 一個小小的論文這樣子
[01:44:50] 就找一個問題
[01:44:51] 然後你想一個解決方法
[01:44:54] 然後那個空空就是
[01:44:55] 因為可能一來就是有很多
[01:44:58] 就是通常我們想過的
[01:44:59] 別人也想過了
[01:45:00] 那我就好奇
[01:45:01] 就是這個解決方法
[01:45:02] 提出來過後
[01:45:03] 有一定要比別人表現好嗎
[01:45:05] 還是東西做出來就好了
[01:45:07] 在第一個作業
[01:45:08] 不用
[01:45:09] 第一個作業
[01:45:10] 只是push你們要去找資料
[01:45:12] 然後把它寫出來
[01:45:14] 我確定
[01:45:15] make sure你們有在找資料
[01:45:16] 有想過
[01:45:17] 就是開始看文獻這樣子
[01:45:18] 但最後是不是
[01:45:20] 嘗試提就是一個try
[01:45:23] 嘗試提自己的解法
[01:45:24] 或者什麼想法
[01:45:25] 但它不一定是要一個
[01:45:26] 最終的成品這樣子
[01:45:27] 對
[01:45:28] okok
[01:45:29] 那因為這個project是一個
[01:45:30] 我會把它理解的就是
[01:45:31] 你是為了後面的東西鋪路
[01:45:32] 所以你可以問就是
[01:45:33] 到最後的那個hw5的這個結果
[01:45:34] 是不是就是expect
[01:45:35] 最好就是自己的解法
[01:45:36] and then you review別人的解法
[01:45:37] 還是有一個新的解法
[01:45:38] 如果有比別人好
[01:45:39] 當然是更好
[01:45:40] 但是我知道
[01:45:41] 大部分同學是做不到
[01:45:42] okok
[01:45:43] 好
[01:45:44] 所以就是
[01:45:45] 就是盡可能就是
[01:45:46] 盡可能做到
[01:45:47] 好
[01:45:48] 好
[01:45:49] 好
[01:45:50] 好
[01:45:51] 好
[01:45:52] 好
[01:45:53] 好
[01:45:54] 就是有自己的想法
[01:45:55] 這才是那個重點
[01:45:56] 對
[01:45:57] okokok
[01:49:56] 好
[01:49:57] 我做的題目就是
[01:49:58] 想要跟路文有關
[01:49:59] 然後想要改成就是
[01:50:00] 根據
[01:50:01] 因為我路文是要做一個實驗設計
[01:50:03] 要發文卷的
[01:50:04] 然後我想說
[01:50:05] 如果我把LLM當作
[01:50:07] 我做實驗設計的前側
[01:50:10] 然後它可以符合
[01:50:12] 就是傳統理論上的那些
[01:50:15] 那些model fit
[01:50:17] 然後
[01:50:18] 但是因為前沿用LLM做這個啊
[01:50:21] 我目前查的都比較多是working paper
[01:50:23] 就沒有很棒的期刊
[01:50:26] 瞭解
[01:50:27] 很多知識
[01:50:28] 那如果只是用來這樣子
[01:50:30] 做測試的看看
[01:50:33] 然後做這個作業的話
[01:50:35] 做這個作業
[01:50:36] 那就是看你後面
[01:50:38] 你只是當前側吧
[01:50:40] 對
[01:50:41] 然後我想說看後面
[01:50:43] 如果
[01:50:44] 因為我如果真的
[01:50:45] 要花錢去做這件事情
[01:50:47] 就是實驗那種
[01:50:49] 跟經典外的
[01:50:50] 我怕收回來的數據會
[01:50:52] 到時候
[01:50:54] 收回來的數據不漂亮
[01:50:55] 如果這樣子聽起來就比較像是
[01:50:57] 你只是在用LLM
[01:50:59] 做事情而已
[01:51:00] 對
[01:51:01] 那除非
[01:51:02] 覺得它假裝人
[01:51:03] 你有帶入一些agent的設計
[01:51:07] 你有帶入
[01:51:08] 比如說
[01:51:09] 你可以去看一下
[01:51:10] 以現在LLM來當agent來講的話
[01:51:13] 比如說你要求他要反思
[01:51:16] 要能夠檢驗
[01:51:19] 人家回答的
[01:51:21] 然後再進一步的
[01:51:23] 提出
[01:51:25] 策略
[01:51:26] 然後再做動作
[01:51:27] 如果你有這樣子的
[01:51:29] 設計的話
[01:51:30] 就不會淪為
[01:51:31] 好像只是在用一個工具
[01:51:34] 這樣會比較符合
[01:51:36] 我們這門課
[01:51:38] 希望你們真的有
[01:51:40] 不要只是用一個
[01:51:42] 尤其現在的工具
[01:51:44] 對啊
[01:51:45] 你自己要去設計一些
[01:51:48] agent的loop
[01:51:51] 就是agent的反思的一些策略
[01:51:54] 讓他去做
[01:51:55] 不要只是用工具
[01:51:57] 對
[01:51:58] 要設計一下
[01:52:01] 不然就變成只用工具就
[01:52:03] 沒什麼啦
[01:52:04] 就是除了他的possum
[01:52:06] 就是那個人設以外
[01:52:08] 再去限制
[01:52:10] 設計他loop的那個條件
[01:52:12] 再延期一點
[01:52:13] 是這個意思嗎
[01:52:14] 對
[01:52:15] 你讓他要
[01:52:16] 好像比較有智慧一點啦
[01:52:17] 不是
[01:52:18] 只是叫他
[01:52:20] 做一個資料的統整
[01:52:23] 好
[01:52:24] 對
[01:52:25] 好
[01:52:26] 再去研究一下
[01:52:27] 好
[01:52:41] 第二個部分
[01:56:41] 第二個部分呢
[01:56:42] 就是所謂的informed search
[01:56:44] 或者是heuristic search
[01:56:47] 那他的定義就是說
[01:56:49] 除了原本
[01:56:51] 問題的
[01:56:52] 該給的資訊之外
[01:56:54] 他還額外多知道了
[01:56:57] 一些
[01:56:58] 離目標有多遠的資訊
[01:57:02] 那一般來講
[01:57:03] 你多知道了一些資訊
[01:57:04] 你就能夠更有效率的
[01:57:07] 解決這個問題
[01:57:09] 那這個額外多知道的資訊呢
[01:57:12] 我們稱呼它叫做
[01:57:13] heuristic function
[01:57:16] 寫成h of n
[01:57:18] 那比如說
[01:57:19] 這個h of n呢
[01:57:20] 可以是
[01:57:22] 我從某一個
[01:57:24] 某一個都市
[01:57:26] 某一個狀態
[01:57:28] 到
[01:57:29] 我的
[01:57:30] 目的地的這個狀態
[01:57:32] 的最小的pass cost
[01:57:36] 可以定義成是這個heuristic function
[01:57:39] 好
[01:57:40] 所以舉個例子啊
[01:57:41] 剛剛的這個羅馬尼亞的這個地圖啊
[01:57:44] 我除了知道這個地圖
[01:57:46] 我除了知道說
[01:57:47] 我從A走到Z的里程是多少
[01:57:51] A走到S的里程是多少之外
[01:57:54] 假設我還知道
[01:57:56] 每一個都市
[01:57:57] 到
[01:57:58] Bucharest的直線距離
[01:58:02] 假設我知道
[01:58:04] 那這個就成為我的heuristic
[01:58:07] 所以這個heuristic呢
[01:58:09] 其實就是任何的某一個都市
[01:58:11] 到B這個都市的
[01:58:14] 最小的pass cost
[01:58:16] 因為直線距離是直線距離
[01:58:18] 它不見得真的有一條路啊
[01:58:20] 它只是在地圖上的直線距離而已啊
[01:58:23] 所以舉例啊
[01:58:25] A到B的直線距離是360
[01:58:27] C到B的直線距離160
[01:58:30] D到B的直線距離242
[01:58:33] 這樣
[01:58:34] 好
[01:58:35] 這是等於說
[01:58:36] 從空中往下拍
[01:58:38] 空照圖
[01:58:39] 然後畫一條直線
[01:58:41] 這個兩個都市之間的直線距離
[01:58:43] 這樣
[01:58:44] 假設我知道這個
[01:58:46] 好
[01:58:47] 那如果是這樣子的話呢
[01:58:49] 欸
[01:58:50] 我就可以開發出另外一種
[01:58:52] info search的辦法
[01:58:54] 這個叫做greedy best first
[01:58:56] first search
[01:58:58] 好
[01:58:59] 貪婪的
[01:59:00] 貪婪的優先搜尋演算法
[01:59:04] 好
[01:59:05] 比如說我今天從A要出發嘛
[01:59:07] 那我知道說呢
[01:59:09] 欸我的分支就是S T跟Z
[01:59:13] 好
[01:59:14] 那我要往哪裡走比較好勒
[01:59:16] 欸我有這個啊
[01:59:18] S距離目標的直線距離253
[01:59:22] 對不對
[01:59:23] T329
[01:59:24] Z374
[01:59:25] R
[01:59:26] 哪一個離目標最近
[01:59:28] 直線距離最近
[01:59:29] S最近
[01:59:30] 所以我就決定
[01:59:31] 我走到S
[01:59:33] 好
[01:59:34] 依次類推我從S往下走
[01:59:35] 我可以走到A
[01:59:38] 我可以走到F
[01:59:39] 可以走到O
[01:59:40] 可以走到R
[01:59:41] 好
[01:59:42] 那哪一個直線距離離
[01:59:45] Bucharest的最近呢
[01:59:47] F最近
[01:59:49] 欸那我就走F
[01:59:50] 好
[01:59:51] 那再繼續從F
[01:59:52] F再走到B
[01:59:53] 結束
[01:59:54] 我找到解了
[01:59:55] 我從A走到S
[01:59:56] S走到F
[01:59:57] 再走到B
[01:59:58] 這樣
[01:59:59] 這個就所謂的Greedy First Search演算法
[02:00:02] 好
[02:00:03] 很棒吧
[02:00:04] 好
[02:00:05] 我就看說
[02:00:06] 我的分支裡面
[02:00:07] 哪一個離Bucharest的最近
[02:00:10] 這樣
[02:00:11] 好
[02:00:12] 這個是在有這個Huristic的情況之下
[02:00:15] 但是但是以這個例子來講
[02:00:18] 不幸的事情是
[02:00:19] 從A走到S再走到F跟走到B
[02:00:22] 它雖然是一種走法
[02:00:24] 但這個走法不是最佳解
[02:00:27] 好
[02:00:28] 所以它是在告訴你說
[02:00:30] 欸即使你有空照圖
[02:00:33] 即使你有最短的直線距離的額外資訊
[02:00:37] 你利用這樣子來找
[02:00:39] 雖然很開心
[02:00:40] 很快就找到解了
[02:00:42] 但是它的解可能不是最佳解
[02:00:45] 好
[02:00:46] 實際上呢
[02:00:47] 你如果先走到R
[02:00:50] 再走到P
[02:00:51] 再走到B的話呢
[02:00:53] 你的整體的里程數是會最低的
[02:00:57] 所以剛剛這樣子講
[02:00:59] 你真正走這條路
[02:01:01] 從A走到S走到F再走到B
[02:01:03] 你真正所需花的Cost
[02:01:05] 你還是要回歸到你地圖上面
[02:01:08] 你A走到S的里程數
[02:01:10] S走到F的里程數
[02:01:11] 跟F走到B的里程數
[02:01:13] 你怎麼加起來
[02:01:15] 其實是比
[02:01:16] 你走到R再走到P再走到B
[02:01:19] 會多32公里
[02:01:21] 好
[02:01:22] 所以
[02:01:26] 什麼意思
[02:01:27] 就是如果有解的話
[02:01:28] 他一定會找到解
[02:01:29] 但是呢
[02:01:30] 他不是optimal
[02:01:32] 他不見得保證找到最佳解
[02:01:36] 好
[02:01:37] 那一般來講啊
[02:01:39] 雖然雖不中亦不遠矣嘛
[02:01:41] 對不對
[02:01:42] 他雖然找到的不是最佳解
[02:01:43] 但是找的解也挺不錯的啦
[02:01:46] 對不對
[02:01:47] 才差32公里嘛
[02:01:49] 那一般來講
[02:01:51] 如果你的heuristic越好
[02:01:54] 你
[02:01:57] 你的這個complexity呢
[02:01:59] 就可以大幅的下降
[02:02:01] 你看嘛
[02:02:02] 你有了這個heuristic
[02:02:03] 你是不是就不用在那邊BFS DFS
[02:02:06] 在那邊弄半天對不對
[02:02:08] 你這樣子很快就找到解啦
[02:02:10] 你的complexity可以大幅的降低
[02:02:14] 好
[02:02:15] 那可是剛剛這個畢竟不是最佳解嘛
[02:02:19] 好
[02:02:20] 所以說呢
[02:02:21] 在info search或者heuristic search這邊呢
[02:02:24] 也有很著名的演算法
[02:02:26] 叫做A star search
[02:02:28] 好
[02:02:29] A star search
[02:02:30] 它是最著名的best first search
[02:02:33] 它的概念是
[02:02:35] 欸
[02:02:36] 我呢
[02:02:37] 就整合剛剛的past cost GN
[02:02:41] 跟還有剛剛的heuristic HN
[02:02:45] 我把它合在一起
[02:02:47] 來一起當作我
[02:02:50] 判斷
[02:02:52] 哪一條路應該優先走的依據
[02:02:55] 所以
[02:02:56] GN代表的是past cost
[02:02:59] HN代表的是heuristic
[02:03:01] 就是the estimated cost of the cheapest path
[02:03:04] 所以
[02:03:05] 決定走哪一條路
[02:03:08] 我是靠GN加FN的結果
[02:03:11] 的這個FN
[02:03:12] 來
[02:03:14] 幫忙決定我要走哪一條路
[02:03:17] 那我們直接先看一個例子好了
[02:03:19] 直接看例子
[02:03:20] 比如說我今天要從A出發
[02:03:22] A呢
[02:03:24] 它可以走到S T跟Z
[02:03:29] 那我現在的評估
[02:03:31] 我要走哪一條路呢
[02:03:33] 我從A走到S
[02:03:35] 我其實要花140
[02:03:38] 我的里程數是140
[02:03:40] 然後呢S
[02:03:42] 它距離Bucharest的直線長度是253
[02:03:47] 我把這兩個加起來
[02:03:48] 也就是說
[02:03:49] 我考慮的點是
[02:03:50] 我如果走到S呢
[02:03:52] 我需要花的cost
[02:03:54] 以及我從S出發
[02:03:56] 走到目的地要花的預估的cost
[02:04:00] 加起來是393
[02:04:03] 好 一直被推
[02:04:04] 我如果走到T呢
[02:04:05] 4447
[02:04:06] 我如果走到Z呢
[02:04:07] 449
[02:04:08] 哪一個最少
[02:04:10] S最少
[02:04:11] 好 那我就走去S
[02:04:13] 你從S可以再繼續往下走
[02:04:16] 好 你所需花的cost是多少呢
[02:04:20] 比如說你S走到F的話
[02:04:22] 你從S走到F
[02:04:24] 你本來就要花239
[02:04:29] 那你從F到Bucharest的直線距離是176
[02:04:34] 所以呢你如果走F的話呢
[02:04:36] 這裡要預估要花415
[02:04:41] 那走到O的話671
[02:04:43] 走到R的話413
[02:04:45] 所以在這個時候呢
[02:04:47] 我就決定走R這條路
[02:04:49] 那一直被推
[02:04:50] R這個再繼續往下走
[02:04:52] 我就挑P這條路
[02:04:54] P再繼續往下走
[02:04:55] 然後你就可以發現
[02:04:56] 就走到Bucharest
[02:04:59] 所以呢它這樣子找出來的路徑呢
[02:05:02] 在這裡
[02:05:03] 走到P
[02:05:04] P再往下走
[02:05:05] 走到這裡
[02:05:06] 所以它找出來的最佳路徑就是
[02:05:08] A走到S
[02:05:10] 走到R
[02:05:11] 走到P
[02:05:12] 再走到B
[02:05:13] 那它之所以比剛剛的
[02:05:17] 這個Greedy Best First Search
[02:05:22] 優越的地方就在於說
[02:05:26] 就是考慮了我過去的歷史
[02:05:31] 我的Past Cost
[02:05:33] 以及我預估未來我要走的Cost有多少
[02:05:38] 兩個一起合併考量
[02:05:40] 那這樣子就可以找到最好的那條路徑
[02:05:44] Cost最低的那條路徑
[02:05:47] 這就是A Star Search
[02:05:50] 你會有點懷疑說
[02:05:52] 欸真的嗎
[02:05:54] 這樣子保證一定可以
[02:05:56] 找到最佳解嗎
[02:05:59] 事實上這是可以證明的
[02:06:01] 當然我們不會講仔細的證明啦
[02:06:05] 理論上我們可以證明
[02:06:06] 這樣子的A Star Search呢
[02:06:09] 是Optimal
[02:06:10] 它可以找到Complete and Optimal
[02:06:13] 只要
[02:06:16] 只要什麼呢
[02:06:18] 只要你的Heuristic Function
[02:06:20] 符合兩個特性
[02:06:23] 一個叫做Admissibility
[02:06:27] 一個叫做
[02:06:28] Consistency
[02:06:30] 你的Heuristic
[02:06:32] 如果你可以證明你的Heuristic Function
[02:06:34] 符合Admissible
[02:06:36] 跟Consistent
[02:06:38] 你就一定能夠說
[02:06:40] A Star Search
[02:06:42] 是Optimal
[02:06:44] OK
[02:06:45] 詳細的證明我們不是
[02:06:46] 不講
[02:06:47] 因為那個很長
[02:06:49] 那但是呢我們講一下什麼叫Admissible
[02:06:52] Admissible是說
[02:06:55] 如果這個Heuristic是Admissible
[02:06:58] 就代表它呢
[02:07:00] Never overestimate the cost to reach the goal
[02:07:04] 你這個Heuristic呢
[02:07:06] 永遠不會過度估計了某一個State
[02:07:13] 走到目標那個State所需花的Cost
[02:07:17] 這樣
[02:07:18] 所以我們剛剛講的這個
[02:07:20] 羅馬尼亞地圖這一個
[02:07:22] 你從Z這個都市
[02:07:24] 到B這個都市
[02:07:26] 的最有可能的最短路徑
[02:07:29] 就像照圖
[02:07:30] 直接畫一條線的直線距離
[02:07:32] 它一定會比你走實際的道路
[02:07:35] 的Cost來的低
[02:07:37] 對不對
[02:07:38] 因為實際是實體世界上
[02:07:41] 沒有一條路剛好是直通
[02:07:44] 從Z直通到B的嘛
[02:07:46] 那我利用Z直通到B這個都市的
[02:07:50] 直線距離
[02:07:52] 來當成是我的Heuristic的事
[02:07:55] 所以它Never overestimate
[02:07:57] 永遠不會過度估計
[02:07:59] 所以呢
[02:08:01] 這樣子的Heuristic
[02:08:02] 我們就說它符合它的Misable
[02:08:05] 這個特性
[02:08:07] 另外一個它同時也要符合
[02:08:10] Consistency的特性
[02:08:12] Consistency的特性是什麼呢
[02:08:15] 就是說我們如何可以說
[02:08:17] 一個Heuristic是Consistent呢
[02:08:20] 那就是
[02:08:22] For every node n
[02:08:24] and every successor n'
[02:08:27] of n
[02:08:29] 就是n的往下分支
[02:08:32] Generated by any action
[02:08:35] 不管是做哪一個動作
[02:08:36] 反正就是所謂的分支的意思吧
[02:08:38] The estimated cost of reaching the goal from n
[02:08:43] is no longer than the step cost
[02:08:47] from n to n'
[02:08:50] plus the estimated cost
[02:08:52] reaching the goal from n'
[02:08:54] 好像在繞口令
[02:08:55] 其實很簡單
[02:08:57] 就是說
[02:08:58] 就是說我從n裡的這個Heuristic
[02:09:05] 我預估的這個Cost
[02:09:07] 一定會小於等於
[02:09:09] 我從n走到n'
[02:09:11] 我說花的花費
[02:09:14] 再加上
[02:09:15] 我從n'的這個Estimation Cost
[02:09:20] 還是很奇怪
[02:09:25] 但事實上這件事情就是三角不等式
[02:09:28] 這個就是三角不等式
[02:09:30] 對不對
[02:09:31] 我們畫一下
[02:09:33] 這個畫很怪異嗎
[02:09:34] 這很簡單啊
[02:09:36] N在這裡
[02:09:39] 然後呢
[02:09:40] 它的分支N'在這裡
[02:09:43] 這個很難用
[02:09:44] 因為我用滑鼠
[02:09:46] 目的地是G
[02:09:48] 在這裡
[02:09:49] 對不對
[02:09:51] HN是什麼意思
[02:09:53] HN就是
[02:09:55] 這個的直線距離
[02:09:56] 這叫HN
[02:09:58] HN一定小於等於什麼
[02:10:02] 這個是什麼
[02:10:03] 這個就是從n走到N'
[02:10:06] 這個是什麼
[02:10:07] 這個就是從N'走到G
[02:10:09] 所以說你看
[02:10:10] 它是不是在講
[02:10:11] 這一條距離一定小於等於這個
[02:10:15] 加上這個
[02:10:17] 這不就是三角不等式嗎
[02:10:20] 數學裡面的三角不等式嗎
[02:10:22] 所以只要你的Heuristic Function
[02:10:24] 符合三角不等式
[02:10:26] 也符合Admissible
[02:10:28] 過去的學者就已經證明瞭
[02:10:33] 這個Amstrong Search的演算法是Active
[02:10:37] 那詳細的證明我們就不講了
[02:10:43] 我們只講它的特性是怎樣
[02:10:47] 好
[02:10:48] 那這個就是Informed Search的部分
[02:10:51] 我們第三章講完了
[02:10:53] 都不針對課程內容問題
[02:11:11] 大家都在注意那些
[02:11:14] 沒有問題我們要繼續往下走
[02:11:26] 再來
[02:11:29] 好
[02:11:49] 剛剛在第三章呢
[02:11:50] 我們知道
[02:11:52] 有一些問題我們可以把它
[02:11:55] 描寫在一顆Tree上面
[02:11:58] 對不對
[02:11:59] 那我們就可以在Tree上面運作
[02:12:01] 來找到我們的解答
[02:12:04] 好
[02:12:05] 那接下來到了第四章呢
[02:12:06] 我們要來講一個更複雜一點的
[02:12:09] 就是如果我今天我的問題
[02:12:12] 無法表達在Tree上面的話怎麼辦
[02:12:19] 所以他說呢
[02:12:20] 這個講到這邊為止呢
[02:12:22] 前面都是說
[02:12:23] 我可以這個表達在Tree上面啊
[02:12:27] 那我在Tree上面走來走去走走走
[02:12:30] 我去做不同的Action走
[02:12:32] 我就找到我的目的地
[02:12:33] 我就找到我的答案了
[02:12:34] 好
[02:12:35] 那但是在很多的問題裡面啊
[02:12:38] 呃
[02:12:39] 我抵達目的地
[02:12:42] 或者是抵達我達到我要的目標
[02:12:45] 這件事情呢
[02:12:46] 跟你怎麼走
[02:12:47] 可能是沒有什麼關係的
[02:12:50] 跟你執行的Action的
[02:12:52] 誰先誰後是沒什麼關係的
[02:12:55] 好
[02:12:56] 比如說在八皇后問題裡面
[02:12:59] 我們並沒有規定說
[02:13:01] 你一定是要把第一隻皇后放在第一個Color
[02:13:08] 第二隻皇后放在第二個Color
[02:13:10] 沒有啊
[02:13:11] 我高興的話
[02:13:12] 我第一隻皇后我直接放在某一個位置
[02:13:15] 第七個Color
[02:13:17] 第二隻皇后我放在第三個Color
[02:13:20] 那反正我最後
[02:13:22] 我擺起來的樣子
[02:13:23] 沒有互相攻擊就好了
[02:13:25] 所以他跟你擺的順序基本上沒有關係
[02:13:30] 沒什麼關係
[02:13:31] 沒什麼關係
[02:13:35] 所以說
[02:13:36] 在這種問題裡面呢
[02:13:37] 他就不太適合用表達成Tree的一個形式
[02:13:42] 在八皇后問題裡面呢
[02:13:46] What matters is the final configuration
[02:13:50] 我在乎的是他最後有沒有互相攻擊
[02:13:53] 跟你怎麼擺那個皇后的順序無關
[02:13:56] 所以呢
[02:13:57] 我們需要另外一種種類的演算法呢
[02:14:00] Not worry about the past at all
[02:14:02] 一點都不關心誰先誰後
[02:14:05] 好
[02:14:06] 那其中呢
[02:14:08] 我們來講
[02:14:09] 最重要的一種做法
[02:14:12] 就叫做Local Search
[02:14:14] 它一樣是一種Search
[02:14:16] 我們這裡講的Search呢
[02:14:18] 是指說
[02:14:19] 在好多不同可能的解答裡面
[02:14:23] 找到我們要的解的這種Search
[02:14:25] 所以大家不要看到Search
[02:14:26] 就覺得說
[02:14:27] 在做Google裡面的文件搜尋
[02:14:30] 我們這裡講的Search是一個更廣泛的概念
[02:14:33] 就是
[02:14:34] 假設在一個空間當中
[02:14:35] 一個虛擬的Solution Space當中
[02:14:41] 我們要去找到我們的最佳解的那種感覺
[02:14:47] 那個大家理工科的應該都上過線性代數吧
[02:14:52] 對不對
[02:14:53] 線性代數就是在做這件事
[02:14:55] 你回想一下
[02:14:56] 你想一下
[02:14:57] 回想一下線性代數
[02:14:59] 是吧
[02:15:00] 我現在給你好多線性方程式
[02:15:03] 你要找到
[02:15:04] Solution
[02:15:08] 你是不是要找到解
[02:15:10] 你要去求AX等於B
[02:15:12] 你要找到那個X嘛
[02:15:14] 對不對
[02:15:15] 好那你一定也修過
[02:15:16] 就是說
[02:15:17] 當你不見得每一個這個AX等於B都會有解啊
[02:15:21] 對不對
[02:15:22] 當A這個矩陣有反矩陣的時候
[02:15:24] 才有解嘛
[02:15:25] 對不對
[02:15:26] 那它如果無解的話怎麼辦
[02:15:29] 你就只能夠找最小平方解
[02:15:32] This Square Solution
[02:15:34] 那其實它的意思就是說
[02:15:36] 在眾多可能的解裡面找到一個解
[02:15:39] 是最佳的那一個
[02:15:41] 能夠符合這種狀態的最佳的解嘛
[02:15:45] 所以這個也就是
[02:15:48] 線性代數裡面就已經有這種觀唸了嘛
[02:15:50] 現在Again
[02:15:51] 這裡又來這種觀念
[02:15:52] 也是一樣
[02:15:53] 我們就是要在眾多可能的解裡面
[02:15:56] 找到最好的那種解的意思
[02:15:59] 好
[02:16:00] 那OK
[02:16:03] 那Local Search的演算法呢
[02:16:05] 它的基本原則就是說
[02:16:06] 我現在從某一個地方出發
[02:16:10] 我就去看我周圍的鄰居
[02:16:13] 現在重新定義是
[02:16:17] 這裡雖然寫Node
[02:16:18] 我現在從這個Node出發
[02:16:20] 現在啊
[02:16:21] 所謂的一個Node的意思就是
[02:16:24] 某一個可能的解的意思
[02:16:27] 但是我這個解呢
[02:16:32] 我這個Solution可能不是那麼好
[02:16:35] 我要從我的鄰居
[02:16:38] 裡面找到一個
[02:16:40] 表現得比我更好的那個Solution
[02:16:43] 然後我走過去
[02:16:45] Update一下
[02:16:46] 我就變成新的
[02:16:47] 用那個鄰居來當成是一個
[02:16:49] 更好的一個解
[02:16:51] 然後那從那個鄰居
[02:16:52] 以它為中心
[02:16:53] 又去找我鄰居的鄰居
[02:16:56] 看看裡面有沒有人
[02:16:57] 又表現得更好
[02:16:59] 我再去Update成更好的一個解
[02:17:01] 這個整個大的原則
[02:17:03] 就叫做Local Search
[02:17:06] 那Local Search的
[02:17:07] 最內的演算法呢
[02:17:09] 它用的Memory很少
[02:17:11] 為什麼
[02:17:12] 因為它一次只需要看
[02:17:14] 少部分的鄰居們
[02:17:16] 這樣子
[02:17:18] 那一般來講呢
[02:17:20] They can often find reasonable solution
[02:17:24] 一般來講
[02:17:25] 它也能夠找到
[02:17:26] 合理還不錯的解
[02:17:28] 即使你的Solution Space
[02:17:30] 非常大
[02:17:31] 你的解空間
[02:17:33] 你可能可以走的
[02:17:35] 這個範圍可能很大
[02:17:36] 一般來講
[02:17:37] 只要你找得夠久
[02:17:39] 可以找到還不錯的解
[02:17:41] 我之所以講還不錯
[02:17:42] 就代表它不見得是最好
[02:17:45] Local Search Algorithms are useful
[02:17:47] for solving pure optimization problems
[02:17:50] 其中呢它就是
[02:17:52] 它基本上每一個解
[02:17:55] 我都可以去評判說
[02:17:56] 你這個解
[02:17:57] 你這個Solution
[02:17:59] 是一個多棒的Solution
[02:18:02] 它有一個Objective Function
[02:18:03] 有一個目標函數
[02:18:05] 來去評判
[02:18:06] 你這個Solution有多棒
[02:18:08] 概念上來講
[02:18:12] 我們可以用這張圖來表達
[02:18:14] Local Search這個問題
[02:18:17] 這張圖的Excel
[02:18:20] 代表的是State Space
[02:18:22] 就是你這個問題的某種狀態
[02:18:25] 你在不同的狀態之下
[02:18:27] 你的Objective Function
[02:18:30] 你的目標函數
[02:18:32] 的值是怎麼樣
[02:18:34] 也就是說
[02:18:35] 你今天做了某一個動作
[02:18:37] 讓你目前的狀態
[02:18:38] 變成某一種狀態了
[02:18:40] 那這個狀態到底有多棒的意思
[02:18:43] 有多棒的意思
[02:18:45] 那假設我們是要
[02:18:46] 讓這個Objective Function的值
[02:18:48] 越高越好
[02:18:49] 越大越好的話
[02:18:51] 那我們可以去試
[02:18:53] 各種不同的狀態嗎
[02:18:56] 你也可以想像
[02:18:57] 剛剛我們那個九宮格的問題
[02:19:00] 九宮格的問題
[02:19:02] 你那八塊積木
[02:19:04] 八塊木塊
[02:19:06] 可以隨便亂擺嗎
[02:19:08] 對不對
[02:19:09] 有一種擺法
[02:19:10] 可能離我真正最後的
[02:19:12] 要排好1 2 3 4 5 6 7 8
[02:19:14] 離得很遠
[02:19:15] 那它的分數
[02:19:16] 它的Objective Function Value
[02:19:18] 就低嘛
[02:19:19] 如果只差那個
[02:19:21] 感覺1 2 3 4 5 6
[02:19:23] 或者說1 2 3 4 5 6 7
[02:19:25] 都已經擺好
[02:19:26] 只剩下8的位置
[02:19:27] 跟7的位置
[02:19:28] 還沒有擺得很好
[02:19:30] 那它其實就離我的目標很近
[02:19:32] 我就給它比較高分嘛
[02:19:34] 所以概念上
[02:19:36] 那我們要解一個
[02:19:37] 這個問題
[02:19:38] 這個問題的時候
[02:19:39] 它就如同是
[02:19:40] X軸是我各式各樣不同的State
[02:19:43] Y軸是我某一種狀態之下
[02:19:47] 有多高的分數
[02:19:50] 那它可能是一個
[02:19:51] 很複雜崎嶇的
[02:19:54] 一個曲線的變動
[02:19:57] 那我們的目標是什麼
[02:19:58] 我們的目標是
[02:19:59] 能夠讓分數最高分的那種狀態
[02:20:02] 所以它的最高分在這裡
[02:20:04] 它對應的狀態就是拉下來
[02:20:06] 就是這個狀態
[02:20:07] 這個狀態
[02:20:09] OK
[02:20:10] 好
[02:20:11] 那一開始
[02:20:15] 首先要怎麼擺
[02:20:20] 它可能在這裡
[02:20:22] 那我們就評估一下
[02:20:23] 那它的分數大概就只有這麼多
[02:20:25] 那我要如何讓
[02:20:29] 我盡可能貼近
[02:20:32] 我的目標呢
[02:20:34] 那我就去
[02:20:35] 如果你在玩這個遊戲的話
[02:20:37] 你是會稍微移移看對不對
[02:20:39] 你會盡可能的移動你的那個空白
[02:20:43] 讓它盡可能去接近
[02:20:46] 你想要達到那個目標的擺設嘛
[02:20:49] 對不對
[02:20:50] 好
[02:20:51] 你可以往右移一格看看
[02:20:53] 往上移一格看看
[02:20:54] 往左移一格看看
[02:20:55] 往下移一格看看嘛
[02:20:57] 對不對
[02:20:58] 這個你往上移一格所造成的狀態
[02:21:01] 就叫做你的鄰居
[02:21:04] 你的鄰居
[02:21:05] 這樣可以嗎
[02:21:06] 你往上移一格造成一個結果
[02:21:09] 那就是你的一號鄰居
[02:21:11] 往右移一格
[02:21:12] 造成的結果就是你二號鄰居
[02:21:14] 那你可能有N個鄰居
[02:21:16] 對不對
[02:21:17] 那你再看看說
[02:21:18] 那你這些鄰居裡面
[02:21:20] 哪一個是最接近
[02:21:23] 你的目標狀態的
[02:21:26] 你就決定
[02:21:28] 就這麼移這樣子
[02:21:30] 那你聽懂嗎
[02:21:31] 好
[02:21:32] 那現在在這裡
[02:21:34] 一樣喔
[02:21:35] 我現在初始狀態可能在這邊
[02:21:36] 我就找到一個最好的鄰居
[02:21:38] 我就移過去
[02:21:39] 然後一時之內
[02:21:40] 我再移一下
[02:21:41] 我可能
[02:21:42] 就找到這個
[02:21:43] 再移一下
[02:21:44] 就找到這個
[02:21:45] 好
[02:21:46] 所以在某種情況下
[02:21:48] 你可能就會發現
[02:21:49] 某種狀態呢
[02:21:50] 接下來我再怎麼移動
[02:21:52] 我再也不會更好的
[02:21:55] 好
[02:21:56] 那你可能就說
[02:21:57] 喔好
[02:21:58] 我的最佳解
[02:21:59] 大概就是這樣子的
[02:22:00] 我目前移到這裡
[02:22:04] 好
[02:22:05] 那這種情況呢
[02:22:06] 就是你達到了一定程度的解拔
[02:22:10] 這就是所謂的local maxima
[02:22:14] 那你一看這個圖
[02:22:15] 你就知道說
[02:22:16] 可是你這個顯然不是最好的解答嘛
[02:22:18] 因為我一看
[02:22:19] 我就知道
[02:22:20] 最好的解答在這裡嘛
[02:22:22] 對不對
[02:22:23] 好
[02:22:24] 但問題是喔
[02:22:25] 在你真正解一個問題的
[02:22:27] 在解一個問題的時候呢
[02:22:29] 你永遠不知道說
[02:22:32] 你可能永遠都不知道
[02:22:35] 哪邊有一個最好的解法
[02:22:36] 那個解法在哪裡
[02:22:37] 你永遠都不知道
[02:22:38] 你只能夠說
[02:22:39] 就目前我能夠看到的範圍內
[02:22:42] 我能夠找到的最佳解法
[02:22:44] 就是在這裡
[02:22:46] 好
[02:22:47] 有可能是這樣
[02:22:48] 所以你在找尋的過程當中
[02:22:49] 你可能會卡在這個local maxima
[02:22:52] 那你也有可能會
[02:22:53] 假設你今天一開始的初始條件在這裡
[02:22:56] 好
[02:22:57] 那你可能走走走
[02:22:58] 走到這裡來囉
[02:22:59] 你就發現
[02:23:00] 我的鄰居們都跟我一樣好
[02:23:04] 那就happy
[02:23:05] 對不對
[02:23:06] 我們不錯了
[02:23:08] 你也有可能會卡在這邊
[02:23:10] 這個叫做
[02:23:11] 你走到一個高原
[02:23:13] 高原的地方
[02:23:14] flat
[02:23:15] the local maxima
[02:23:16] 好
[02:23:17] 或者你走到一個山腰
[02:23:18] 剛好這個山腰
[02:23:19] 不知道為什麼
[02:23:20] 剛好有一個平臺
[02:23:21] 你本來從這裡出發
[02:23:22] 走走走
[02:23:23] 走到這裡來
[02:23:24] 你覺得你已經走到最好的
[02:23:30] 殊不知其實
[02:23:31] 你如果再繼續往下走
[02:23:33] 你有可能會找到這裡
[02:23:35] 但你不知道
[02:23:36] 那你在走之前
[02:23:37] 根本就不知道
[02:23:38] 所以基本上
[02:23:40] 這個search的演算法
[02:23:42] search的這個問題呢
[02:23:43] 就是說
[02:23:44] 你其實永遠也不曉得
[02:23:47] 你的最佳解
[02:23:49] 會是在什麼地方
[02:23:53] 你只能夠邊走邊看
[02:23:55] 好
[02:23:56] 那所以說呢
[02:23:57] 這個local search的演算法
[02:23:59] 我們介紹好幾個
[02:24:00] 都屬於這一類的
[02:24:02] 其中第一個就叫做
[02:24:03] heel climbing search
[02:24:05] 爬山演算法
[02:24:07] 那概念
[02:24:08] 我剛剛其實已經講完了
[02:24:10] 就是說呢
[02:24:11] 我今天隨便把你丟到
[02:24:13] 一個奇虛不平的一個地方
[02:24:17] 你的目標就是
[02:24:18] 爬到最高那裡
[02:24:20] 好
[02:24:21] 那這裡的策略就是什麼
[02:24:22] 我隨機的把你丟到某個地
[02:24:24] 一個位置
[02:24:26] 好
[02:24:27] 那你就去看一下
[02:24:28] 我的鄰居們
[02:24:29] 我就看一下
[02:24:30] 方圓100公尺內
[02:24:32] 哪一個地方是最高的
[02:24:34] 因為方圓100公尺
[02:24:35] 就是我的鄰居嘛
[02:24:36] 哪個地方
[02:24:37] 我就把我的鄰居
[02:24:38] 全部都check過一次
[02:24:40] 發現呢
[02:24:41] 我往右邊走20公尺的那個地方
[02:24:44] 是海拔高度最高的
[02:24:46] 好
[02:24:47] 然後就走過去
[02:24:48] 然後我再以那個鄰居為中心
[02:24:51] 再去看他方圓100公尺內的範圍
[02:24:54] 的鄰居們
[02:24:56] 有沒有比他再更好的
[02:24:57] 如果有
[02:24:58] 我就走過去
[02:24:59] 就這樣
[02:25:00] 就這麼簡單
[02:25:01] 所以你看這個演算法很簡單啊
[02:25:03] 我現在呢
[02:25:05] 我是current
[02:25:07] 我在這裡
[02:25:08] 那我去找到
[02:25:10] 我的鄰居們
[02:25:15] 當然鄰居的定義
[02:25:16] 有各式各樣
[02:25:17] 就看你的應用核定
[02:25:19] 好
[02:25:20] 如果鄰居的
[02:25:23] 所有鄰居的objective function value
[02:25:27] 都比我現在來的低
[02:25:29] 那代表我現在已經在最高處啦
[02:25:31] 那我就回答我現在的答案
[02:25:35] 如果沒有
[02:25:37] 有鄰居的value比我高
[02:25:40] 那我就用鄰居來取代叫我
[02:25:43] 好
[02:25:44] 而且這裡講的鄰居是
[02:25:46] 周邊鄰居裡面最高的那個鄰居
[02:25:49] 他的objective function value最高的那個鄰居
[02:25:52] 所以我永遠都會走到
[02:25:54] 我最強的那個鄰居那裡
[02:25:56] 就對了啦
[02:25:57] 好
[02:25:58] 如果我已經是最強的
[02:25:59] 我就是答案
[02:26:00] 如果我不是
[02:26:01] 如果旁邊有鄰居比我更強
[02:26:04] 我就用那個鄰居來取代叫我
[02:26:07] 這個就叫希爾談
[02:26:11] OK
[02:26:12] 來舉個例子啦
[02:26:13] 剛剛講八皇后問題
[02:26:15] 八皇后問題呢
[02:26:17] 假設今天
[02:26:19] 我隨機的放這八隻
[02:26:21] 八隻皇后
[02:26:23] 長這樣
[02:26:24] 我放完之後長這樣
[02:26:26] 好那我現在
[02:26:27] 我要想辦法調整這個盤面
[02:26:31] 使得
[02:26:33] 我越接近我的目標越好
[02:26:36] 我的目標當然就是八隻皇后
[02:26:38] 我的衝突的數量要越少越好
[02:26:40] 好那我現在來定義一下
[02:26:42] 怎麼樣叫做鄰居呢
[02:26:43] 就是說我允許你動一隻皇后
[02:26:47] 然後呢
[02:26:48] 這隻皇后只能夠在同一個column裡面移動
[02:26:51] 好
[02:26:52] 我定義我的所謂的鄰居是這樣
[02:26:54] 好
[02:26:55] 那
[02:26:56] 我每動一個位置
[02:26:58] 我就要
[02:26:59] 我都可以去評估說
[02:27:01] 我動了她之後呢
[02:27:02] 我皇后之間我衝突的數量
[02:27:06] 是多少個
[02:27:07] 所以比如說
[02:27:08] 假設我動這個皇后
[02:27:10] 第二個column的皇后
[02:27:11] 我如果是把她移到這一格
[02:27:14] 我還是會有十四個衝突
[02:27:17] 十四組皇后的衝突
[02:27:20] 我如果移到這一格也是十四組
[02:27:22] 我如果移到這一格呢
[02:27:23] 會只剩下十二組皇后的衝突
[02:27:26] 以此類推
[02:27:28] 所以說呢
[02:27:29] 在這個盤面之下呢
[02:27:31] 我就決定
[02:27:33] 我要把這個皇后移到這裡來
[02:27:36] 相當於我就走到一個
[02:27:39] 我的鄰居那邊去
[02:27:41] 好到了下一個步驟
[02:27:42] 我再從那個鄰居
[02:27:44] 再去看說我要移哪一個
[02:27:46] 能夠讓我的衝突的數量
[02:27:49] 越低越好
[02:27:50] 那經過很多次很多次呢
[02:27:53] 他可能就只像這個樣子
[02:27:55] OK那這個就是一個heel climbing
[02:28:00] 好那heel climbing的演算法呢
[02:28:03] 有時候又稱為是
[02:28:05] greedy local search
[02:28:06] 就是隻看周邊的鄰居
[02:28:09] 做出最貪婪的決定
[02:28:11] 因為他永遠只取
[02:28:13] 最強的那個鄰居來取代掉
[02:28:15] 那是這麼簡單的一個想法呢
[02:28:20] it turns out that the greedy algorithm
[02:28:22] often performs quite well
[02:28:24] 事實上表現得還不錯喔
[02:28:27] 他當然你可想而知
[02:28:30] 他絕對不保證
[02:28:31] 永遠可以找到最佳解
[02:28:33] 但一般來講
[02:28:34] 可以找到還不錯的解
[02:28:37] 那他也
[02:28:40] 我之所以講還不錯
[02:28:41] 就是因為他不是最佳解嘛
[02:28:43] 他可能走走走
[02:28:45] 走到一定的程度就卡住了
[02:28:47] 所謂的卡住是因為
[02:28:50] 他已經覺得他很厲害了
[02:28:52] 他夠好了
[02:28:53] 周邊的鄰居沒有在比他更好
[02:28:55] 所以他可能是卡在一個local maximum
[02:28:58] 也可能卡在一個無極
[02:29:01] rich
[02:29:02] 就是說剛好
[02:29:04] 這個無極這條線上
[02:29:07] 所有旁邊的鄰居都是更弱的
[02:29:11] 那我往某個方向走
[02:29:13] 其實所有的鄰居都跟我一樣好
[02:29:17] 對不對
[02:29:18] 某個方向上的鄰居都跟我一樣好
[02:29:20] 除了這個方向之外的其他鄰居
[02:29:22] 都比我們來的爛
[02:29:24] 那我也會覺得說
[02:29:25] 我已經夠好了
[02:29:26] 這是無極
[02:29:27] 或者說我走到一個平原
[02:29:29] 高原
[02:29:31] 那你也可能會卡住
[02:29:33] 那這裡有一些過去的實驗數據
[02:29:36] 比如說八華貨問題裡面呢
[02:29:38] 假設我永遠都取
[02:29:40] 最好的那個鄰居走過去
[02:29:44] 他基本上有86%的時間呢
[02:29:49] 會卡在local minimum
[02:29:52] 然後呢14%會找到解答
[02:29:59] 那通常是這樣
[02:30:02] 它的好處是說
[02:30:03] It works quickly
[02:30:05] Taking just 4 steps on average
[02:30:07] when it succeeds
[02:30:09] and 3 when it gets done
[02:30:11] 他的意思是說
[02:30:12] 如果他在八華貨問題裡面
[02:30:15] 如果真的有找到最佳解的話
[02:30:19] 真的有找到不死
[02:30:22] 即使八隻皇后不互相衝突
[02:30:24] 如果有找到的話
[02:30:25] 平均四步移動四次就找到了
[02:30:28] 如果他找得到的話
[02:30:30] 那我們說
[02:30:31] 他其實大概只有14%找到
[02:30:33] 大部分86%是找不到的
[02:30:36] 那不過好在是這樣
[02:30:38] 他就算沒找到互相衝突的case
[02:30:42] 他卡住了
[02:30:43] 他也很快就卡住
[02:30:44] 他三步就卡住了
[02:30:46] OK
[02:30:48] 那他說呢
[02:30:49] 即使整體而言
[02:30:50] 這不錯喔
[02:30:51] 因為整體而言呢
[02:30:53] 他要考慮的所有擺設的情況
[02:30:56] 有8的84%
[02:30:58] 17個million
[02:31:00] 在這17個million可能的狀況裡面
[02:31:03] 你就算卡住了
[02:31:05] 也是很快就卡住了
[02:31:07] 這是很不錯的
[02:31:09] 至少讓你很快知道你失敗了
[02:31:13] OK
[02:31:14] 那你可能會想
[02:31:16] 那我可不可以稍微改良一下
[02:31:18] 比如說
[02:31:19] 我讓他
[02:31:21] 如果允許讓他
[02:31:23] 即使你走到一個高遠的地方
[02:31:25] 照理講高遠的地方就是說
[02:31:27] 你的鄰居們都
[02:31:29] 跟你一樣好了嘛
[02:31:30] 對不對
[02:31:31] 你如果允許讓他用
[02:31:33] 跟你一樣的鄰居
[02:31:35] 你也走過去試試看
[02:31:37] 你讓他有這個彈性
[02:31:40] 那效果會變好呢
[02:31:42] 答案是會
[02:31:44] 因為
[02:31:46] 這個
[02:31:48] 你有更多探索的機會嘛
[02:31:51] 說不定
[02:31:52] 你雖然你左邊
[02:31:54] 連續5個鄰居
[02:31:56] 都跟你一樣好
[02:31:57] 你搞不好到了第6個
[02:31:59] 左邊的第5個
[02:32:00] 再往外看
[02:32:01] 說不定就會找到一個更好的
[02:32:03] 一個高峰可以爬上去
[02:32:05] 所以在這樣的一個小巧的變形之下呢
[02:32:08] 成功找到錢的機率
[02:32:10] 就從14%飛到94%喔
[02:32:13] 不過呢
[02:32:14] 因為你允許他
[02:32:16] 用一個跟你一樣好的鄰居
[02:32:18] 所以呢
[02:32:19] 你要
[02:32:20] 找到最佳企業的
[02:32:22] 這個步驟啊
[02:32:23] 就遠遠
[02:32:24] 變成21步
[02:32:26] 那你如果要卡住
[02:32:28] 也要64步
[02:32:29] 之後才會卡住
[02:32:31] 所以
[02:32:32] 這個就是一個
[02:32:33] 妥協啦
[02:32:35] 那還有其他變形呢
[02:32:36] 比如說
[02:32:38] Stochastic Hill Climbing
[02:32:41] 他說
[02:32:42] 我們剛剛前面都講說
[02:32:43] 我永遠都找最好的那個鄰居嘛
[02:32:47] 那我可不可以不要
[02:32:48] 永遠找最好的鄰居
[02:32:50] 今天我有一百個鄰居
[02:32:52] 其中有十個表現比我好
[02:32:54] 我從這十個裡面
[02:32:55] 我隨機挑一個
[02:32:56] 我不要永遠都挑最好的那一個
[02:32:59] 這叫Stochastic Hill Climbing
[02:33:02] 誰知道啊
[02:33:03] 說不定
[02:33:04] 這個
[02:33:05] 我先挑一個不是那麼好的鄰居
[02:33:09] 從他去往外走
[02:33:12] 搞不好有更好的一個結果啊
[02:33:14] 這就好像說
[02:33:15] 大家畢業的時候
[02:33:16] 一開始第一份工作
[02:33:17] 你一定要挑
[02:33:19] 給你吸嘴最高的那個工作嘛
[02:33:22] 你是Greedy First Search
[02:33:25] 是不是
[02:33:26] 但很難保證
[02:33:28] 你未來的生涯
[02:33:29] 你走這條路是最好的
[02:33:31] 對不對
[02:33:32] 再來
[02:33:34] First Choice Hill Climbing
[02:33:36] 意思就是說
[02:33:37] 你在搜尋鄰居的過程當中
[02:33:39] 你碰到的
[02:33:41] 第一個表現比你好的鄰居
[02:33:43] 你就選他了這樣子
[02:33:47] 所以這有點像是
[02:33:48] 你以後出去轉工作
[02:33:49] 你投了時間努力
[02:33:51] 對不對
[02:33:52] 第一個說要搜你的那家公司
[02:33:54] 你就去了
[02:33:55] 這是First Choice Hill Climbing
[02:33:57] 不見得一定是不好
[02:33:59] 也不見得一定好就是了啦
[02:34:02] 不好說
[02:34:03] 那也可以是Render Result
[02:34:05] 那比如說
[02:34:06] 因為不管怎麼樣
[02:34:08] 不管是哪一種Hill Climbing
[02:34:10] 都有可能會卡住
[02:34:12] 你隨機從這個地方出發
[02:34:14] 搜尋
[02:34:15] 有可能卡住了
[02:34:17] 那所以怎麼辦
[02:34:18] 我可不可以隨機很多次出發
[02:34:21] 對不對
[02:34:22] 我這次從這裡出發
[02:34:23] 卡在某一個Local Maxima
[02:34:27] 我下一次從另外一個地方出發
[02:34:29] 我可能卡在另外一個Local Maxima
[02:34:32] 對不對
[02:34:33] 我做了好幾次
[02:34:34] 那這些Local Maxima裡面
[02:34:37] 我就取相對最厲害的那一個
[02:34:41] 那這就是Render Result Hill Climbing
[02:34:44] OK
[02:34:45] 那到底Hill Climbing會不會成功呢
[02:34:47] 會不會整整找到解呢
[02:34:49] Depends very much on the shape of the state
[02:34:52] State and the state space landscape
[02:34:55] 那就要看說
[02:34:56] 你這個整個Objective Function
[02:34:59] 隨著你不同的State
[02:35:00] 你這個高高低低的複雜的情況是怎樣
[02:35:03] 不見得一定不好
[02:35:06] 也不見得一定好
[02:35:08] 我們只是說
[02:35:09] 它是一種解決
[02:35:12] 它是一種Local Search的方式
[02:35:13] 它是一種解法
[02:35:16] OK
[02:35:17] 好
[02:35:18] 那今天時間差不多了
[02:35:20] 我們就今天先講到Hill Climbing
[02:35:23] 就好了
[02:35:25] 那看看最後有沒有什麼問題
[02:35:27] 是的
[02:35:35] 我之後會把它放上去
[02:35:37] 沒有問題
[02:35:42] 大家對課程內容
[02:35:44] 全盤理解
[02:35:46] 一點問題都沒有
[02:35:47] 我們今天就上到這裡