Tree Search(樹狀搜尋)

一、什麼是 Tree Search(樹狀搜尋)? 在人工智慧(AI)與演算法中,許多問題都可以表示成一棵樹(圖一): 起點(A) / | \ B C D /|\ | / \ E F G H I J 每個節點(Node)代表一種狀態(State)。 例如: 迷宮中的位置 棋局的盤面 路徑規劃中的城市 遊戲中的決策 搜尋演算法的目的: 從起點找到目標節點(Goal Node) 二、Breadth First Search (BFS) 核心思想 先搜尋離起點最近的節點。 一層一層往外擴展。 Level 0: A Level 1: B C D Level 2: E F G H I J 搜尋順序: A B C D E F G H I J 圖一結果: A → B → C → D → E → F → G → H → I → J 使用資料結構 Queue(佇列) FIFO: First In First Out 先進先出 例如: Queue: A 取出A 加入B,C,D Queue: B,C,D BFS特性 優點 如果邊權重相同: BFS一定找到最短路徑。 缺點 需要大量記憶體。 假設每個節點有10個子節點: 深度5: 10^5 = 100000 需要保存很多節點。 時間複雜度 O(V + E) V = Vertex(節點數) E = Edge(邊數) 三、Depth First Search (DFS) 核心思想 一路往下走到底。 不能走才回頭。 A | B | E 然後: A | B | F 搜尋順序 圖一結果: A B E F G C H D I J 使用資料結構 Stack(堆疊) LIFO Last In First Out 後進先出 例如: push(B) push(C) push(D) pop() => D DFS特性 優點 記憶體需求小。 只需保存: 目前路徑 即可。 缺點 可能找到很差的解。 例如: A ├── Goal └── 巨大子樹 DFS可能先跑完整個巨大子樹。 時間複雜度 O(V+E)...

Scratch 3 變數與自訂積木

建立變數
點選程式積木區的資料,按下製作一個變數的按鈕,再輸入新變數的名稱。


變數的顯示方式
打勾會顯示變數內容。
有三種顯示方式:正常顯示、大型顯示、滑桿
在變數名稱上用滑鼠左鍵快速連點兩下也可以切換。

全域變數練習
Step 1:開新檔案,刪除貓咪角色。
Step 2:新增變數「吃到幾個水果」
Step 3:新增動物角色,並匯入音效。(可任選動物)
Step 4:新增食物角色,並匯入音效。(可任選食物與音效)
Step 5:設計動物角色程式積木。(下圖為參考,可自由設計)
Step 6:設計食物角色程式積木。(下圖為參考,可自由設計)

Step 7:複製食物角色數個。
恭喜完成了,完一下此遊戲吧。


角色分身
將食物角色的程式修改如下:

建立自訂積木
在動物吃水果遊戲中是否有注意到有重複的程式積木呢?自訂積木可以讓重複的程式積木容易修改與管理。
按下更多積木中的製作一個積木按鈕,輸入新積木的名稱:隨機出現。

將重複的程式積木放到自訂積木中:

將食物角色的程式修改如下:

這樣的程式積木是否有更精簡了?

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

留言

這個網誌中的熱門文章