Fewest number of turns heuristic

Question

Is there anyway to ensure the 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:

0 1 1 1 2
3 4 5 6 7
9 a 5 b c
9 d e f f
9 9 g h i

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.

It is very important that the fewest number of turns is the result of this search as that value is part of the heuristic for a more complex problem.

Answer 1

You said yourself each group of numbers represents one node, and each node is connected to adjascent nodes. Then this is a simple shortest-path problem, and you could use (for instance) Dijkstra's algorithm, with each edge having weight 1 (for 1 turn).

Answer 2

This sounds like Dijkstra's algorithm. The hardest part would lay in properly setting up the graph (keeping track of which node gets which children), but if you can devote some CPU cycles to that, you'd be fine afterwards.

Why don't you want a breadth-first search?

Here.. I was bored :-) This is in Ruby but may get you started. Mind you, it is not tested.

class Node
  attr_accessor :parents, :children, :value
  def initialize args={}
    @parents = args[:parents] || []
    @children = args[:children] || []
    @value = args[:value]
  end

  def add_parents *args
    args.flatten.each do |node|
      @parents << node
      node.add_children self unless node.children.include? self
    end
  end

  def add_children *args
    args.flatten.each do |node|
      @children << node
      node.add_parents self unless node.parents.include? self
    end
  end
end

class Graph
  attr_accessor :graph, :root
  def initialize args={}
    @graph = args[:graph]
    @root = Node.new
    prepare_graph
    @root = @graph[0][0]
  end

  private

  def prepare_graph
# We will iterate through the graph, and only check the values above and to the
# left of the current cell.

    @graph.each_with_index do |row, i|
      row.each_with_index do |cell, j|
        cell = Node.new :value => cell #in-place modification!
        # Check above
        unless i.zero?
          above = @graph[i-1][j]
          if above.value == cell.value
            # Here it is safe to do this: the new node has no children, no parents.
            cell = above
          else
            cell.add_parents above
            above.add_children cell # Redundant given the code for both of those
            # methods, but implementations may differ.
          end
        end
        # Check to the left!
        unless j.zero?
          left = @graph[i][j-1]
          if left.value == cell.value
            # Well, potentially it's the same as the one above the current cell,
            # so we can't just set one equal to the other: have to merge them.
            left.add_parents cell.parents
            left.add_children cell.children
            cell = left
          else
            cell.add_parents left
            left.add_children cell
          end
        end
      end
    end
  end
end
     #j = 0, 1, 2, 3, 4
graph = [
         [3, 4, 4, 4, 2], # i = 0
         [8, 3, 1, 0, 8], # i = 1
         [9, 0, 1, 2, 4], # i = 2
         [9, 8, 0, 3, 3], # i = 3
         [9, 9, 7, 2, 5]] # i = 4

maze = Graph.new :graph => graph

# Now, going from maze.root on, we have a weighted graph, should it matter.
# If it doesn't matter, you can just count the number of steps.
# Dijkstra's algorithm is really simple to find in the wild.