4
$\begingroup$

Consider two heuristics $h_1$ and $h_2$ defined for the 15 puzzle problem as:

  1. $h_1(n)$ = number of misplaced tiles
  2. $h_2(n)$ = total Manhatten distance

15 Puzzle

Could anyone tell why $h_2$ is a better heuristic than $h_1$? I would like to know why the number of nodes generated for $h_1$ is greater than that for $h2$. Also why going deeper into the state space the number of nodes increase drastically for both heuristics.

Source: Informed Search

Improve this question
$\endgroup$
1
  • $\begingroup$ I find that Manhattan Distance is confusing to think about for this problem, because it refers to a grid, and this problem is visually a grid, but that fact is irrelevant to computing M.D. between a given state and the goal state. $\endgroup$
    – ryanwebjackson
    Commented Oct 10, 2022 at 2:31

3 Answers 3

Reset to default
5
$\begingroup$

There probably will be no formal proof; probably the only way to tell which is better is through experiments.

But some intuition seems possible. $h_1$ only takes into account whether a tile is misplaced or not, but it doesn't take into account how far away that tile is from being correct: a tile that is 1 square away from its ultimate destination is treated the same as a tile that is far away from where it belongs.

In contrast, $h_2$ does take this information into account. Instead of treating each tile as either "correct" or "incorrect" (a binary decision), $h_2$ introduces shades of grey that take into account how far the tile is from where it belongs. It seems plausible that this might possibly yield some improvement.

Of course, the only way to find out which one actually works better is to try the experiment. But this might give some intuition about why one might reasonably hope that $h2$ could be potentially be better than $h_1$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ :Okay that might be good for why 'Manhattan distance' is a better heuristic compared to the other but could you tell why the number of nodes generated by $h1(n)$ is greater than the other.Since in slide 27 of the source:1drv.ms/1zpYA3l it tells that $h2(n)>h1(n)$. Does that mean _if the heuristic value($h1(n)$) is greater than another then the number of nodes generated by that heuristic would always be low compared to the other? $\endgroup$
    – justin
    Commented Jan 31, 2015 at 8:58
  • $\begingroup$ @justin, yes. (Here's a thought experiment for you to try: if you had to devise a criterion/definition for which one counts as better, what criterion would you use?) $\endgroup$
    – D.W. ♦
    Commented Jan 31, 2015 at 9:00
  • $\begingroup$ :I would certainly use the heuristic that has a minimum number of states because that would allow to search faster for the goal state. $\endgroup$
    – justin
    Commented Jan 31, 2015 at 9:03
  • $\begingroup$ :If the state space is large whether we could get a goal state easily or whether it would be difficult? $\endgroup$
    – justin
    Commented Feb 2, 2015 at 11:07
4
$\begingroup$

The current answers are good, but I think I have a simpler way to understand it. The Manhattan Distance heuristic approximates the actual distance better than the misplaced tiles heuristic. So, you can think of the actual number of moves it would take as the perfect heuristic (at that point it stops being a heuristic). Like Daniil Agashiyev said, the lowest the Manhattan distance huristic can possibly be is equal to the misplaced tile heuristic. Since both are admissible, that means they both underestimate the true distance. So, the estimations are closer to the actual for Manhattan distance heuristic since it is grater then $H_1$ and less than the actual (let’s call it $H^*$). This is the better heuristic definitively, and it can be formally proven.

$$H_1 \leq H_2 \leq H^*.$$

The reason it will generate less nodes in the search tree is because it will be able to approximate which nodes to explore next better than the misplaced tile heuristic. This is related to $H_1\leq H_2\leq H^*$. Of all the nodes unexplored, the one to select next is decided by the cost estimated by the heuristic. Therefore, the $H_2$ heuristic will provide you a better selection criterion on what to move next. At $H_2$’s worst case, it’ll be equal to $H_1$. For example, beginning at the start state, all the next moves possible will have equal cost with $H_1$. This is because no tile can be placed in the right location in one move. For $H_2$ there will be an order to the next moves, so you can still look one by one, but in an order that can only help.

Also why going deeper into the state space the number of nodes increase drastically for both heuristics.

I think you mean going deeper down the search tree? This is because A* is based off Breadth first search, the number of nodes expand exponentially as you explore more nodes.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I'm not sure it's really helpful to think of A* as being based on BFS. In one sense, it's true that BFS, DFS, UCS and A* are "the same" algorithm, except that BFS uses a queue to store the unexplored nodes, DFS uses a stack, UCS uses a priority queue based on cost and A* uses a priority queue based on cost plus heuristic. But the choice of data structure is more than just an implementation detail and they all behave rather differently in many situations. $\endgroup$
    – David Richerby
    Commented Oct 17, 2017 at 8:08
  • 2
    $\begingroup$ Thanks for the warm welcome. You are right. Rather than the algorithm's implementation, I was hoping to draw parallels with BFS in the way the search tree expands. If you can re-word it better in an answer, I will happily change it. $\endgroup$
    – Mo Azim
    Commented Oct 18, 2017 at 21:51
1
$\begingroup$

$h_1(n) \leq h_2(n)$ because if a tile is misplaced, it will add value of 1 to the total heuristic evaluation, while its Manhattan distance will be at least 1. If it's not misplaced, both are 0.

$h_2(n) \leq h^*(n)$ because each transition will change the Manhattan distance of only one tile and each tile will have to move at least its Manhattan distance to the goal state.

Now the answer to the question why $h1$ expands more nodes than $h2$ when $h_1(n) \leq h_2(n) \leq h^*(n)$, has been given before:
Why is it the lower the h(n) cost the more nodes need to be expanded in A*?

Improve this answer
$\endgroup$
18
  • $\begingroup$ :Could you tell me why $h_2(n) \leq h^*(n)$.Is it because $h^*(n)$ includes the cost of depth towards the goal state ($g(n)$)? $\endgroup$
    – justin
    Commented Feb 3, 2015 at 11:27
  • 1
    $\begingroup$ $h^*(n)$ represents the actual distance from node $n$ to goal node. $g(n)$ is distance traveled from start node to node $n$. So I'm not sure what you mean. But to answer the question, it's because the distance each tile will actually travel to its goal state will be at least the Manhattan distance. $\endgroup$
    – Daniil Agashiyev
    Commented Feb 3, 2015 at 22:46
  • $\begingroup$ :Are both $h_2(n)$ and $h^*(n)$ heuristics or whether only $h_2(n)$ is an heuristic? $\endgroup$
    – justin
    Commented Feb 4, 2015 at 7:18
  • $\begingroup$ For any node n in the state space $h^*(n)$ denotes the actual cost of reaching the goal from $n$. $\endgroup$
    – Daniil Agashiyev
    Commented Feb 4, 2015 at 23:02
  • $\begingroup$ :Okay.But whether $h^*(n)$ is an heuristic.If yes by this do you meant to say that every function is an heuristic? $\endgroup$
    – justin
    Commented Feb 5, 2015 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.