2 - Uninformed Search

Question 1

All ________ problems can be stored in a ________.

Answer 1

All DISCRETE problems can be stored in a DISCRETE GRAPH.

Question 2

________ search might not find a solution in cyclic ________.

Answer 2

TREE search might not find a solution in cyclic GRAPHS.

Question 3

Graph search algorithms ________ nodes.

Answer 3

Graph search algorithms REMEMBER VISITED nodes.

Question 4

Uninformed Search Techniques can only ________ and ________.

Answer 4

Uninformed Search Techniques can only PRODUCE NEXT STATES and CHECK WHETHER THE GOAL STATE IS REACHED.

Question 5

Uninformed Search

Answer 5

There is no additional information besides the problem statement

Question 6

Breadth-First Search (BFS) expands …

Answer 6

…the shallowest nodes first

Question 7

BFS is most commonly implemented as a …

Answer 7

FIFO-Queue

Question 8

BFS: Completeness

Answer 8

BFS is complete if depth and branching factor are finite

Question 9

BFS: Optimality

Answer 9

BFS is not optimal in general ONLY optimal if cost is equal per step

Question 10

BFS: Time/Space Complexity

Answer 10

BFS is O(b^d) time complex and O(b^(d-1)) space complex. For the frontier its space complexity is O(b^d)

Question 11

Uniform-Cost Search (UCS) …

Answer 11

… expands the node with the lowest path cost

Question 12

UCS: Completeness

Answer 12

UCS is complete if costs > 0

Question 13

UCS: Optimality

Answer 13

UCS is optimal if cost >= eps in R+

Question 14

UCS: Time/Space Complexity

Answer 14

TC = O(b^(1+[C*/eps]) = SC

Question 15

Depth-First Search (DFS) expands …

Answer 15

… the deepest unexpanded node First

Question 16

DFS is most commonly implemented as a …

Answer 16

LIFO-Queue

Question 17

DFS: Completeness

Answer 17

DFS is not complete in general ONLY complete if repeated states are avoided and if the state space is finite

Question 18

DFS: Optimality

Answer 18

DFS is NOT optimal

Question 19

DFS: Time/Space Complexity

Answer 19

DFS has EXPONENTIAL time complexity O(b^m) and LINEAR space complexity O(bm)

Question 20

Depth-Limited First Search (DLFS)

Answer 20

Equivalent to DFS but introduces a cutoff limit l

Question 21

DLFS: Completeness

Answer 21

DLFS is complete if l >= d

Question 22

DLFS: Optimality

Answer 22

DLFS is NOT optimal

Question 23

DLFS: Time/Space Complexity

Answer 23

DLFS has EXPONENTIAL time complexity O(b^l) and LINEAR space complexity O(bl)

Question 24

Iterative-Deepening Search (IDS) visits the nodes in the search tree in the same order as ________.

Answer 24

Depth-First Search

Question 25

IDS uses ________ memory as BFS.

Answer 25

IDS uses MUCH LESS memory as BFS.

Question 26

IDS: Completeness

Answer 26

IDS is complete if branching factor b is finite

Question 27

IDS: Optimality

Answer 27

IDS is optimal if all step costs are identical

Question 28

IDS: Time/Space Complexity

Answer 28

IDS has EXPONENTIAL time complexity O(b^d) and LINEAR space complexity O(bd)

Question 29

Bidirectional Search

Answer 29

Technique to vastly improve time performance but is not always applicable

Question 30

Trees are ________ and have a ________.

Answer 30

Trees are RESTRICTED GRAPHS and have a DIRECTION.

Question 31

Can trees contain cycles?

Answer 31

No. Trees don’t contain cycles and can be seen as modified Directed Acyclic Graphs (DAGs)

Question 32

Search algorithms are typically judged by ________.

Answer 32

COMPLETENESS; OPTIMALITY; TIME COMPLEXITY and SPACE COMPLEXITY