スリープ探索

スリープ探索アルゴリズム[Chishow PRESENTS BLOG]
最初は，スリプーソートのインパクトと比べて弱いなーと思ったんだけど，コスト比較とコスト計算が分離できるのは悪くないんじゃなかろうかと思えてきた．

多分，A*とかで書いたほうが早いだろうけども．

スレッド未使用版SleepSortクラス

class SoftSleepSort

  def initialize
    @threads = []
  end

  def push( priority, &block)
    @threads << {:prio => priority, :func => block}
    @threads = @threads.sort_by{|h| h[:prio] }
  end

  def pop
    return if empty?
    h = @threads.shift
    h[:func].call
  end

  def wait_all
    while(not empty?) do
      pop
    end
  end

  def empty?
    @threads.empty?
  end
end

=begin
# 単純なソート
ar = []
1.upto(10){|i| ar << (rand()*100).to_i }

sss = SoftSleepSort.new
ar.each{|x| sss.push(x) { p x} }
sss.wait_all
=end

スリープ探索

# 経路は http://yukirin.dontexist.org/archives/741 から借用
nodes = {
  "s" => {"a" => 5, "b" => 4, "c" => 2},
  "a" => {"s" => 5, "g" => 6, "b" => 2},
  "b" => {"s" => 4, "a" => 2, "c" => 3, "d" => 2},
  "c" => {"s" => 2, "b" => 3, "d" => 6},
  "d" => {"c" => 6, "b" => 2, "g" => 4},
  "g" => {"a" => 6, "d" => 4},
}

start_node = "s"
goal_node = "g"
map_memo = {}

sss2 = SoftSleepSort.new

calc_cost = Proc.new{|total_cost, current_node, route|
  result = false

  if (current_node==goal_node)
    puts "#{total_cost}: #{route.join(' -> ')}"
    result = true
  else
    nodes[current_node].each{|next_node, cost|
      c = total_cost + cost
      c2 = map_memo[next_node]

      # 初めての場所、または既出より短い経路なら探索を行う
      if (c2==nil or c2>c)
        map_memo[next_node] = c
        sss2.push(c) { calc_cost.call( c, next_node, route+[next_node] ) }
      end
    }
  end
  result
}

calc_cost.call( 0, start_node, [start_node] )

# 探索が終了するか、ゴールに到達する経路が出現するまで取り出す。
while(not sss2.empty? and not sss2.pop) do
  ;
end

最初は，無名のプロシージャにするためにYコンビネータを使って書いたけど，別にそんなことする必要なかった．