#visited-list

Question 1: Single choice

The state graph has a manageable number of states but many cycles, links of varying cost, and no heuristic. You want shortest paths, and the running time should grow with the number of states rather than the number of paths. Which search fits?

Iterative deepening (depth-first) without any list1
Uniform-cost search with a visited list2
Breadth-first search with an expanded list3
Uniform-cost search with a strict expanded list4

Timed test