Lecture 3 - Blind Search Strategies

Question 1

What is the objective of a search strategy?

Answer 1

To systematically explore the state space using a search tree

Question 2

When a node is added to the tree, it is ______.

Answer 2

Generated

Question 3

When a node’s children are added to the tree, the node is _______

Answer 3

Expanded

Question 4

What is breadth first search?

Answer 4

Where all nodes at depth n are expanded before moving on to nodes at depth n+1.

I.e. doing rows of the tree before columns

Question 5

What is a search strategy?

Answer 5

A rule for determining which node to expand next

Question 6

What is depth first search?

Answer 6

Most recently generated nodes are expanded first.

i.e. going down the tree before going sideways

Question 7

What does a search strategy determine?

Answer 7

The order in which the tree will be constructed/traversed

Question 8

When the least recently generated node is expanded next, the search strategy is

________ search

Answer 8

breadth first

Question 9

When the most recently generated node is chosen to be expanded next, the search strategy is _________

Answer 9

depth first

Question 10

In depth first search, if a node cannot be expanded and is not the goal state, the search strategy will ____________

Answer 10

backtrack

Question 11

Before a search strategy backtracks, it

a) must remove the just expanded nodes from the unexpanded list
b) must not remove the just expanded nodes from the unexpanded list

Answer 11

a) must remove them

Question 12

Why are depth/breadth first known as blind search strategies?

Answer 12

They do not use any extra information when deciding which node to expand next

Question 13

Blind search is also known as

Answer 13

uninformed search

Question 14

What is the completeness of breadth first search?

Why?

Answer 14

Complete

The program will eventually get to any depth d

Question 15

What is the completeness of depth first search?

Why?

Answer 15

Incomplete

If a search space is infinite the program may never get to the branch with the solution

Question 16

In terms of the number of moves in the solution, which blind search strategy is better and why?

Answer 16

Breadth first is optimal because clearly the first solution encountered has the minimum depth and hence number of moves.

Depth first might find a solution really deep down a branch - not optimal

Question 17

With

branching factor b

Solution depth d from the root

Maximum depth m

What is the time complexity of Breadth First and Depth First searches?

Answer 17

Breadth first:

Max. number of nodes expanded: 1 + b¹ + b² + … + b^d

So worst case time complexity = O(b^d)

Depth first:

Worst case: Solution is last node reached

So worst case time complexity = O(b^m)

Question 18

With

branching factor b

Solution depth d from the root

Maximum depth m

What is the space complexity of Breadth First and Depth First searches?

Answer 18

Breadth first:

All nodes at depth n must be kept in memory prior to expanding n+1

So space complexity = O(b^d)

Depth first:

When backtracking old nodes are not needed so can be discarded

Space complexity: O(bm)

Question 19

What is depth limited search?

Answer 19

A limit is placed on the depth that can be explored before backtracking occurs

Question 20

What is iterative deepening search?

Answer 20

Depth limited search but iterates with increasing limit. So if solution not found with limit m, try m+1

Question 21

What is bidirectional search?

Answer 21

Search from start state to goal state and at the same time, search backwards from goal to start

When the meet, found a solution.

Question 22

What is the time complexity of bidirectional search?

Answer 22

O(b^d/2)

Because each path is going to be half the length (they will meet halfway)

Question 23

What are some possible issues with bidirectional search?

Answer 23

Must be able to easily work backwards

May be many goal states

Must be easy to test whether the searches have met

Question 24

What is uniform cost search based on?

Answer 24

Breadth first

Question 25

What is uniform cost search?

Answer 25

A search where each node has an associated cost

Always expand the cheapest node next

Question 26

How is the cost of a node calculated in uniform cost search?

Answer 26

The sum of the costs of the nodes leading to it