修正オイラー法
vは速度です。常微分方程式が2つ出てきましたが難しいことはありません。それぞれに修正オイラー法を適用して解いていきます。 #include <stdio.h> double f1(double x,double v); double f2(double x,double v); int main() { double t,dt,x,v,tmax; double k0[2],k1[2]; dt=0.01; //刻み幅設定 x=1.0; //位置初期値 v=0.0; //速度初期値 tmax=100; //繰り返し最大回数 FILE *output; output=fopen("output.data","w"); fprintf(output,"%f %f\n",x,v); for(t=0;t<tmax;t+=dt) { k0[0]=f1(x,v); k0[1]=f2(x,v); k1[0]
オイラー法
vは速度です。常微分方程式が2つ出てきましたが難しいことはありません。それぞれにオイラー法を適用して解いていきます。 #include <stdio.h> double f1(double t,double x,double v); double f2(double t,double x,double v); int main() { double x,v,t,dt,tmax; double k0[2]; FILE *output; output=fopen("output.data","w"); /*初期値*/ x=1.0; v=0.0; dt=0.01; tmax=100; for(t=0.0;t<=tmax;t+=dt) { k0[0]=dt*f1(t,x,v); k0[1]=dt*f2(t,x,v); x=x+k0[0]; v=v+k0[1]; fprintf(output,"%f
ルンゲクッタ法
vは速度です。常微分方程式が2つ出てきましたが難しいことはありません。それぞれにルンゲクッタ法を適用して解いていきます。 #include <stdio.h> double f1(double t,double x,double v); double f2(double t,double x,double v); int main() { double t,x,v,dt,tmax; double k1[2],k2[2],k3[2],k4[2]; x=1.0; //位置の初期値 v=0.0; //速度の初期値 dt=0.01; //刻み幅 tmax=500.0; //繰り返し最大回数 FILE *output; output=fopen("output.data","w"); for(t=0;t<tmax;t+=dt) { k1[0]=dt*f1(t,x,v); k1[1]=dt*f2(t,
ルンゲ＝クッタ法 - Wikipedia
数値解析においてルンゲ＝クッタ法（英: Runge–Kutta method）とは、初期値問題に対して近似解を与える常微分方程式の数値解法に対する総称である。この技法は1900年頃に数学者カール・ルンゲとマルティン・クッタによって発展を見た。 一連のルンゲ＝クッタ公式の中で最も広く知られているのが、古典的ルンゲ=クッタ法 (RK4、もしくは単に狭義の ルンゲ=クッタ法、英: the (classical) Runge–Kutta method) などと呼ばれる4次の公式である。 次の初期値問題を考える。 但し、y(t) が近似的に求めたい未知関数であり、その t における勾配は f(t, y) によって t 及び y(t) の関数として与えられている。時刻 t0 における初期値は y0 で与えられている。 今、時刻 tn における値 yn = y(tn) が既知のとき、十分に小さなステップ
Tutorial: Building a Force Directed Graph from XML on kylescholz.com :: blog
Part of my upcoming talk at The Ajax Experience is, of course, about graph-based data visualizations using JSViz. I've worked up a couple of tutorials using the new JSViz 0.3.1 and I'm sharing abbrieviated versions of them here. Conference attendees should find these posts useful as a recap and additional reference for coding your own apps. In this first tutorial, we'll introduce the JSViz 0.3.1 A
Force-directed graph drawing - Wikipedia
Social network visualization using a force-directed graph drawing algorithm[1]Visualization of links between pages on a wiki using a force-directed layout Force-directed graph drawing algorithms are a class of algorithms for drawing graphs in an aesthetically-pleasing way. Their purpose is to position the nodes of a graph in two-dimensional or three-dimensional space so that all the edges are of m
COS類似度 - 小宮日記
文章の類似度を計算する場合などにCOS類似度というのが 使われるらしい。 二次元で考えた場合、ベクトルAとベクトルBの類似度は、 COS類似度＝AとBの内積/(norm(A)*norm(B))normは my $norm_1 = 0.0; map { $norm_1 += $_ ** 2 } values %{$vector_1}; $norm_1 = sqrt($norm_1);のように、ベクトルの要素をそれぞれ二乗して積算して、SQRTをとったもの。 二次元の場合は、norm([x,y])=sqrt(x^2+y^2)=距離ですね （このへんはボナメソのペナルティでもおなじみ。L1norm、L2norm） 内積をノルムで割ってるのは、正規化がかかるためのようです。 ベクトルによって長かったり、短かったりするでしょうから。 ベクトルとベクトルの間の角度が、類似度を表現するわけです。 内積は
bayonやCLUTOが爆速な理由 - download_takeshi’s diary
クラスタリングツールbayonを使っていて、常々「どうしてこんなに高速に処理できんのかなぁ」と疑問に感じていました。repeated bisectionという手法自体がk-means法などと比べると効率がいいのですが、それにしても、それだけでは説明がつかないほど爆速なわけです。 うまく例えられませんが、自前でk-meansのスクリプトを書いて比べてみると、自転車と新幹線くらいちがうという印象です。はじめてCLUTOを触った時、数万件程規模のクラスタリング処理が本当に「あっ」という間に終わってしまい、びっくりした記憶があります。 きっと実装面でなにか特殊なことがあるんだろうなと思い、mixiエンジニアブログでbayonの記事を改めて読み漁っていたら、以下の部分が目に止まりました。 このクラスタの評価は、クラスタの各要素とクラスタの中心とのcosine類似度の和としています。この和が大きいほど
人材獲得作戦の問題を反復深化深さ優先探索で - 簡潔なQ
人生を書き換える者すらいた。: 人材獲得作戦・４ 試験問題ほか 反復深化深さ優先探索は、深さ優先探索の深さのリミットを少しずつ増やしながら行う探索で、幅優先探索に近い性質をもつ探索。 ゲーム木のように浅くて広い探索木の場合にメモリ効率が良く好まれる。 再帰で書けるので幅優先よりシンプル。 #include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; string maze; vector<int> depths; size_t w; bool search(int x, int depth) { if(depth<=depths[x])return false; depths[x]=depth; if(maze[x]=='*')return false; i
人材獲得作戦の問題をWarshall-Floydで - 簡潔なQ
人生を書き換える者すらいた。: 人材獲得作戦・４ 試験問題ほかを今度はWarshall-Floydで解いてみた。 Dijkstraが特定の2点間の最短経路を求めるのに対して、Warshall-Floydは全ての2点間の最短経路を一括で求める。 またWarshall-Floydの良い点として、負辺の処理および負閉路の検出も可能ということが挙げられる。 負辺に対応した単一始点最短経路探索のBellman-Fordというのもあるようだけれど、Warshall-FloydのオーダーがO(|V|^3)なのに対してBellman-FordはO(|V||E|)らしいので、ある程度疎でない限りWarshall-Floydでいいんじゃないかな。 効率は悪いが、まあWarshall-Floydの練習ってことでどんまい。綺麗だし。 #include <iostream> #include <string> #i
グラフの自動レイアウトに挑戦
2012-08-12 13:37:12 追記 (2022/8) もともとは、Windowsアプリケーション（.NET Windows Formsアプリケーション) として実装していましたが、再公開を機にJavaScriptに移行しました。 きっかけ Nintendo DSのパズルゲーム「レイトン教授と最後の時間旅行」で出題された問題に、複雑に絡まったトンネルが出てくる。 これを解くときに、道が絡まったままだと頭がこんがらがるので、交点に番号を振り、 位置を入れ替えて見やすくした。 これをコンピュータにやらせたら面白いのでは？というのがこの連載記事のきっかけだ。 目次 #1 グラフ構造をSVGで表示 ノード（節点）とエッジ（線）のデータをSVGで表示する。 #2 ばねモデル Eadesのばねモデルをオイラー法を使って実装し、アニメーションさせる。 #3 ノードをドラッグできるようにする ばね
ネットワークの可視化技術
K. Boitmanis, U. Brandes, and C. Pich, Visualizing internet evolution on the autonomous systems level, Graph Drawing 2007, LNCS, vol.4875, pp.365 376, 2007. p.252, 1986. P. Eades, A heuristic for graph drawing, Congressus Nu merantium, vol.42, pp.149 160, 1984. T.M.J. Fruchterman and E.M. Reingold, Graph Drawing by force directed placement, Softw. Pract. Exp., vol.2, no.11, pp.1129 1164, 1991. T.
もっと高速に－線分交差判定－
線分交差判定といっても、すべての与えられた線分に対して、同様な計算を 行って判定していたのでは、無駄が多いように見えます。場合によっては もっと単純な軽い判定で行えるはずです。そこで、 『場合分けによるラフチェック』を もっと簡単に－線分交差判定－のプロシージャ に追加して、次のように変更します。 '構造体 Private Type POINT x As Double y As Double End Type '座標 p1,p2 を結ぶ線分と座標 p3,p4 を結ぶ線分が交差しているかを調べる 'ただし、線分が重なっている場合(3点,4点が一直線上にある)、「交差している」、と判定します。 Private Function intersectionEX(p1 As POINT, p2 As POINT, _ p3 As POINT, p4 As POINT) As Boolean 'x座標
もっと簡単に－線分交差判定－
ここでは、線分交差判定の定石ともいえる方法を紹介しています。 線分と直線の見落としがちな大切な定義です。
Bayesian Setsによる関連文書検索システムStupa - mixi engineer blog
都会よりも田舎が好きなfujisawaです。Bayesian Setsというアルゴリズムを使って、関連する文書を高速・高精度に検索できるシステムを作成しましたので、そのご紹介をさせていただきます。 Bayesian Setsとは Bayesian Setsはいくつかアイテムを入力すると、それを補完するようなアイテムを返してくれるアルゴリズムです。原著論文の先頭に"Inspired by Google Sets"と書かれているように、Google Setsを参考にして作成されています。実際にどのような出力が得られるか、Google Setsに以下の表のクエリを検索して試してみますと、 クエリ 出力 apple, banana chocolate, strawberry, vanilla, cherry, ... apple, macintosh software, windows, mac,
トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター
トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター：最強最速アルゴリズマー養成講座（1/4 ページ） プログラミングにおける重要な概念である「探索」を最速でマスターするために、今回は少し応用となる探索手法などを紹介しながら、その実践力を育成します。問題をグラフとして表現し、効率よく探索する方法をぜひ日常に生かしてみましょう。 まだまだ活用可能な探索 前回の「知れば天国、知らねば地獄――『探索』虎の巻」で、「探索」という概念の基礎について紹介しました。すでに探索についてよく理解している方には物足りなかったかと思いますが、「問題をグラフとしてうまく表現し、そのグラフを効率よく探索する」というアルゴリズマー的な思考法がまだ身についていなかった方には、得るものもあったのではないでしょうか。 前回は、「幅優先探索」と「深さ優先探索」という、比較的単純なものを紹介しましたが
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
CiteSeerX
NWB Community Wiki : Fruchterman-Rheingold browse
グラフ描画入門 - Wolfram Mathematica
ネットワーク構造の可視化