CMSC421: Midterm 1(All accurately solved)

T/F: "A* tree search is not complete if some step costs are equal to zero." correct answers False. If we have finite number of states and avoid cycles/loops, it will be complete. (Me: OHHH I think that it will complete, but it might not be Optimal bc we haven't said anything about whether the heuristic is admissible) T/F: Uniform cost search is complete even if some step costs are equal to zero. correct answers True, assuming we have finite number of states and avoid cycles/loops. A* tree search in a finite state space with strictly positive step costs is optimal if the heuristic function is admissible. correct answers True, admissible heuristics ensure the optimality of A* tree search. T/F: "A* tree search always expands fewer nodes than breadth first search." correct answers False, breadth first search does not consider cost and thus may expand only a few nodes if the cost-optimal path is not the shortest one. T/F: An admissible heuristic, say h1(x), dominates another one, say h2(x), if there exists at least one statex for which h1(x) ≥h2(x). correct answers False, a dominant heuristic requires h1(x) ≥h2(x)∀x. We can design a h1(x) to underesti-mate a few x such that h1(x) ≤h2(x). T/F: Consider a search instance where there are two goal states g1 and g2 reachable from the initial state.Suppose the initial state is strictly closer to g1 than g2. If h(x) is an admissible heuristic, then h(g1) h(g2). correct answers False, we may also have h(g1) = h(g2). T/F: If the minimum step costs are greater than zero, than A* will be complete correct answers True IF THE SPACE IS FINITE AND HAS CYCLE CHECKS A* will find an optimal solution if... correct answers h is admissible (Note from professor: if a heuristic is not admissible, one can show that A* will find a solution (i.e., a path from the start to the goal) that's not optimal. To guarantee optimality, the heuristic has to be optimal.) A* is guaranteed to return a solution (be complete) if either of the following conditions is true: correct answers 1. Finite state space, and we use cycle detection 2. The minimum step cost is greater than zero (hence no infinite path has a finite cost) - ME: bc or else could be on a path for eternity just because its cost was less (but then would never be able to get out of it) (ME: NOTE: in addition, it would be guaranteed to be "optimal" if we had an additional condition: That the heuristic is admissible)