Uninformed Search

Question 1

What does a well-defined search problem consist of?

Answer 1

1. Set of possible states
2. Initial state of the agent
3. Actions (in a given state)
4. Transition Model returns result of action a in state s
5. Goal test checks whether s is a goal state
6. Action cost: cost of applying action a in state s to reach s’

Question 2

Differentiate between incremental formulation and complete-state formulation (Queen problem)

Answer 2

Incremental: Start with an empty chessboard and add a queen at a time.

Complete-state formulation: Start with 8 queens and move them.

Question 3

How to avoid cycles in a search tree?

Answer 3

Only expand nodes that have not been visited before. Reached states are stored in a reached set (known as graph search)

Question 4

How to measure the problem-solving performance of search algorithms? (hint: SCOT)

Answer 4

Space complexity: How much memory is needed to perform the search?
Completeness: Does it guarantee finding a solution if it exists?
Optimality: Does the strategy find the optimal solution? (minimum costs)
Time complexity: How long does it take to find a solution?

Question 5

What’s the difference between informed search and uninformed search?

Answer 5

Uninformed search can only produce next states and check whether it is a goal state because there is no additional information besides the problem statement.

Informed search strategies know whether a state is more promising than another to reach a goal. Informed search uses measures to indicate the distance to a goal.

Question 6

When all step costs are equal, … is optimal because it always…

Uniform-cost search is …, as it expands the node with the lowest path cost g(n) = n.Path-Cost.

This is realized by …

Answer 6

breadth-first; expands the shallowest nodes

optimal for any step costs

storing the frontier as a priority queue ordered by g.

Question 7

Best-first search compared to breadth-first search.

Goal test is applied to a node when it is selected for expansion rather than when it is first generated. Reason: …

A test is added in case a better path to an already reached state is found. Realization: subsequent operations on the lookup table reached.

Answer 7

the first generated goal node might be on a suboptimal path.