Barnes-Hutのアルゴリズムについて

はじめに

グラフを描こうと思い、力学モデルについて調べていたらBarnes-Hutのアルゴリズムという手法を見つけたのでためしに書いてみたメモ。
ノード間の相互作用を計算するときに計算量を減らすためのアルゴリズム。
多体問題のシミュレーションに使うのかなと期待したけどそんなことはなかった。(計算が全く厳密でない)

サンプルをgistに上げました。(https://gist.github.com/domitry/7214402)
Processingがあればそのまま動きます。
Processingというか、Javaを初めてまともに書いたので使い勝手がよくわからなかった。
Rubyで書き直そうかなあと思いつつrcairoでウィンドウに描画するのが予想以上にめんどくさかったので挫折。

参考url

The Barnes-Hut Algorithm - arborjs.org
http://arborjs.org/docs/barnes-hut
詳しい解説が載っているのでこれを読めばわかります。

A hierarchical O(N log N) force-calculation algorithm - nature
http://www.nature.com/nature/journal/v324/n6096/abs/324446a0.html
元の論文。

アルゴリズム

  1. 空間を再帰的に4分割していき、1つの領域に1つの質点が収まるようにする。
  2. この分割を元に4分木を作る。
  3. ある質点より十分離れた領域に所属する質点との相互作用を計算するときは、領域に属する質点の重心との相互作用として計算する。

詳しくは参考url1(http://arborjs.org/docs/barnes-hut)をご覧ください。

サンプル

f:id:domitry_h:20131231181223p:plain
初期条件が悪いと汚いグラフができるのでKamada-Kawaiのアルゴリズム等でうまい初期条件を見つける工夫が必要。