Please use your own words to define (a) State; (b) State Graph: (c) Successor Function: (d) Search Node: (e) Node Expansion; and (f) Fringe of a Search Tree (1 pt) 1. 2. A search algorithm requires a data structure to keep track of the search tree that is being constructed. For each node in the search tree, please outline its major data structure (1.0 pt . When moving the empty tile up from S to S in Figure 1, please show the Permutation Inversion relationships for tiles x1, x2, x3, and x4, before and after the empty tile movement for each of the two conditions: (1) xl x2x3 x3>x4; (Tip: check the relationship between n, and n) (0.5 pt). Please explain why the total Permutation Inversions from S to S' is "N mod 2" invariant (0.5 pt) (including the row number of the empty tile) Explain why one can NOT solve the 15 puzzle whose initial layout is showing on the left of Figure 2, and the goal state is showing on the right of Figure 2. (0.5 pt) 56x1 x2 x3 x4 8 13 14 15 12 12 3 4 5 6 x4x1 x2x38 13 14 15 12 Figure 1