Grundlagen der künstlichen Intelligenz lecture 3&4-search

What is the maximum number of steps required in graph search?

• The shortest number of edges from the initial state to the goal state

• The number of edges of the graph

• The number of nodes of the graph minus one

Which of these search algorithms are complete? (all path costs are greater than 0, goal is reachable in a finite number of steps)

• Breadth-First Search

• Uniform Cost Search

• Depth First Search

• Depth Limited Search

• Iterative Deepening Search

Which of these search algorithms are optimal? (finite number of nodes, only positive cost)

• Breadth-First Search

• Uniform Cost Search

• Depth First Search

• Depth Limited Search

• Iterative Deepening Search (step cost 1)

The depth d is...

• ..the depth of the shallowest goal node

• ...the depth of the deepest goal node

• ...the depth of the shallowest leaf

• ...the depth of the deepest leaf

What is the branching factor in each direction?

• forwards: 1 backwards: 2

• forwards: 2 backwards: 1

• 2 in both directions

• 1 in both directions

Does a finite state transition graph always lead to a finite search tree? How about a finite state transition graph that is a tree?

• finite in both cases

• infinite for graph, finite for tree

• finite for graph, infinite for tree

• infinite in both cases

Greedy best-first search using tree search; start: Iasi, goal: Faragas. Neamt is first expanded. Next,

• no further node expanded

• Iasis is expanded. Afterwards, Neamt is again expanded due to the closest straight line distance

• Iasis is expanded. Afterwards, Vaslui is expanded, since Neamt has been expanded before

Is greedy best-first search optimal?

• Yes

• No

What is the time complexity of greedy best-first search?

Branching factor b, depth d, maximum length m of any path

• $O\left(b^m\right)$

• $O\left(b^d\right)$

Given the cost C∗ of the optimal path.

Does A* expand nodes, where f (n) ≥ C ∗?

• Yes

• No