雲林SONG

程式設計可以改變您的未來(Programming can change your future)。雲林SONG 全名為雲林軟體工程(SOftware eNGineering)，目標致力於軟體人才的培養並推廣開源軟體落實於資訊教育。程式設計的觀念是軟體產品的基礎，程式碼就像沙子一樣，要紮實，所建立出來的高塔才會穩固。本站也提供資訊教育相關的教學資源。 YunlinSONG stands for Yunlin SOftware eNGineering, offering tutorial for computer programming and promoting open-source software. Teaching resources in information technology education are provided here.

Tree Search: BFS, DFS, Best-First, and A* Search

This example is from MIT OCW Artificial Intelligence.

Consider the tree shown below. The numbers on the arcs are the arc lengths; the numbers

near states B, C, and D are the heuristic estimates; all other states have a heuristic estimate

of 0.

Assume that the children of a node are expanded in alphabetical order when no other order

is speciﬁed by the search, and that the goal is state J . No visited or expanded lists are used.

What order would the states be expanded by each type of search. Write only the sequence

of states expanded by each search.

Breadth First

Setep 1:

Visited: A

Queue: B, C, D

Step 2:

Visited: A, B

Queue: C, D, E, F G

Step 3:

Visited: A, B, C

Queue: D, E, F G, H

Step 4:

Visited: A, B, C, D

Queue: E, F, G, H, I, J

Step 5:

Visited: A, B, C, D, E

Queue: F, G, H, I, J

Step 6:

Visited: A, B, C, D, E, F

Queue: G, H, I, J

Step 7:

Visited: A, B, C, D, E, F, G

Queue: H, I, J

Step 8:

Visited: A, B, C, D, E, F, G, H

Queue: I, J

Step 9:

Visited: A, B, C, D, E, F, G, H, I

Queue: J

Step 10:

Visited: A, B, C, D, E, F, G, H, I, J

Queue:

Path for BFS: A, B, C, D, E, F, G, H, I, J

Depth First

Step 1:

Visited: A

Stack: B, C, D

Step 2:

Visited: A, B

Stack: E, F, G, C, D

Step 3:

Visited: A, B, E

Stack: F, G, C, D

Step 4:

Visited: A, B, E, F

Stack: G, C, D

Step 5:

Visited: A, B, E, F, G

Stack: C, D

Step 6:

Visited: A, B, E, F, G, C

Stack: H, D

Step 7:

Visited: A, B, E, F, G, C, H

Stack: D

Step 8:

Visited: A, B, E, F, G, C, H, D

Stack: I, J

Step 9:

Visited: A, B, E, F, G, C, H, D, I

Stack: J

Step 10:

Visited: A, B, E, F, G, C, H, D, I, J

Stack:

Path for DFS: A, B, E, F, G, C, H, D, I, J

Best-First

Node	h(n)
A	0
B	1
C	6
D	3
E	0
F	0
G	0
H	0
I	0
J	0

Step 1:

Open: A

Close:

Step 2:

Open: B, C, D

Close: A

h(B) = 1 ==> the lowest

h(C) = 6

h(D) = 3

Step 3:

Open: C, D, E, F, G

Close: A, B

h(C) = 6

h(D) = 3

h(E) = 0 ==> the lowest

h(F) = 0

h(G) = 0

Step 4:

Open: C, D, F, G

Close: A, B, E

h(C) = 6

h(D) = 3

h(F) = 0 ==> the lowest

h(G) = 0

Step 5:

Open: C, D, G

Close: A, B, E, F

h(C) = 6

h(D) = 3

h(G) = 0 ==> the lowest

Step 6:

Open: C, D,

Close: A, B, E, F, G

h(C) = 6

h(D) = 3 ==> the lowest

Step 7:

Open: C, I, J

Close: A, B, E, F, G, D

h(C) = 6

h(I) = 0 ==> the lowest

h(J) = 0

Step 8:

Open: C, J

Close: A, B, E, F, G, D, I

h(C) = 6

h(J) = 0 ==> the lowest

Step 9:

Open: C

Close: A, B, E, F, G, D, I, J

Reach the Goal J

Path for Best-First: A, B, E, F, G, D, I, J

A*-Search

Node	h(n)
A	0
B	1
C	6
D	3
E	0
F	0
G	0
H	0
I	0
J	0

Step 1:

Open: A

Close:

Step 2:

Open: B, C, D

Close: A

f(A->B) = h(B) + g(A->B) = 1 + 5 = 6 ==> the lowest

f(A->C) = h(C) + g(A->C) = 6 + 2 = 8

f(A->D) = h(D) + g(A->D) = 3 + 4 = 7

Step 3:

Open: C, D, E, F, G

Close: A, B

f(A->B->E) = f(A->B) + h(E) + g(B->E) = 6 + 0 + 6 = 12

f(A->B->F) = f(A->B) + h(F) + g(B->F) = 6 + 0 + 3 = 9

f(A->B->G) = f(A->B) + h(G) + g(B->G) = 6 + 0 + 4 = 10

f(A->C) = h(C) + g(A->C) = 6 + 2 = 8

f(A->D) = h(D) + g(A->D) = 3 + 4 = 7 ==> the lowest

Step 4:

Open: C, E, F, G, I, J

Close: A, B, D

f(A->D->I) = f(A->D) + h(I) + g(D->I) = 7 + 0 + 6 = 13

f(A->D->J) = f(A->D) + h(J) + g(D->J) = 7 + 0 + 3 = 10 ==> the lowest

Step 5:

Open: C, E, F, G, J

Close: A, B, D, J

Reach the Goal J

Path for A*: A, B, D, J

自製Otto二足機器人

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

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

本站Otto二足機器人相關文章：

Otto 組裝( Assemble Your Own Otto )

Arduino Otto 跳舞機器人( Otto Dancing Robot )

Otto機器人動作之程式碼分析(Otto Source Code Understanding Part I)

Otto機器人動作之程式碼分析2(Otto Source Code Understanding Part II)

Arduino Otto 指令說明Otto Command List

官網 Otto DIY 有很多豐富的資料。

正文開始囉。

筆者試著使用紙箱來自製二足機器人，結果成功了。

電子材料如下：

名稱數量

Arduino Nano 1

NANO UNO 多用擴展板 1

HC-SR04超音波模組 1

SG90伺服馬達 4

5V 有源蜂鳴器 1

usb 線 1

母母杜邦線10公分 10

工具：剪刀、熱熔膠槍等。

筆者是將兩個 SG90伺服馬達用熱溶膠槍給黏在一起。

實際動起來就像這個影片

Otto 大軍照。

Solutions to SQL Zoo practice Part 2

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

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

For solutions to SELECT basics and SELECT from world please refer to Solutions to SQL Zoo practice Part 1.

This post contains solutions to SELECT from nobel.

針對 SQL Zoo (https://sqlzoo.net/wiki/SQL_Tutorial) 這個SQL學習網站的SELECT from nobel練習題，本文提供了一些參考解法。

Solutions to SQL Zoo practice Part 1

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

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

This post contains solutions to SELECT basics and SELECT from world.
針對 SQL Zoo (https://sqlzoo.net/wiki/SQL_Tutorial) 這個SQL學習網站，本文提供了一些參考解法。

SELECT basics