アルゴリズム

焼きなまし法でThomson問題の解を探索する

Thomson問題 Thomson問題とは、三次元単位球の表面にN個の電荷の等しい粒子を配置するとき、クーロンポテンシャル\( U = \sum_{i wikiをThomson problem - Wikipedia, the free encyclopedia。N=5のときにて三方両錐形が解になったり、N=8で立方体が解になら…

Richardson補外とか丸め誤差について

『数値計算の常識』(伊理正夫・藤野和建著)を読んでいろいろ試したくなったので、取り敢えず簡単にできるものをやってみる。定積分\( I = \int_{a}^{b} f(x) dx\)をN等分した台形\(I_N\)で近似するとき、 \( I_{1} = \frac{1}{2}(b - a)(f(a) + f(b)) \) \( …

高速メビウス変換について

高速メビウス変換について自分が勉強した内容をまとめておく。証明はいい感じのサイトを参照のこと。 (http://d.hatena.ne.jp/simezi_tan/20130522/1369203086)集合に関する関数f,gについて次式が成り立つとき、g(S)が計算できているならば、任意のSについて…

ネットワークフロー

練習会でフロー関連の発表をした。内容は↓のとおり。 今までフローを避けてきたので、まとまった勉強をする良い機会となった。しかし、一般マッチングや最大マッチングと最小点カバーにおける関係などはまだ理解できてないので、もう少し蟻本を睨む必要があ…

最短経路問題

蟻本等の内容を復習していく。 Bellman-Ford法 頂点sから頂点iまでの仮の最短距離をd[i]とする 0: d[s]=0, d[i(≠s)]=INF とする 1: u,v∈V に対してd[v]=min(d[v],d[u]+w(u,v))で更新。更新できなくなったら終了 step1がV回実行されても終了しない場合、負の…