Solving Problems by Searching

Question 1

A imagine that our searching is done on a ______ _____ or ______ _____

Answer 1

search tree, search graph

Question 2

A node in the search tree contains the ______ of the environment

Answer 2

state

Question 3

We will usually have _______ nodes in non-trivial search trees

Answer 3

many

Question 4

Since trees are gargantuan, we assume the tree is expanded _________ as we go

Answer 4

incrementally

Question 5

In search trees, we have some way of recognizing ______ nodes

Answer 5

goal

Question 6

It is very difficult to find optimal solution to the __-puzzle

Answer 6

25

Question 7

There is no way to find optimal solution to the __-puzzle

Answer 7

36

Question 8

A problem has at least 5 parts. What are they?

Answer 8

• Initial state
• Actions that can be executed
• Transition model
• Goal test
• Path cost

Question 9

An initial state describes where the ____ starts

Answer 9

agent

Question 10

A __________ model describes how the state changes when an action is applied to it

Answer 10

transition

Question 11

Describe the basic pseudocode for a tree search

Answer 11

function tree-search(problem)
frontier

Question 12

Describe the basic pseudocode for a graph search

Answer 12

function graph-search(problem)
frontier

Question 13

What are the 4 ways in which search algorithm performance is evaluated in?

Answer 13

• Completeness
• Optimality
• Time Complexity
• Space Complexity

Question 14

To create BFS, we implement frontier as a ______

Answer 14

queue

Question 15

BFS is _______ and _______ by definition, but has poor ______ complexity

Answer 15

complete, optimal, space

Question 16

What is the total number of nodes generated in BFS at depth d with branching factor b?

Answer 16

b^d

Question 17

In practice, BFS’ major problem is that it runs out of ______

Answer 17

memory

Question 18

_______-____ Search is BFS but with !1 path costs

Answer 18

Uniform-cost

Question 19

Uniform-cost search works better than BFS because…

Answer 19

BFS stops as soon as it removes a goal from frontier, but Uniform-cost search checks for a goal with a cheaper path cost

Question 20

DFS always expands the _______ node in search tree

Answer 20

deepest

Question 21

DFS’ queue is implemented as a _______ instead of a queue

Answer 21

stack

Question 22

DFS is not ______ because it may find goal nodes further from the root

Answer 22

optimal

Question 23

DFS’ major advantage over BFS is ______ __________ as it only stores one root-to-node path

Answer 23

space complexity

Question 24

What is depth-limited search?

Answer 24

DFS plus a number L that indicates the max depth to be searched

Question 25

What is the pseudocode for iterative deepening depth-first search?

Answer 25

for depth = 0 to infinity: result = depth-limited-search(P, depth) if result != cutoff then return result

Question 26

What is the number of generated nodes for iterative deepening DFS?

Answer 26

N=(d)b+(d−1)b^2+…+(1)b^d = O(b^d)

Question 27

What is bidirectional search?

Answer 27

Simultaneously search forwards from the goal state, and backwards from a goal state

Question 28

Informed search strategies use information about the _______ ______ to find solutions quickly

Answer 28

problem domain

Question 29

A ______ _________ function is usually a part of a heuristic function h(n)

Answer 29

node evaluation

Question 30

A heuristic function h(n) estimates the cost of the....

Answer 30

cheapest path from n to a goal

Question 31

What does h(n) = 0 indicate?

Answer 31

n is a goal node

Question 32

In greedy best first search, which nodes are chosen first?

Answer 32

Nodes estimated to be closest to the solution

Question 33

Greedy best first search is not ______ and not _______

Answer 33

optimal, complete

Question 34

In A* search, what does g(n) specify?

Answer 34

The cost to reach node n from the root

Question 35

In A* search, what does the evaluation function f for frontier look like?

Answer 35

f(n) = g(n) + h(n)

Question 36

In A* search, the heuristic must be ________ and ________

Answer 36

admissible, consistent

Question 37

Admissible heuristics never __________ the cost to reach the goal

Answer 37

over-estimates

Question 38

For tree search problems, A* search is optimal and complete if the heuristic is _______

Answer 38

admissible

Question 39

What does a consistent heuristic guarantee?

Answer 39

h(n) only ever increases or stays the same

Question 40

A*-search is ______ as long as a consistent heuristic is used

Answer 40

optimal

Question 41

A* is a kind of ______ ____ search

Answer 41

breadth first

Question 42

What are 3 memory-efficient variants of A* search?

Answer 42

IDA*, RBFS, SMA*

Question 43

A useful trick for developing admissible heuristics is by considering the ______ version of the problem

Answer 43

relaxed

Question 44

A ________ ______ contains pre-solved, simplified versions of the problem

Answer 44

pattern database