Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CMPT 310 > Solving Problems by Searching > Flashcards

Solving Problems by Searching Flashcards

1
Q

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

A

search tree, search graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

state

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

many

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

incrementally

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

goal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

25

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

36

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A
  • Initial state
  • Actions that can be executed
  • Transition model
  • Goal test
  • Path cost
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

An initial state describes where the ____ starts

A

agent

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

transition

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Describe the basic pseudocode for a tree search

A 
function tree-search(problem)
frontier
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Describe the basic pseudocode for a graph search

A 
function graph-search(problem)
frontier
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A
  • Completeness
  • Optimality
  • Time Complexity
  • Space Complexity
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

To create BFS, we implement frontier as a ______

A

queue

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

complete, optimal, space

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

A

b^d

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

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

A

memory

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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

A

Uniform-cost

19
Q

Uniform-cost search works better than BFS because…

A

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

20
Q

DFS always expands the _______ node in search tree

A

deepest

21
Q

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

A

stack

22
Q

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

A

optimal

23
Q

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

A

space complexity

24
Q

What is depth-limited search?

A

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

25
Q

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

A

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

26
Q

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

A

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

27
Q

What is bidirectional search?

A

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

28
Q

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

A

problem domain

29
Q

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

A

node evaluation

30
Q

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

A

cheapest path from n to a goal

31
Q

What does h(n) = 0 indicate?

A

n is a goal node

32
Q

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

A

Nodes estimated to be closest to the solution

33
Q

Greedy best first search is not ______ and not _______

A

optimal, complete

34
Q

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

A

The cost to reach node n from the root

35
Q

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

A

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

36
Q

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

A

admissible, consistent

37
Q

Admissible heuristics never __________ the cost to reach the goal

A

over-estimates

38
Q

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

A

admissible

39
Q

What does a consistent heuristic guarantee?

A

h(n) only ever increases or stays the same

40
Q

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

A

optimal

41
Q

A* is a kind of ______ ____ search

A

breadth first

42
Q

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

A

IDA, RBFS, SMA

43
Q

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

A

relaxed

44
Q

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

A

pattern database

CMPT 310 (6 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions