Analysis of Algorithm Chapter 10 : State Space

Which state is the root node of State space tree

• Initial state

• Partial solution state

• Goal state

• Terminal state

Which ones are search strategies of state space tree

• Blind search

• Heuristic search

• Binary search

• Linear search

Which kind of state space structure shown in the figure ?

• Enumeration

• Permutation

• Binary counter

• Linear

Based on this state of 15-puzzle problem as shown, which action cannot be performed next ?

• Top

• Down

• Right

• Left

• Every action is valid

Which are differences between Brute force search and Backtracking approach

• Validity verification function on the partial solution

• The number of choices of action

• The direction of search on tree

• The height of state space tree

Which problems are similar based on searching on state space ?

• 0/1 Knapsack

• 15-puzzle

• N-queens

• Sum of subsets

Which one are the correct pairing of checking the solution on N-Queen problem

• checking the uniqueness of col : verifying whether no queen attacking on the vertical line

• checking the uniqueness of i - col[i] : verifying whether no queen attacking on the negative diagonal

• checking the unique of i + col[i] : verifying whether no queen attacking on the negative diagonal

• checking the unique of i - col[i] : verifying whether no queen attacking on the positive diagonal

• checking the unique of i + col[i] : verifying whether no queen attacking on the positive diagonal

How many solutions are there to the n-queens problem when n = 5?