Fewest number of turns heuristic

Question

Is there any way to ensure that the fewest number of turns heuristic is met by anything except a breadth-first search? Perhaps some more explanation would help.

 

I have a random graph, much like this:

Starting in the top left corner, I need to know the fewest number of steps it would take to get to the bottom right corner. Each set of connected colors is assumed to be a single node, so for instance in this random graph, the three 1's on the top row are all considered a single node, and every adjacent (not diagonal) connected node is a possible next state. So from the start, possible next states are the 1's in the top row or 3 in the second row.

 

Currently, I use a bidirectional search, but the explosiveness of the tree size ramps up pretty quickly. For the life of me, I haven't been able to adjust the problem so that I can safely assign weights to the nodes and have them ensure the fewest number of state changes to reach the goal without it turning into a breadth-first search. Thinking of this as a city map, the heuristic would be the fewest number of turns to reach the goal.

The fewest number of turns must be the result of this search as that value is part of the heuristic for a more complex problem.

Answer 1

You mentioned that each group of numbers represents one node, and each node is connected to adjacent nodes. Then this is a simple shortest-path problem, and you could use Dijkstra's algorithm, with each edge having weight 1 (for 1 turn). This paper has a slightly faster version of Dijkstra's algorithm, which lowers the constant term. Yet, O(n) though, since you are going to have to look at every node.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.8746&rep=rep1&type=pdf

If you wish to learn about Artificial Intelligence then visit this Artificial Intelligence Course.