(a) The following is a graph of a search problem, where the directed arcs represent the successors of a node. The cost of moving to a node is given by the number on the arc. The value of the heuristic function h is shown inside each node. The start state is S and the goal is G.

For each of the following search strategies, state the order in which states are expanded (use a tree to define the order), as well as the final path returned when the search is finished. Calculate the cost of the final path for each of these algorithms. Assume that all ties are resolved in alphabetical order (i.e., the A state is expanded before the B state which is expanded before the C state, etc.). i. Breadth-first search ii. A*search

b) The following rule base and dynamic input: Rule Base: R1: if a and b then x R2: if c or d then x Dynamic Input: a, with certainty 1.0 b, with certainty 0.8 c, with certainty 0.9 d, with certainty 0.7

Compute the Certainty Factor (CF) for x.