こともなし - オベリスク備忘録

こともなし

晴。
昨晩は明け方まで AOJ をやっていた。そんなになるとは思っていなかったのだが、この問題を Ruby で解いていて詰まってしまったのである。グラフの単一始点最短経路問題なので、まずはふつうに幅優先探索で実装したのだが、なんとメモリオーバーになってしまった。何か爆発的に経路が多いらしい。なので、確信はなかったけれど、ダイクストラ法に切り替えて実装する。それに手間どって時間を喰った。けれども、今度はタイムオーバーなのである。ちょっと Ruby では無理なのかも知れないが、まだダイクストラ法で優先度付きキュー（二分ヒープ）を使って実装するという方法などが残っている。しかしこれはやったことがないので、簡単に実装というわけにはいかない。まあできるとは思うが、疲れたのでさすがにそこで寝ました。だんだんむずかしくなってきて、少しずつしか進まない。これなどはどうやってもタイムオーバーで、Ruby で解けた人は誰もいないという有り様である。コードは正しいと思うのだが。これでも苦労したのだけれどなあ。

ダイクストラ法はノードの確定のさせ方がいろいろあるので、自分のやり方はまだ必ずしも効率的でない（毎回全ノードから探索している）。もっとも効率的な確定のさせ方はどうしたらよいか考える余地が（だいぶ）ある。

＃

一時、雪。
NML で音楽を聴く。■ショパンのポロネーズ第五番 op.44 で、ピアノはラザール・ベルマン（NML、MP3）。

■モーツァルトのピアノ協奏曲第二十三番 K.488 で、ピアノは田部京子、指揮は小林研一郎、日本フィルハーモニー交響楽団（NML）。コバケンはふつうによい。田部京子さんはよくわからないのだが、自分のもっていない感受性をもっている可能性大。田部さんの CD はたくさん出ているな。