Admissible heuristics Hello can someone help me with questio

Admissible heuristics

Hello, can someone help me with questions b, c and d please ?

Thank you

Show the solution path (i.e., the sequence of puzzle states from the initial to the goal state) found by each of the following algorithms, assuming transitions have unit cost. You must ensure that puzzle states that have been explored are not added to the search queue. Given multiple states to explore that are otherwise equivalent in priority, the algorithm should prefer the state that involves moving a lower-numbered piece. Breadth first search Uniform cost search Depth first search Iterative deepening b) Suppose now that transitions have differing costs. In particular, the cost of a transition is equal to the number of the piece that is moved (e.g., moving the \"4\" costs 4). If we employ the Manhattan distance heuristic for the original unit cost version of the eight-puzzle presented in class (Lecture 3, slide 13, h_2), would this heuristic still be an admissible heuristic for A* search in the new variant? Justify your answer. Design an admissible heuristic that dominates the heuristic from part b, under the same transition cost scheme as part b. Now consider another variant of the problem in which moving pieces to the left or right costs 2, whereas moving pieces up or down costs 0.5. Would the Manhattan distance heuristic from part b still be admissible? Justify your answer.

Solution

b) The Manhattan Distance heuristic is admissble.

The Manhattan Distance is the distance between two points measured along axes at right angles. The name alludes to the grid layout of the streets of Manhattan, which causes the shortest path a car could take between two points in the city.

if xi(s) and yi(s) are the x and y coordinates of tile i in states, and if upper-line(xi) and upper-line (yi) are the x and y coordinates of tile i in the goal state, the heuristic is:

The limitation of the Manhattan Distance heuristic is that it considers each tile independently, while in fact tiles interfere with each other. Higher accuracy can be achieved by combining other heuristics, such as the Linear Conflict Heuristic.

A* is a kind of search algorithm. It uses a heuristic function to determine the estimated distance to the goal. As long as this heuristic function never overestimates the distance to the goal, the algorithm will find the shortest path, probably faster than breadth-first search would. A heuristic that satisfies that condition is admissible.

Idea:

avoid expanding paths that are already expensive

focus on paths that show promise

Evaluation function f(n) = g(n) + h(n)

g(n) = cost so far to reach n

h(n)= estimated cost from n to goal

f(n) = estimated total cost of path through n to goal

Admissible heuristics are an important class of heuristics because they have several desirable properties in various search algorithms.

The heuristic function h(N) is admissible

if: 0 h(N) h*(N)

An admissible heuristic function is always optimistic

G is a goal node

h(G) = 0