概要
具体的に出来ること
- じゃんけんのような相対的に勝ち負けが決まるデータのソート。
- 干支のように延々ループするデータを相対的に次のノードへアクセス。
- 複数の歯抜け配列から共通項を頼りに順序を保ってひとつの配列にマージ。
- 左右双方向に繋げば、無向グラフとして全域木の経路探索も可能。
具体例
じゃんけん
leftのノードに負けて、rightのノードに勝つ、という上下関係。
3つのノードはループしているので右にも左にも経路はあるが、もっとも近いノード(隣接しているノード)を直接的な勝敗とする。
root = HighLow::Root.new([ ["グー", "チョキ"], ["チョキ", "パー"], ["パー", "グー"], ]) puts "グーからパーへの経路" routes = root.traceroutes("グー", "パー") routes.each {|route| puts "方向=#{route.direction}, 距離=#{route.metric}, 経路=#{route.nodes.map(&:value)}" } puts left = root.node("グー") 10.times { right = left left = left.next_lefts.first puts "#{right.value}に勝つのは#{left.value}" }
実行結果。
グーからパーへの経路 方向=left, 距離=1, 経路=["グー", "パー"] 方向=right, 距離=2, 経路=["グー", "チョキ", "パー"] グーに勝つのはパー パーに勝つのはチョキ チョキに勝つのはグー グーに勝つのはパー パーに勝つのはチョキ チョキに勝つのはグー グーに勝つのはパー パーに勝つのはチョキ チョキに勝つのはグー グーに勝つのはパー
干支
ループするデータ。
leftのノードは過去、rightのノードは未来、という上下関係。
metric(デフォルトではhop数)で何年の差があるかを算出できる。
root = HighLow::Root.new([ ['子', '丑', '寅', '卯', '辰', '巳', '午', '未', '申', '酉', '戌', '亥', '子'] ]) src = '卯' dst = '申' left_route = root.left_traceroutes(src, dst).first right_route = root.right_traceroutes(src, dst).first shortest_route = root.shortest_routes(src, dst).first puts "#{src}年を基準に前の#{dst}年は、#{left_route.metric}年前" puts "#{src}年を基準に次の#{dst}年は、#{right_route.metric}年後" sign = shortest_route.direction==:left ? '前' : '後' puts "#{src}年を基準に一番近い#{dst}年は、#{shortest_route.metric}年#{sign}"
実行結果。
卯年を基準に前の申年は、7年前 卯年を基準に次の申年は、5年後 卯年を基準に一番近い申年は、5年後
複数の歯抜け配列から共通項を頼りに順序を保ってひとつの配列にマージ
文殊の知恵的なマージ。
複数のソートされた配列を共通項を元にマージする。
branchなし、loopなしの一番シンプルな例。
一概にソートできない場合は、渡したProcでオーダーを決める。
alphabets = [] alphabets << [:a, :c, :e] alphabets << [:a, :b, :d] alphabets << [:c, :d, :e] alphabets << [:e, :f] alphabets << [:b, :c, :f] pp RelativeComparison.merge(alphabets) {|a,b| puts "unknown order: #{a} #{b}" 0 }
実行結果。
[:a, :b, :c, :d, :e, :f]
一概にソートできないbranchありの例。
data = [] data << [:a, :b, :d] data << [:a, :c, :d]
このような場合だと、以下2つの式が成り立つ。
- a < b < d
- a < c < d
bとcの比較は出来ないのでProcが呼ばれる。
出世魚の名前を辿る
地域ごとのブリの稚魚の名前を辿る。
a = [] a << ['アオコ', 'イナダ', 'ワラサ', 'ブリ'] a << ['ワカシ', 'イナダ', 'ワラサ', 'ブリ'] a << ['ワカナゴ', 'イナダ', 'ワラサ', 'ブリ'] a << ['ツバス', 'ハマチ', 'メジロ', 'ブリ'] a << ['ツバイソ', 'フクラギ', 'ガンド', 'ブリ'] a << ['コゾクラ', 'フクラギ', 'ガンド', 'ブリ'] a << ['ツバス', 'ハマチ', 'マルゴ', 'ブリ'] a << ['ツバス', 'ヤズ', 'ワラサ', 'ブリ'] def print_prev_names(node) lefts = node.next_lefts return if lefts.length==0 puts "#{node.value}のひとつ前の名前は#{lefts.length}個" p lefts.map(&:value) puts lefts.each {|left| print_prev_names(left) } end root = RelativeComparison::Root.new(a) node = root.node('ブリ') print_prev_names(node) puts puts "ツバスからブリへの経路" root.traceroutes('ツバス', 'ブリ').each {|route| p route.nodes.map(&:value) }
実行結果。
ブリのひとつ前の名前は4個 ["ワラサ", "メジロ", "ガンド", "マルゴ"] ワラサのひとつ前の名前は2個 ["イナダ", "ヤズ"] イナダのひとつ前の名前は3個 ["アオコ", "ワカシ", "ワカナゴ"] ヤズのひとつ前の名前は1個 ["ツバス"] メジロのひとつ前の名前は1個 ["ハマチ"] ハマチのひとつ前の名前は1個 ["ツバス"] ガンドのひとつ前の名前は1個 ["フクラギ"] フクラギのひとつ前の名前は2個 ["ツバイソ", "コゾクラ"] マルゴのひとつ前の名前は1個 ["ハマチ"] ハマチのひとつ前の名前は1個 ["ツバス"] ツバスからブリへの経路 ["ツバス", "ハマチ", "メジロ", "ブリ"] ["ツバス", "ハマチ", "マルゴ", "ブリ"] ["ツバス", "ヤズ", "ワラサ", "ブリ"]
ブリの名前は以下を参照。
http://jsnfri.fra.affrc.go.jp/kids/buri/kw6.html
全域木の経路探索
ノードを双方向に繋いで、無向グラフとする。
metricを指定することでOSPFのようにコストをmetricとすることが出来る。
無指定であればRIPと同じHop数がmetricとなる。
def regist_bi(root, left, right, metric) root.regist_pair(left, right, metric: metric) root.regist_pair(right, left, metric: metric) end root = RelativeComparison::Root.new regist_bi(root, :left_node, :top_node, 5) regist_bi(root, :left_node, :center_node, 4) regist_bi(root, :left_node, :left_bottom_node, 2) regist_bi(root, :top_node, :center_node, 2) regist_bi(root, :top_node, :right_node, 6) regist_bi(root, :center_node, :left_bottom_node, 3) regist_bi(root, :center_node, :right_bottom_node, 2) regist_bi(root, :left_bottom_node, :right_bottom_node, 6) regist_bi(root, :right_bottom_node, :right_node, 4) shortest_route = root.shortest_routes(:left_node, :right_node).first puts "hop count: #{shortest_route.hop_count}" puts "total metric: #{shortest_route.metric}" puts puts "routes (metric)" puts shortest_route.map {|hop| "#{hop.node.value} (#{hop.metric})" }.join(" => ")
実行結果。
hop count: 3 total metric: 10 routes (metric) left_node (0) => center_node (4) => right_bottom_node (2) => right_node (4)
最短経路アルゴリズムは実装していないが、このローカルにあるこの程度のデータなら何の問題もない。
今後高速化の必要性を感じたらダイクストラ法やら何やらを実装しようと思う。
全域木図は以下を参照。
http://www.deqnotes.net/acmicpc/dijkstra/
あとがき
RubyGemsは気が向いたらやる。
