3.14 Which of the foloowing are true and which are false? Explain your answers.

Question

3.14 Which of the foloowing are true and which are false? Explain your answers.
a. Depth-first search always expands at least as many notes as A* search with an admissible heuristic.
b. h(n) = 0 is an admissible heuristic for the 8-puzzle.
c. A* is of no use in robotics because percepts, states, and actions are continuous.
d. Breadth-first search is complete even if zero step costs are allowed.
e. Assume that a rook can move on a chessboard any number of squares in a straight line, vertically or horizontally, but cannot jump over other pieces. Manhattan distance is an admissible heuristic for the problem of moving the rook from square A to square B in the smallest number of moves.

3.21) Prove each of the following statements, or give a counterexample:
a. Breadth-firrst search is a special case of uniform-cost search.
b. Depth-first search is a special case of best-first search.
c. Uniform-cost search is a special case of A* search

Explanation / Answer

Dear user,
3.14)
a) FALSE, depth-first search always expands at least as many nodes as A* search with an admissible heuristic. Because depth-first search always expands the deepest node in the current frontier of the search tree tree and backtracking search uses still less memory. So, depth-first search may possible some times only, but expand fewer nodes than A* search with an admissible heurist. Admissible heuristic is one that never overestimates the cost to reach the goal.

b) TRUE, h(n)=0 is an admissible heuristic for the 8-puzzle. As a heuristic function that never overestimates the number of steps to the goal. Here h(n)=0 is an admissible heuristic because in 8-puzzle have any tile that is out of place must be moved at least once.

C)FALSE, A* is often commonly used in percepts, states, and actions are continuous.

d) TRUE, because if the shallowest goal node is at some finite depth d, breadth-first search will eventually find it after generating all shallower nodes( provided the branching factor b is finite). Breadth-first is optimal if the path cost is a nondecreasing function of the depth of the node.

Imagine searching a uniform tree where every stat has b successors. The root of the search tree generates b nodes at the first level, each of which generates b more nodes, for a total of b2 at the second level and so on. Now suppose that the solution is at depth d. In the worst case, the total number of nodes generates is b+b2+…bd=0(bd).

e) FALSE, Manhattan tiles cannot move along diagonals, the distance count the sum of the horizonatal and vertical distances. Here rook can move on a chessboard any number of squares in a straight line, vertically or horizonatally. So, a rook may cover several squares in a single move. It is not possible in admissible heuristic.

NOTE: One question per one post regarding cramster rules....

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.