- DATA.ML.310
- 3. Classical Search and Beyond
- 3.2 Quiz: Classical search

# Quiz: Classical search¶

The sheep and wolves problem is usually stated as follows. Three sheep and three wolves are on one side of a river, along with a boat that can hold one or two creatures. Find a way to get everyone to the other side without ever leaving a group of sheep in one place outnumbered by the wolves in that place. Any animal can steer the boat, and the boat cannot move on its own.

(This problem is famous in AI because it was the subject of the first paper that approached problem formulation from an analytical viewpoint (Amarel, 1968).)

Suppose we formulate the state as a six-tuple, where the first 3 indices hold the number of sheep, wolves, and boats on the first side of the river, and the other 3 hold the numbers on the second side. If the start state is (3,3,1,0,0,0), which of the following are valid goal states

The sheep and wolves problem is usually stated as follows. Three sheep and three wolves are on one side of a river, along with a boat that can hold one or two creatures. Find a way to get everyone to the other side without ever leaving a group of sheep in one place outnumbered by the wolves in that place. Any animal can steer the boat, and the boat cannot move on its own.

(This problem is famous in AI because it was the subject of the first paper that approached problem formulation from an analytical viewpoint (Amarel, 1968).)

In formulating search problems, the first step involves determining what the state is. Which of the following constitute as valid state representations for this problem? Select all that apply.

The sheep and wolves problem is usually stated as follows. Three sheep and three wolves are on one side of a river, along with a boat that can hold one or two creatures. Find a way to get everyone to the other side without ever leaving a group of sheep in one place outnumbered by the wolves in that place. Any animal can steer the boat, and the boat cannot move on its own.

(This problem is famous in AI because it was the subject of the first paper that approached problem formulation from an analytical viewpoint (Amarel, 1968).)

For each of the following search algorithms, can the algorithm be used to solve this problem? Select it if it can.

Is the following statement True or False?

Breadth-first search is complete even if zero step costs are allowed.

Is the following statement True or False?

Greedy best first search guarantees both completeness and optimality.

Consider A* graph search on the graph above. Arcs are labeled with action costs and states are labeled with heuristic values. Assume that ties are broken alphabetically.

What path does A* graph search return?

Consider A* graph search on the graph above. Arcs are labeled with action costs and states are labeled with heuristic values. Assume that ties are broken alphabetically.

In what order are states expanded by A* graph search? You may find it helpful to execute the search on paper.

Consider the state space shown above. If nodes are expanded ascending order, what is the order in which nodes will be visited for BFS with goal state 11.

Consider the state space shown above. If nodes are expanded ascending order, what is the order in which nodes will be visited for depth-limited search with limit 2 and goal state 6.

You control one insect in a rectangular maze-like environment with dimensions MxN, as shown in the figure above. The insect must reach a designated target location X, also known as the hive. There are no other insects moving around.

At each time step, the insect can move into an adjacent square if that square is currently free, or the insect may stay in its current location. Squares may be blocked by walls, but the map is known. Optimality is measured in terms of time steps; all actions have a cost of 1 regardless of whether the insect moves or stays put.

Note: your answer should reflect a general instance of the problem, not necessarily the example map shown.

Which of the following is a minimal correct state space representation?

You control one insect in a rectangular maze-like environment with dimensions MxN, as shown in the figure above. The insect must reach a designated target location X, also known as the hive. There are no other insects moving around.

At each time step, the insect can move into an adjacent square if that square is currently free, or the insect may stay in its current location. Squares may be blocked by walls, but the map is known. Optimality is measured in terms of time steps; all actions have a cost of 1 regardless of whether the insect moves or stays put.

Note: your answer should reflect a general instance of the problem, not necessarily the example map shown.

What is the size of the state space in this problem?

^{2}

^{N}

^{M}

^{MN}

You control one insect in a rectangular maze-like environment with dimensions MxN, as shown in the figure above. The insect must reach a designated target location X, also known as the hive. There are no other insects moving around.

At each time step, the insect can move into an adjacent square if that square is currently free, or the insect may stay in its current location. Squares may be blocked by walls, but the map is known. Optimality is measured in terms of time steps; all actions have a cost of 1 regardless of whether the insect moves or stays put.

Note: your answer should reflect a general instance of the problem, not necessarily the example map shown.

Which of the following heuristics (if any) are admissible? Select all that apply.