2014年4月14日月曜日

MST-一息つく

アルゴリズムってすごい

プリム法というアルゴリズムに二分ヒープというものを加えて悪戦苦闘した結果、5,000個の座標を繋ぐMSTの作成時間を5sに短縮できた。

アルゴリズムを使わなかった頃2,000個でも一分かかっていたことを思うと感慨深い。

こちらから動作確認が出来ます。

うちのパソコンでも500個くらいならアニメーション出来ますが、加減がわからないので少なめの100個にしています。

見る人が見たら不完全な出来だと思うが、そろそろ勉強を再開したくなってきたのでMSTはこれまで。

何が出来るか

ゲームだと迷路の作成とか、実社会だと路線とか、生物だと粘菌とか。他にもいろいろ。

最小コストで手を繋ぐ方法を考える手法だと理解しているが、一週間近く付き合っても使い道を発見してあげることが出来なかった。