0 votes
1 view
in AI and Deep Learning by (19.1k points)

I am learning an A* algorithm on the 8-puzzle problem.

I don't have questions about A*, but have some for the heuristic score - Nilsson's sequence score.

Justin Heyes-Jones web pages - A* Algorithm explains A* very clearly. It has a picture of Nilsson's sequence scores.

image

It explains:

Nilsson's sequence score

A tile in the center scores 1 (since it should be empty)

For each tile not in the center, if the tile clockwise to it is not the one that should be clockwise to it then score 2.

Multiply this sequence by three and finally add the total distance you need to move each tile back to its correct position.

I can't understand the steps above for calculating the scores.

For example, for the start state, what h = 17?

+---+---+---+

|   | A | C |

+---+---+---+

| H | B | D |

+---+---+---+

| G | F | E |

+---+---+---+

So, by following the description,  B is in the center, so we have a score of 1.

Then

For each title not in the center, if the tile clockwise to it is not the one that should be clockwise to it then score 2.

I am not sure what does this statement mean. What does the bolded tile refer to? What does the bolded it refer to? Does the bolded it refers to the center title (B in this example)? Or does it refer to each tile, not in the center?

Is the next step that we start from A, so C should not be clockwise to A, then we have a score of 2. And then B should be clockwise to A, then we ignore, so on so forth?

1 Answer

0 votes
by (42.4k points)

I will answer your question one by one:

  1. The bolded tile refers to the tile on the square. That is the next square round the edge.

  2. The bolded it refers to those tiles which are not in the center.

  3. The next step is given by looking at A.  C should not be clockwise to A, then we have 2. Next, we look at C, D should be clockwise to A, so this is okay. Looking at D, E, F and G all of these are okay, but when we get to H it should not be next to 0, so we have a score of 4. We add 1 because B is in the center to get 5. Then multiply by 3 to get 15. Then add 1 to move B up to the right place, and 1 to move A left to the right place for a final total of 17.

...