[AI/인공지능] Breadth-First Search, Uniform-Cost Search, Depth-First Sesarch

Uninformed Search - 2/3

 

Organization
<previous post>
1. Formulating Problems
2. Example Problems
3. Searching for Solutions
4. Uninformed Sercha Strategies
      1) Breadth-First Search
      2) Uniform-Cost Search (Dijkstra's algorithm)
      3) Depth-First Search
<next post>
      4) Depth-limited Search
      5) Interative Deepening Search
      6) Bidirectional Serach
5. Comparision and Summary

Uninformed Search vs. Informed Search

Uninformed search

No additional information besides the problem statement is provided

Uninformed search can only produce next states and check whether it is a goal state.

 

Breadth-First Search : BFS 

Idea : Special insatance of the graph-search algorithm. All nodes are expanded at a given depth in the search tree before any nodes at the next leven are expanded.

/ A부터 G까지 중에 어떤 노드가 Goal인지 모른다(uninformed) 이때, 밑으로 내려가며, 왼쪽에서 오른쪽으로 가며 탐색하는 방법이다. 

가장 위쪽인 A부터

 

B와 C에선 왼쪽에 있는 B가 먼저

function BFS returns a solution or failure

node <- a node with State = Problem.Initial-State, Path-Cost = 0 $$
if problem.Goal-Test(node.State) then return Solution(node)
frontier <- a FIFO queue with node as the only element
explored <- an empty set

loop do
        if Empty(frontier) then return failure
       node <- Pop(frontier) /* chooses the shallowest node in frontier* /
       add node.State to explored
       for each action in problem.Actions(node.State) do
             child <- Child-Node(problem, node, action)
             if child.State ist neither in explored nor frontier then
                   if problem.Goal-Test(child.State) then return Solution(child)
                   frontier <- Insert(child, frontier)

 

Auxiliary Algorithm: Child-Node  /보조, 예비 알고리즘

 

function Child-Note (problem , parent, action) returns a node

return a node with
     State = problem.Result(parent.State, action)
     Parent = parent
     Action = action
     Path-Cost = parent.Path-Cost
                                      + problem.Step-Cost(parent.State, action) 

 

Breadth-First Search Perfomance

 

• the branching factor  \( b \)  (maximum number of successors of any node),
• the depth  \( d \)  (depth of the shallowest goal node),
• the maximum length \( m \) of any path in the state space.

BFS의 성능을 지난 포스트에 언급한 4가지 기준들로 조사해본다.

• Completeness? : yes, if depth \( d \) , branching factor \( b \) are finite.

/ 모든 노드들을 탐색하기 때문에 정답을 보장한다.

• Optimality? : not optimal in general; but, if cost is equal per step, then yes

/ 만약 goal이 여러개이거나, 각각의 Step에 대항하는 비용이 같을 경우, 그러나 일반적으로는 아니다.

• Time complexity? : The worst case is that each node has \( b \) successors. then

$$ b + b^2 + ... + b^d = \mathcal{O}(b^d) $$

/ BFS의 취약점은 Time complexity이다. 시간이 너무 오래걸린다. 

• Space complexity: All explored nodes are  \( {O}(b^{d-1})  \) and all nodes in the frontier are \( {O}(b^d) \)

 

Uniform-Cost Search (aka Dijkstra's algorithm)

 

Idea : 가장 적은 비용으로 탐색하는 방법, BFS에서 비롯되었다.

• When all step costs are equal, BFS is optimal because it always expands the shallowest nodes.
• Uniform-Cost search ist optimal when it expands the node with the lowest path cost \( g(n) \).

Example for Holiday in Romania

 

이것을 Tree 형태로 나타내면 아래와 같이 표현된다. 

 

여기서부터 BFS처럼 위에서부터 아래로 진행되지만 비용이 더 적은 것을 선택한다. R은 80, F는 99이므로 R을 선택한다. 비용은 거리를 나타낸다.

그 아래로 내려갈수록 비용은 누적된다. 

Uniform-Cost Search Perfomance

 

• the cost  \( C* \)  of the optimal solution
• the minimum step-cost \( \epsilon \)

UCS의 성능을 지난 포스트에 언급한 4가지 기준들로 조사해본다.

• Completeness? : Yes 

/ 모든 노드들을 탐색하기 때문에 정답을 보장한다.

• Optimality? : Yes (BFS에서 옵티멀하게 발전된 케이스,,)
• Time complexity? : 

$$ O(b^{1+C*/{\epsilon}}) $$

• Space complexity: Equals time complexity since all nodes are stored.

/ 모든 노드들을 다 탐색해야 하므로 time  complexity와 같다.

 

 

 

Depth-First Search

Idea : 가장 깊은 왼쪽 노드부터 탐색한다.

 ㅇ

 

Order : A -> B -> D -> H -> I -> E -> J -> K -> C -> F -> L -> M -> G -> N -> O

 

 

Remind : Branching factor \( b \) , depth  \( d \), maximum length  \( m \) of any path.

 

Depth-First Search Perfomance

• Remind : Branching factor \( b \) , depth  \( d \), maximum length  \( m \) of any path.

DFS의 성능을 지난 포스트에 언급한 4가지 기준들로 조사해본다.

• Completeness? : No, 노드의 갯수가 무한할땐 보장하지 못한다.

• Optimality? : No, 예를들어 정답이 여러개 이고, 그 중 하나가 C라고 가정할 경우 BFS가 훨씬 빠르다.
• Time complexity? : 기본적으로 모든 노드를 다 탐색하므로 시간이 길게 걸리지만 BFS보다는 살짝 빠르다.

$$ O(b^{m}) $$

                              Reminder: BFS has \( {O}(b^d)\) and \( d \leq m \)

• Space complexity: The length of longest path = m. 
  For each node, you have to store its siblings so that when you have visited all the children, 

and you come back to a parent node, you can know which sibling to explore next. 

/ 한 부모 아래의 모든 자식들을 탐색하고 다시 부모로 올라왔을 때 다음 탐색할 것이 무엇인지 알수 있도록 형제를 저장해야 한다.  그러므로 경로 아래의 \( m \) 노드에 대해 추가로 \( b \)노드를 저장한다. \( O(bm) \)