### Best-First Search Strategy

```報告者:陳俊至



Depth-First Search

Hill Climbing

Best-First Search Strategy
Step 1
Step 2
Form a one-element queue consisting of the root node.
Test to see if the first element in the queue is a goal node.
If it is, stop. Otherwise, go to step 3.
Step 3
Step 4
Remove the first element from the queue. Add the first
element’s descendants, if any, to the end of the queue.
If the queue is empty, then failure. Otherwise, go to Step 2.





Breadth-first search (BFS) is a general technique for
traversing a graph
BFS on a graph with n vertices and m edges takesO(n + m )
time

BFS 會使用到Queue (佇列--先進先出) 來紀錄過程中展

A
Queue
B
A
B
D
C
E
D
G
C
E
G
F
F
Output

http://www.cs.bme.hu/~gsala/alg_anims/3/graph2-e.html

http://www.cosc.canterbury.ac.nz/mukundan/dsal/GraphAppl.html


http://www.cs.duke.edu/csed/jawaa2/examples/BFS.html

http://www.rci.rutgers.edu/~cfs/472_html/AI_SEARCH/SearchAnimations
.html
Depth-First Search
Step 1
Step 2
Form a one-element stack consisting of the root node.
Test to see if the top element in the stack is a goal node.
If it is, stop; otherwise, go to step 3.
Step 3
Step 4
Remove the top element from the stack and add the first
element’s descendants, if any, to the top of the stack.
If the stack is empty, then failure. Otherwise, go to Step 2.

 Depth-first search (DFS) is a general techniquefor
traversing a graph
 DFS on a graph with n vertices and m edges takes O(n +
m ) time
 先走訪越深的子節點, 直到該點沒有子節點後,回溯到最

 DFS 會使用到Stack (堆疊—後進先出) 來紀錄過程中展

A
Stack
G
D
E
F
C
B
A
B
D
C
E
G
F

http://www.cs.bme.hu/~gsala/alg_anims/3/graph-e.html

http://www.cosc.canterbury.ac.nz/mukundan/dsal/GraphAppl.html

http://www.ee.ryerson.ca/~courses/coe428/graphs/depth.html

http://www.cs.duke.edu/csed/jawaa2/examples/DFS.html

http://www.rci.rutgers.edu/~cfs/472_html/AI_SEARCH/SearchAnimations
.html
 Hill
Climbing



1. 從搜尋空間中亂數取一點a作為出發點
2. 考慮a點周圍可用的狀態點
3. 取a點周圍最好品質(錯位少)的一點b，並移往b點
4. 重複2～4，直到找不到更好的點
5. 則最後的狀態點就是用Hill Climbing找到的最佳解
6. 若有兩點以上是最好解，則亂數擇一
Hill Climbing並不能保證得到最佳化 solution，但卻可


8-puzzle problem
 Given a initial arrangement and the goal state,
the problem is to determine whether there exists a sequence of
movements from initial state to goal state, where each item can be
moved only horizontally or vertically to the empty spot.
Example:
The initial arrangement and the goal state of the 8-puzzle problem.

Hill Climbing strategy for 8-puzzle problem
◦ Evaluation function f(n) = w(n), where w(n) is # of misplaced
tiles in node n.
◦ The hill climbing strategy is to select the least f(n) to expand
the present node
Ex:
(3)
1, 2, 8 are misplace, f(n)=3

An 8-puzzle problem solved
by a hill climbing method.
1
2
8
7
3
4
6
goal state
5

http://www.rci.rutgers.edu/~cfs/472_html/AI_SEARCH/SearchAnimations
.html

http://www.kramer.me.uk/robin/NetLogo/hill-climbing%20algorithm.html

http://files.bookboon.com/ai/Hill-Climbing-Example-2.html
 Best-First
Search Strategy


Combine depth-first search and breadth-first search.

◦ 當評估函數的準確度愈高，則愈可能找到最佳的節點
◦ 反之，評估函數可能無作用，甚至可能導至錯誤的搜尋。


◦ 若電腦是“ｏ”，對手是“x”


◦ F(x)=同一行及對角線的其他空白個數×1
+同一行及對角線的“ｏ”個數×2 +Y(X)
◦ Y(X)= 0 若該一行及對角線的“x”個數為0
=–1 若該一行及對角線的“x”個數為 1
=2 若該一行及對角線的“x”個數為 2




若由電腦先下，則
◦ F(A1)=(2+2+2) ×1 + (0+0+0) ×2 + (0+0+0) = 6
◦ F(A2)=(2+2) ×1 + (0+0) ×2 + (0+0) = 4
◦ F(A3)=(2+2+2) ×1 + (0+0+0) ×2 + (0+0+0) = 6
◦ F(A4)=(2+2) ×1 + (0+0) ×2 + (0+0) ×2 = 4
◦ F(A5)=(2+2+2+2) ×1 + (0+0+0) ×2 + (0+0+0) = 8
◦ F(A6)=(2+2) ×1 + (0+0) ×2 + (0+0) = 4
◦ F(A7)=(2+2+2) ×1 + (0+0+0) ×2 + (0+0+0) = 6
◦ F(A8)=(2+2) ×1 + (0+0) ×2 + (0+0) ×2 = 4
◦ F(A9)=(2+2+2) ×1 + (0+0+0) ×2 + (0+0+0) ×2 = 6





◦ F(A2)=(1+1) ×1 + (1+0) ×2 + (-1+0) = 3
◦ F(A3)=(1+1+2) ×1 + (0+1+0) ×2 + (-1+0+0) = 5
◦ F(A4)=(1+1) ×1 + (1+0) ×2 + (0-1) = 3
◦ F(A6)=(1+2) ×1 + (1+0) ×2 + (0+0) = 5
◦ F(A7)=(1+1+2) ×1 + (0+1+0) ×2 + (-1+0+0) = 5
◦ F(A8)=(1+2) ×1 + (1+0) ×2 + (0+0) = 5
◦ F(A9)=(0+2+2) ×1 + (0+1+0) ×2 + (0-1+0) = 5






◦ F(A2)=(0+1) ×1 + (1+1) ×2 + (-1+0) = 4
◦ F(A4)=(0+1) ×1 + (0+1) ×2 + (4+0) = 7
◦ F(A6)=(1+1) ×1 + (1+1) ×2 + (0+0) = 6
◦ F(A8)=(1+1) ×1 + (0+1) ×2 + (-1+0) = 3
◦ F(A9)=(1+0+1) ×1 + (0+1+1) ×2 + (-1+0+0) = 5





◦ F(A2)=(0+1) ×1 + (1+1) ×2 + (-1+0) = 4
◦ F(A8)=(1+1) ×1 + (0+1) ×2 + (-1+0) = 3
◦ F(A9)=(1+0+０) ×1 + (0+1+1) ×2 + (-1+0-1) = 3



```