カテゴリー: algorithm

ダイクストラ法とは、グラフ上の最短経路問題をとくアルゴリズム。↓このページに詳しいアルゴリズムの説明がある。

　cf. ダイクストラ法（最短経路問題） – deq notes

Ruby でやってみた。
例題は、上のページにもあるこのグラフ（ただしノードにつけた番号のせいか上下が逆になっている）。

円（ノード）に番号がふられ、ノードをつなぐ辺（エッジ）にはそこを通るときのコスト（距離とも時間とも解釈できる）が付されている。この中の任意の 2 つのノードをつなぐ最短経路とコストを求めるのが最短経路問題だ。
今回は 0 番のノードをスタートし 5 番のノードをゴールとする最短経路とそのコストを求めてみる。

#!/usr/bin/env ruby
# encoding: utf-8

class Node

  attr_reader :name
  attr_accessor :done, :cost, :from

  def initialize(name)
    @name = name
    @edges = []
    @done = false
    @cost = nil
    @from = nil
  end

  def add_edge(edge)
    @edges << edge
  end

  def each_edge
    @edges.each{|e| yield(e) }
  end

end

Edge = Struct.new(:dest, :cost)

def make_edge(nodes, a, b, cost)
  nodes[a].add_edge(Edge.new(b, cost))
  nodes[b].add_edge(Edge.new(a, cost))
end

nodes = []
0.upto(5) do |i|
  nodes << Node.new(i)
end

edges = [
  [0, 1, 2],    # [node_a, node_b, cost]
  [0, 2, 4],
  [0, 3, 5],
  [1, 2, 3],
  [2, 3, 2],
  [1, 4, 6],
  [2, 4, 2],
  [4, 5, 4],
  [3, 5, 6]
]
edges.each do |a, b, cost|
  make_edge(nodes, a, b, cost)
end

start = 0
goal = 5

start_node = nodes[start]
start_node.cost = 0
start_node.done = true
start_node.each_edge do |edge|
  n = nodes[edge.dest]
  n.cost = edge.cost
  n.from = start_node.name
end

while true do
  done_node = nil
  nodes.each do |node|
    if node.done || node.cost.nil?
      next
    else
      node.each_edge do |e|
        n = nodes[e.dest]
          if n.cost.nil?
          n.cost = node.cost + e.cost
          n.from = node.name
        else
          if node.cost + e.cost < n.cost
            n.cost = node.cost + e.cost
            n.from = node.name
          end
        end
      end
      if done_node.nil? || node.cost < done_node.cost
        done_node = node
      end
    end
  end
  done_node.done = true
  break if nodes.all?{|n| n.done }
end

puts nodes[goal].cost
route = [goal]
begin
  node = nodes[route.first]
  route.unshift(node.from)
end
until route.first == start

 puts route.map(&:to_s).join(" -> ")

実行結果：

takatoh@nightschool $ ruby dijkstra.rb
10
0 -> 2 -> 4 -> 5

というわけで、最短経路は 0 -> 2 -> 4 -> 5、コストは 10 という答えが得られた。これは上のリンク先の答えと同じなので、あっていると思っていいだろう。

ヒープじゃなくて単純な二分木を使ったソート。すなわち、

• 左の子は親よりも小さい
• 右の子は親よりも大きい

という構造。で、これを通りがけ順（左の枝、根、右の枝の順に調べる）に出力すると昇順にソートされる。

class BinaryTree

  def initialize(x)
    @val = x
    @left = nil
    @right = nil
  end

  def insert(x)
    if x < @val
      @left.nil? ? @left = BinaryTree.new(x) : @left.insert(x)
    else
      @right.nil? ? @right = BinaryTree.new(x) : @right.insert(x)
    end
  end

  def traverse(&block)
    @left.traverse(&block) unless @left.nil?
    block.call(@val)
    @right.traverse(&block) unless @right.nil?
  end

end

def sort(ary)
  btree = BinaryTree.new(ary.shift)
  ary.each{|x| btree.insert(x) }
  [].tap{|a| btree.traverse{|v| a << v } }
end

if $0 == __FILE__
  sample = (1..100).to_a.sample(10)
  puts "unsorted: " + sample.inspect
  result = sort(sample)
  puts "sorted:   " + result.inspect
end

