1 of 16

Chapter4 :Uninformed (Blind)Search

Searching through a state space

Evaluating Search strategies

Search Tree

Breadth First Search (BFS)

Depth first Search

2 of 16

  • Searching through a state space involves the following:
    • A set of states
    • Operators and their costs
    • A Start state
    • A test to check for goal state

​

3 of 16

The basic search algorithm

4 of 16

Which path to find?

  • The objective of a search problem is to find a path from the initial state to a goal state. If there are several paths which path should be chosen?
  • Our objective could be to find any path, or we may need to find the shortest path or least cost path.

5 of 16

Evaluating Search strategies

​

1.Completeness: Is the strategy guaranteed to find a solution if one exists?

2. Optimality: Does the solution have low cost or the minimal cost?

​

3. What is the search cost associated with the time and memory required to find a solution?

​

Time complexity: Time taken

​

Space complexity: Space used

​

6 of 16

search strategies

  • The different search strategies that we will consider include the following:
    • 1. Blind Search strategies or Uninformed search

a. Depth first search

b. Breadth first search

c. Iterative deepening search

d. Iterative broadening search

    • 2. Informed Search
    • 3. Constraint Satisfaction Search
    • 4. Adversary Search

​

7 of 16

We can transform graph to tree for simplicity

No duplicate nodes

No duplicate nodes

8 of 16

Search Tree

  • Root Node: The node from which the search starts.
  • Leaf Node: A node in the search tree having no children.
  • X is an ancestor of Y is either X is Y’s parent or X is an ancestor of the parent of Y. If X is an ancestor of Y, Y is said to be a descendant of X.
  • Branching factor: the maximum number of children of a non-leaf node in the search tree
  • Path: A path in the search tree is a complete path if it begins with the start node and ends with a goal node. Otherwise it is a partial path.

​

Path=A-C-D-F-G

Branching Factor of D =2

9 of 16

Breadth First Search (BFS)

implies the expansion in a FIFO (First In First Out) order.

10 of 16

BFS illustration (Level)

11 of 16

Properties of Breadth-First Search

  • Complete.
  • Breadth first search finds a solution with the shortest path length.
  • The algorithm has exponential time and space complexity.

Suppose the search tree can be modeled as a b-ary tree . Then the time and space complexity of the algorithm is O(bd) where d is the depth of the solution.

12 of 16

Advantages of BFS

Disadvantages

Finds the path of minimal length to the goal.

​

​

Requires the generation and storage of a tree whose size is exponential .

13 of 16

Depth first Search

14 of 16

DFS illustrated

กำหนด Search Space ดังนี้

Initial State = A

Goal State = G

แปลงเป็น

Search Tree

แถวข้อมูลที่ใช้งาน

Search Space

เริ่มกระบวนการค้น

แถวข้อมูลที่ใช้งาน

15 of 16

แถวข้อมูลที่ใช้งาน

แถวข้อมูลที่ใช้งาน

แถวข้อมูลที่ใช้งาน

แถวข้อมูลที่ใช้งาน

16 of 16

If the search tree has infinite depth, the algorithm may not terminate.

  • If the search tree has infinite depth, the algorithm may not terminate.
  • It can also happen if the search space contains cycles. The latter case can be handled by checking for cycles in the algorithm. Thus Depth First Search is not complete.