= Solution
\b[TODO: the classifications, chosen <heuristic functions> and least-cost outcomes for G1–G5 cannot be established from the corrupted original Figure 1.] The missing <edges>, costs, priority labels and lower portions of the five <search trees> are required inputs. The surviving portions and the two <heuristic function> tables do not determine those answers. No reconstructed <graph> or invented expansion trace is assumed.
For a readable instance, <depth-first search> follows the deepest pending branch and <breadth-first search> expands by <search depth>; neither generally minimizes unequal <edge> costs. <Uniform-cost search> orders by <path cost> $g$, whereas <A-star search> orders by $g+h$. A displayed <A-star search> score would identify the estimate by subtracting the accumulated <path cost>. Under nonnegative costs and the usual terminating-search assumptions, <uniform-cost search> returns a least-cost <goal state> when testing goals on removal from the <search frontier>; <A-star search> additionally needs an <admissible heuristic> with appropriate reopening, or a <consistent heuristic> for the usual closed-set implementation. These rules explain how the missing information would be used, but cannot identify a particular damaged <search tree>.
Back to article page
