The n-puzzle is a known sliding puzzle that consists of a grid of numbered squares with...

  

Transcribed Image Text:

The n-puzzle is a known sliding puzzle that consists of a grid of numbered squares with one square missing (the empty square), and the labels on the squares in a (pseudo-) random order. The goal of the puzzle is to reorder the squares by only making moves which slide squares into the empty space, in turn revealing another empty space in the position of the moved piece. Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the Manhattan distances between each block and its position in the goal configuration. a) Are the above mentioned heuristics admissible? If they are, what is the effect they have in A*? b) Can you devise (or find) any other heuristic for n-puzzle? What would be the value of the heuristic function given the above state as an example? c) Give the following initial state, show how A* will expand the tree in order to reach the goal: 2 3 15 6 478 The n-puzzle is a known sliding puzzle that consists of a grid of numbered squares with one square missing (the empty square), and the labels on the squares in a (pseudo-) random order. The goal of the puzzle is to reorder the squares by only making moves which slide squares into the empty space, in turn revealing another empty space in the position of the moved piece. Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the Manhattan distances between each block and its position in the goal configuration. a) Are the above mentioned heuristics admissible? If they are, what is the effect they have in A*? b) Can you devise (or find) any other heuristic for n-puzzle? What would be the value of the heuristic function given the above state as an example? c) Give the following initial state, show how A* will expand the tree in order to reach the goal: 2 3 15 6 478

Answer rating: 100% (QA)

A Algorithm A is a computer algorithm that is widely used in pathfinding and graph traversal the process of plotting an efficiently traversable path b... View the full answer