takatoh@nightschool $ ruby btree_sort.rb
unsorted: [47, 97, 34, 39, 74, 44, 38, 5, 10, 53]
sorted:   [5, 10, 34, 38, 39, 44, 47, 53, 74, 97]

一昨日は二分木を使ったヒープソートを作った。配列を使ったヒープの構造についてはここのページのヒープの項が分かりやすい。

　cf. 二分木 (binary tree) とヒープ (heap) – Algorithms with Python

二分木のルートを番号 0 として、各ノードに幅優先で左から番号をふっていく。ふった番号を配列の添字だと考えれば、次の関係が成り立つ。
すなわち、親の添字を k とすると：

• 左側の子の添字は 2 * k + 1
• 右側の子の添字は 2 * k + 2

子の添字を k とすると：

• 親の添字は floor((k – 1) / 2)

となる。
これで二分木を配列に置き換えられる。後はやることは基本的に一緒だ。

class Heap

  def initialize
    @heap = []
  end

  def insert(x)
    @heap << x
    upheap
    self
  end

  def shift
    v = @heap.shift
    @heap.unshift(@heap.pop)
    downheap
    v
  end

  def upheap
    k = @heap.size - 1
    j = (k - 1) / 2    # parent of k
    until k == 0 || @heap[j] < @heap[k]
      @heap[j], @heap[k] = @heap[k], @heap[j]
      k = j
      j = (k - 1) / 2
    end
  end

  def downheap
    k = 0
    i = 2 * k + 1    # left child of k
    j = 2 * k + 2    # right child of k
    until @heap[i].nil?    # no children
      if @heap[j].nil? || @heap[i] < @heap[j]
        if @heap[k] < @heap[i]
          break
        else
          @heap[i], @heap[k] = @heap[k], @heap[i]
          k = i
          i = 2 * k + 1
          j = 2 * k + 2
        end
      else
        if @heap[k] < @heap[j]
          break
        else
          @heap[j], @heap[k] = @heap[k], @heap[j]
          k = j
          i = 2 * k + 1
          j = 2 * k + 2
        end
      end
    end
  end

end   # of class Heap

def heap_sort(ary)
  heap = Heap.new
  ary.each{|x| heap.insert(x) }
  result = []
  while y = heap.shift
    result << y
  end
  result
end

if $0 == __FILE__
  ary = (1..100).to_a.sample(10)
  puts "unsorted: " + ary.inspect
  result = heap_sort(ary)
  puts "sorted: " + result.inspect
end

実行例：

unsorted: [15, 70, 93, 27, 5, 8, 26, 40, 74, 67]
sorted:   [5, 8, 15, 26, 27, 40, 67, 70, 74, 93]

[おまけ]

二分木を使ったヒープソート（heap_sort.rb）と今日の配列を使ったヒープソート（heap_sort2.rb)の実行時間の比較をしてみた。

takatoh@nightschool $ time ruby heap_sort.rb
unsorted: [85, 61, 68, 9, 73, 79, 26, 84, 21, 13]
sorted:   [9, 13, 21, 26, 61, 68, 73, 79, 84, 85]

real	0m0.102s
user	0m0.019s
sys	0m0.008s
takatoh@nightschool $ time ruby heap_sort2.rb
unsorted: [65, 26, 92, 51, 33, 31, 61, 97, 34, 57]
sorted:   [26, 31, 33, 34, 51, 57, 61, 65, 92, 97]

real	0m0.034s
user	0m0.017s
sys	0m0.017s

配列を使ったヒープソートのほうが３倍位速い。ま、そうだろうな…と思ったら、user の時間は大して変わらないな。

ヒープソートって配列を使ってやるのがフツウみたいだけど、アルゴリズムのアイデアに忠実に二分ヒープ（木）を使ってやってみた。
参考にしたページはココらへん。

　cf. 二分木 (binary tree) とヒープ (heap) – Algorithms with Python
　cf. 二分ヒープ – ウィキペディア

class Node

  attr_accessor :val, :left, :right
  attr_reader :parent

  def initialize(val, parent = nil)
    @val = val
    @parent = parent
    @left = nil
    @right = nil
  end

end   # of class Node

