これは、ダイクストラのアルゴリズムのように聞こえます。最も困難な部分は、グラフを適切に設定すること (どのノードがどの子を取得するかを追跡すること) にありますが、そのために CPU サイクルをいくらか当てることができれば、その後は問題ありません。
幅優先検索をしたくないのはなぜですか?
ここ..私は退屈していました:-) これはRubyで書かれていますが、あなたが始めることができるかもしれません. 注意してください、それはテストされていません。
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.