CODEWITHSUNDEEP
artificial-intelligencea-starsliding-tile-puzzle
msc
msc

Reputation: 67

How to prevent A* search from repeating paths

I am doing the 8-puzzle challenge where I have to arrange the tiles in the right order with the shortest path cost. for my heuristic, I've combined the # of misplaced tiles+ distances of n tile to its goal position.

the goal is

1 2 3
8 0 4
7 6 5

for a puzzle like this

1 2 3 
7 8 4
6 0 5

it works perfectly fine

but with this configuration

1 3 4
8 0 2
7 6 5

it infinitely chooses this combination as the shortest

1)

1 0 4
8 3 2
7 6 5

2)

1 3 4
8 0 2
7 6 5

then 1) then 2)

Upvotes: 2

Views: 103

Answers (1)

Dennis Soemers
Dennis Soemers

Reputation: 8488

If you look at the pseudocode of the algorithm on wikipedia, you'll notice the thing they named closedSet. This is a collection in which you can store states that have already been expanded (states for which the successors have been generated). Then, the loop through all successors (or neighbors in the pseudocode) starts with this:

if neighbor in closedSet
    continue        // Ignore the neighbor which is already evaluated.

The purpose of that piece of code is to prevent exactly your issue from happening.

Note that your choice of data structure for closedSet will significantly impact your algorithm's runtime. It shouldn't be something like a list, where checking if an object is already in it requires looping through the entire list. You'll instead want to look at something like a hash map / set (exact terminology depends on your choice of programming language).

Upvotes: 2

Related Questions