Problem 1 - nisshiee/takashi GitHub Wiki

たかしくんはみかん5個とリンゴ3個を買いにおつかいに行きます。
たかしくんは左上から出て右下まで移動します。
たかしくんは上、下、左、右のいずれかに進むことができます。
たかしくんは一度通った場所を二度と通ることはできません。
また、工事中で通ることが出来ない場所が何カ所かあります。
たかしくんの道筋は何通りあるか算出する関数を記述してください。

nisshieeの解答

この問題、全探査以外の手法はあるのでしょうか・・・残念ながら私は見つけられませんでした。

ということで、単純に「1歩進む→通った道を記録」を再帰呼び出しして道筋をカウントしています。

工夫1

課題

さて、再帰呼び出しするということ、「末尾再帰かどうか」が気になります。直感的に記述すると、「4方向に1歩進んで再帰→結果を加算」の順になるので、末尾再帰になりません。

末尾再帰でないことを気にする必要があるか、という点に関しては難しいところです。「再帰呼び出しで掘るスタックの数=進んだ歩数」になるので、高々、「通行可能なマスの数」です。

入力例として与えられた5x5マス程度では、25回スタック掘ったところで問題になりません。また、もし仮に10x10マスにしたところで高々100で問題ありませんし、むしろこの頃には計算時間の方がボトルネックになります。

しかしStackOverflowの問題が顕在化するキラーケースが存在します。

0,0,0,0,0,0,0,0,0,......

要するに、長い一本道の場合です。 1x10000マスですべて通行可能なマスの場合、経路数は1で瞬時に計算が終わることを期待したいですが、再帰呼び出ししていると10000回スタックを掘ることになり、StackOverflowErrorで落ちます。

対策

そこでScalazですよ。

Trampoline使います。

https://github.com/nisshiee/takashi/blob/master/src/main/scala/prob1/Takashi.scala

def next(f: Field, step: Point): Trampoline[Int]

再帰呼び出しをTrampolineに包んで返す関数 next を用意し、

for {
  up <- next(f, (0, -1))
  down <- next(f, (0, 1))
  left <- next(f, (-1, 0))
  right <- next(f, (1, 0))
} yield up + down + left + right

あとはfor式で結合。

ね、簡単でしょ？

工夫2

課題

冒頭でも述べたとおり、アルゴリズム上は全く工夫なく全探査をしています。もちろん計算時間はうなぎのぼりです。マップの広さに対する指数関数で計算時間が伸びます。最悪ですね。

入力例は5x5マスでしたが、これを拡張して9x9マスで検証します(10x10は待ってられなかった)。

0,1,0,1,0,0,1,0,1
0,0,0,0,1,0,0,0,0
0,0,0,0,0,0,0,0,0
0,1,0,0,0,0,1,0,0
0,1,0,0,0,0,1,0,0
0,1,0,1,0,0,1,0,1
0,0,0,0,1,0,0,0,0
0,0,0,0,0,0,0,0,0
0,1,0,0,0,0,1,0,0

これをTrampolineを使ったシングルスレッド環境で解いてみました。実行環境はAmazonEC2のc1.mediumです。結果、所要時間は 約4分40秒 でした。

対策

ありきたりですが、分散処理で高速化を狙います。目標としては、

akka 使うこと(今回のScala Conference Japanでも注目を浴びてたことですし)
スケーラビリティを高く保つ(EC2インスタンスをぽんぽんぽんっと立てれば勝手に早くなるイメージ)

という感じです。 akka-clusterとか使うとカッコ良かったかもしれませんが、もともとakkaに詳しかったわけではないので今回は見送りました。ノード追加時にconf1箇所書き換えまでOKということにしています。

分散化のアルゴリズムとしては最も単純なものを採用しました。以下のように、木構造を根から葉の方向に下って探査します。

最初のn層だけを唯一の上位ノード(Aggregater)が探査
到達した枝から始まるサブツリーを下位ノード(SearchActor)に送信
下位ノードは与えられたサブツリーをそれぞれ独自に探査

実験

AWS上にインスタンスを構築。

c1.medium 1インスタンス → Aggregater
c1.xlarge 8インスタンス → SearchActor

結果：上記9x9マスの問題を解くのに 約30秒 かかった。

考察

分散化のアルゴリズムがイマイチ。 SearchActorに渡ったあと、一瞬で残りが終わるサブツリーとまだ長時間かかるサブツリーの差が激しい。

ただし、SearchActorインスタンスを追加することによる効果は十分に得られたが、インスタンス数と計算時間の関係とかきちんと分析する時間はなかった。なによりc1.xlarge8インスタンスを動かしっぱなしはさすがに財布に響くｗ

やりたくてできなかったこと

http://www.youtube.com/watch?v=Q4gTV4r0zRs

これを思い出すのが遅すぎた。

Simpathアルゴリズム実装しようと思ってから締め切りまでにとれた時間が2時間程度で、完成しなかった。

feature/issue/10 ブランチが実装しようとした名残。バグが残ってます。