【Ruby】【アルゴリズム】ガーベッジコレクションの実装。不正な状態遷移を見つける。ダイクストラ法。

　
「有限オートマトン」についてググっていたときに面白そうな問題を見つけたよ。
有限オートマトンとは関係ない話だけれど、勉強になりそうなのでチャレンジ。
　
（注）
メモリに配慮した実装方法はこちら。
（10月9日追記）
　

問題

状態、'0'および、'A'～'I'に対して、
以下の状態遷移が定義されているとする。
'0'→'A'
'A'→'B'
'B'→'C'
'C'→'B'
'C'→'A'
'D'→'B'
'D'→'H'
'H'→'D'
'E'→'F'
'F'→'G'
'G'→'F'
'G'→'E'
'I'→'I'
この状態遷移は間違っており、遷移しない状態が存在する。
遷移しない状態を求めるプログラムを作成せよ。
ここで、'0' は開始状態である。

http://d.hatena.ne.jp/a-san/20090623/p1

考え方

n次行列にデータを整理して、到達可否を再帰で取得すればOK。

行列を使わないやり方は出来ないかなー、と考えてみたものの思いつかず。

行列の使い方にしても、行列を正規化して
上三角・下三角に分ければたぶんもっとスマートに解けると思う。
そこまでは知識足らずで出来ず。

　
到達可否・行列を使うやり方は前にやったから余裕！
http://sekai.hateblo.jp/entries/2013/09/16
ダイクストラ法。

n次正方行列をn+1正方行列に拡大する方法

Matrixクラス・ArrayクラスのRDocには見つからず。
そもそも次元の拡大自体、数学的発想ではないから仕方ないかな。

あきらめて自作する。
すぐに実装できた。。。探してた時間のほうが長い。まあ仕方ない。

def extension(arr) # n次正方行列をn+1正方行列に拡大
  return [[1]] if arr.length == 0
  arr.each{|row| row << 0}
  arr << Array.new(arr.length+1, 0)
  arr[arr.length-1][arr.length-1] = 1
  arr
end

与えられる情報

datas =[
  ['start', 'A'],
  ['A', 'Banana'],
  ['Banana', 'Car'],
  ['Car', 'Banana'],
  ['Car', 'A'],
  ['D', 'Banana'],
  ['D', 'H'],
  ['H', 'D'],
  ['E', 'F'],
  ['F', 'G'],
  ['G', 'F'],
  ['G', 'E'],
  ['I', 'I']
]

情報の行列化

def matrix(datas) #到達情報を行列化
  key = []; arr = []
  datas.each do |from, to|
    if !key.include?(from)
      key << from 
      arr = extension(arr)
    end
    if !key.include?(to)
      key << to 
      arr = extension(arr)
    end
    arr[key.index(to)][key.index(from)] = 1
  end
  [key, arr]
end

到達可否を取得

def reach?(key, arr, from, to)
  return true if from == to
  key.length.times do |i|
    if arr[i][from] == 1 && i > from #i==fromは除外 ,i<fromはすでに調査済みのため調べない
      return reach?(key, arr, i, to) 
    end
  end
  false
end

コード全量

def extension(arr) # n次正方行列をn+1正方行列に拡大
  return [[1]] if arr.length == 0
  arr.each{|row| row << 0}
  arr << Array.new(arr.length+1, 0)
  arr[arr.length-1][arr.length-1] = 1
  arr
end

def matrix(datas) #到達情報を行列化
  key = []; arr = []
  datas.each do |from, to|
    if !key.include?(from)
      key << from 
      arr = extension(arr)
    end
    if !key.include?(to)
      key << to 
      arr = extension(arr)
    end
    arr[key.index(to)][key.index(from)] = 1
  end
  [key, arr]
end

def reach?(key, arr, from, to)
  return true if from == to
  key.length.times do |i|
    if arr[i][from] == 1 && i > from #i==fromは除外 ,i<fromはすでに調査済みのため調べない
      return reach?(key, arr, i, to) 
    end
  end
  false
end

def solve(key, arr)
  not_achieved = []
  key.length.times do |i|
    not_achieved << key[i] if !reach?(key, arr, 0, i)
  end
  not_achieved
end
datas =[
  ['start', 'A'],
  ['A', 'Banana'],
  ['Banana', 'Car'],
  ['Car', 'Banana'],
  ['Car', 'A'],
  ['D', 'Banana'],
  ['D', 'H'],
  ['H', 'D'],
  ['E', 'F'],
  ['F', 'G'],
  ['G', 'F'],
  ['G', 'E'],
  ['I', 'I']
]
key, arr = matrix(datas)

p solve(key, arr)

#理解用
p key
p arr

　
■実行結果

["D", "H", "E", "F", "G", "I"]
["start", "A", "Banana", "Car", "D", "H", "E", "F", "G", "I"]
[[1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 0, 1, 0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 0, 0, 0, 0, 0], [0, 0, 1, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 1, 0], [0, 0, 0, 0, 0, 0, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0, 0, 1, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 1]]

素朴なやり方なんだろうな。