class HeapTree

  def initialize
    @root = nil
  end

  def insert(val)
    if @root.nil?
      @root = Node.new(val)
    else
      v = vacant
      n = Node.new(val, v)
      if v.left.nil?
        v.left = n
      else
        v.right = n
      end
      upheap(n)
    end
  end

  def shift
    if @root.nil?
      nil
    else
      val = @root.val
      @root.val = delete_last
      downheap(@root)
      val
    end
  end

  def upheap(node)
    until node.parent.nil? || node.val > node.parent.val
      v = node.val
      node.val = node.parent.val
      node.parent.val = v
      node = node.parent
    end
  end

  def downheap(node)
    return nil if node.nil?
    until node.left.nil?
      if node.right.nil? || node.left.val < node.right.val
        if node.val > node.left.val
          v = node.val
          node.val = node.left.val
          node.left.val = v
          node = node.left
        else
          break
        end
      else
        if node.val > node.right.val
          v = node.val
          node.val = node.right.val
          node.right.val = v
          node = node.right
        else
          break
        end
      end
    end
  end

  def vacant
    q = [@root]
    while n = q.shift
      if n.left.nil? || n.right.nil?
        return n
      else
        q << n.left
        q << n.right
      end
    end
  end

  def last
    q = [@root]
    begin
      n = q.shift
      q << n.left if n.left
      q << n.right if n.right
    end until q.empty?
    n
  end

  def delete_last
    node = last
    if node.parent.nil?
      @root = nil
    else
      if node.parent.right == node
        node.parent.right = nil
      else
        node.parent.left = nil
      end
    end
    node.val
  end

end   # of HeapTree


if $0 == __FILE__
  ary = (1..100).to_a.sample(10)
  puts "unsorted: " + ary.inspect
  heap = HeapTree.new
  ary.each do |x|
    heap.insert(x)
  end
  sorted = []
  while v = heap.shift do
    sorted << v
  end
  puts "sorted: " + sorted.inspect
end

なんだかあんまりきれいじゃないけど。特に downheap のあたりが。 とりあえず出来たって感じ。 最初は upheap や downheap でノード自体を入れ替えようとしてたのでもっとひどかった。ノードはそのままにしておいて持っている値だけ入れ替えればいいことに気づいていくらかマシになった。 実行結果：

takatoh@nightschool $ ruby heap_sort.rb
unsorted: [75, 63, 96, 9, 21, 92, 48, 83, 51, 31]
sorted:   [9, 21, 31, 48, 51, 63, 75, 83, 92, 96]

cf. RubyでクイックソートとRSpecでそのテストを書いてみる – 凸ろぐ

なんだかまどろっこしい書き方をしてるなあ。これでいいんじゃないか？

require 'benchmark'

class Array
  def qsort
    return self if self.size <= 1
    pivot = self.shift
    left = self.select{|x| x < pivot }
    right = self.select{|x| pivot <= x }
    return left.qsort + [pivot] + right.qsort
  end
end

ary = [1,2,3,4,5,6,7,8,9,10].shuffle
ary2 = ary.dup

Benchmark.bm(13) do |x|
  x.report("Array#sort: ") { ary.sort }
  x.report("Array#qsort:") { ary2.qsort }
end

takatoh@nightschool $ ruby qsort.rb
                    user     system      total        real
Array#sort:     0.000000   0.000000   0.000000 (  0.000006)
Array#qsort:    0.000000   0.000000   0.000000 (  0.000013)

Array#soft 速いな。やっぱり自前で作るよりあるものを使ったほうがいいってことか。
いや、リンク先の実装だと速いのか？

require 'benchmark'

class Array
  def qsort
    return self if self.size <= 1
    mark = self[0]
    right = Array.new
    left = Array.new
    (1..self.size-1).each do |i|
      if self[i] <= mark
        left.push(self[i])
      else
        right.push(self[i])
      end
    end
    left = left.qsort
    right = right.qsort
    return left + [mark] + right
  end
end

ary = [1,2,3,4,5,6,7,8,9,10].shuffle
ary2 = ary.dup

Benchmark.bm(10) do |x|
  x.report("Array#sort: ") { ary.sort }
  x.report("Array#qsort:") { ary2.qsort }
end

takatoh@nightschool $ ruby qsort2.rb
                 user     system      total        real
Array#sort:   0.000000   0.000000   0.000000 (  0.000006)
Array#qsort:  0.000000   0.000000   0.000000 (  0.000019)

そんなことはなかった。