ダイクストラ法

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

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

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

g

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

実行結果:

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

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

g1

文字列間のレーベンシュタイン距離を求める

レーベンシュタイン距離というのを知った。

Wikipedia のレーベンシュタイン距離の項によると:

レーベンシュタイン距離(レーベンシュタインきょり)は、二つの文字列がどの程度異なっているかを示す距離(距離空間を参照)である編集距離(へんしゅうきょり)の一種類である。具体的には、文字の挿入や削除、置換によって、一つの文字列を別の文字列に変形するのに必要な手順の最小回数として与えられる。名称は、1965年にこれを考案したロシアの学者ウラジミール・レーベンシュタインにちなむ。

だそう。上記ページに擬似コードによる実装例が載ってるのと、次のページの Python での実装例が参考になった。なので JavaScript でやってみた。

 cf. 編集距離 (Levenshtein Distance) – naoyaのはてなダイアリー

実行例:

takatoh@nightschool $ ./ld.js apple play
4
takatoh@nightschool $ ./ld.js perl pearl
1

二分木を使ったソート

単純な二分木を使ったソート。
構造体で二分木を表現するのと、malloc() / free() の練習。

takatoh@nightschool $ ./btreesort
unsorted: 80 77 21 42 50 76 88 48 32 19 
sorted:   19 21 32 42 48 50 76 77 80 88

二分木を使ったソート

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

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

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

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)

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

実行例:

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

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

二分ヒープ(ヒープ木)を使ったヒープソート

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

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

なんだかあんまりきれいじゃないけど。特に 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]

Rubyでクイックソート

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

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

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 速いな。やっぱり自前で作るよりあるものを使ったほうがいいってことか。
いや、リンク先の実装だと速いのか?

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)

そんなことはなかった。

Schemeでユークリッドの互除法

今日は時間がないので埋草的エントリ。
ユークリッドの互除法で最大公約数を求める。

takatoh@nightschool $ gosh gcd.scm
21

Schemeでマージソート

やってみた。

実行結果:

^o^ > gosh merge-sort.scm
(1 2 3 4 5 6 7 8 9)

バイナリサーチ

AOJの問題を解く途中で作ったのでメモしておく。結局使わなくなったけど。
あらかじめソートされているのが前提。見つからないときは None を返す。

実行結果:

^o^ > python binary_search.py
3359
None
0
None