Hatena::ブログ(Diary)

cocoatomo衝動日記

2011-01-20 ガチな数学・まとめ

[]点線で楕円を描く・まとめ 02:11 点線で楕円を描く・まとめ - cocoatomo衝動日記 を含むブックマーク

【追記・2011/01/22】最初に書いた内容に大幅に誤りがあったので, 再度編集しています. おっちょこちょいですみません.

【追記・2011/02/03】修正完了. ソースコードを色々変えました.

昨日一昨日の記事には数式に間違いがあったので訂正したまとめ記事を書きます。

【修正・2013/03/12】数式に対するコメントの通り, 修正しました.

楕円の弧長

まず、 x = a ¥cos ¥varphi,¥quad y = b ¥sin ¥varphiパラメータ表示して、点 (a, 0) から左回りに弧長 u(¥varphi) を測っていくことにします。

¥begin{align*} u &= ¥int_0^{¥varphi} ¥sqrt{dx^2 + dy ^2} ¥¥ &= ¥int_0^{¥varphi} ¥sqrt{a^2 ¥sin^2 ¥varphi + b^2 ¥cos^2 ¥varphi} d¥varphi ¥end{align*}

となり、この逆関数  ¥varphi (u)微分を考えます。(ここの時点で式の形に間違いがありましたね.)

¥frac{d ¥varphi}{du} = ¥frac{1}{¥frac{du}{d ¥varphi}}  = ¥frac{1}{¥sqrt{a^2 ¥sin^2 ¥varphi + b^2 ¥cos^2 ¥varphi}}

これを差分形にして、

¥begin{align*} ¥Delta ¥varphi &= ¥frac{¥Delta u}{¥sqrt{a^2 ¥sin^2 ¥varphi + b^2 ¥cos^2 ¥varphi}} ¥¥ ¥varphi_0 &= 0 ¥¥ ¥varphi_n &= ¥varphi_{n - 1} + ¥frac{¥Delta u}{¥sqrt{a^2 ¥sin^2 ¥varphi_{n-1} + b^2 ¥cos^2 ¥varphi_{n-1}}} ¥end{align*}

¥sin¥cos を間違えていましたね。

ここで ab の大小については何も言っていないことに注意してください。

これを実装します。

Python ソースコード

開発をローカルから Github に移したので, 最新のソースはこちらを見てください.

import sys
import math

DIVISION = 1000.0
CYCLE = 10

def angles(du, a, b):
    phi = 0
    while phi <= 2 * math.pi:
        yield phi
        phi += du / math.sqrt((a * math.sin(phi))**2 + (b * math.cos(phi))**2)

def coordinate(du, a, b):
    for angle in angles(du, a, b):
        yield (a * math.cos(angle), b * math.sin(angle))

def circumference(a, b):
    """Return a length of a circumference of an ellipse.

    @param a, b length of two semi-axes

    reference: http://en.wikipedia.org/wiki/Ellipse#Circumference
    """
    expr = ((a - b)/(a + b))**2
    return math.pi * (a + b) * (1 + (3 * expr)/(10 + math.sqrt(4 - 3 * expr)))

def draw(argv=None):
    if not argv:
        argv = sys.argv
    filename = argv[1]
    a = float(argv[2])
    b = float(argv[3])
    du = circumference(a, b) / DIVISION

    with open(filename, 'w') as out_file:
        print >> out_file, 'plot "-" w l'
        print >> out_file, '#x\ty'
        for i, coord in enumerate(coordinate(du, a, b)):
            i %= CYCLE * 2
            if i < CYCLE:
                print >> out_file, '{0}\t{1}'.format(*coord)
            else:
                print >> out_file, ''
        print >> out_file, 'end'
        print >> out_file, 'pause -1'


if __name__ == '__main__':
    draw(sys.argv)

コマンド

$ python ellipse.py ellipse.dat 1.0 0.5
gnuplot> plot "ellipse.dat" w l

出力結果

以下のようにちゃんと点線が等長、等間隔で描けています。(実際にプログラムで点線の長さと間隔を測ったところ、1 % 程度の誤差はありましたがだいたい同じでした。)

f:id:cocoatomo:20110121020543j:image

ab には大小の制限は無いので縦長の楕円も描けます。

f:id:cocoatomo:20110121022011j:image

あとがき

昨日一昨日の記事を書いてから、色々な方からコメントやツッコミをいただきました。ありがとうございます。

今まで何かを作ったり、記事を書いたりして公開したことはあったけれど、今回もらった反応は今までで一番多いものでした。

そして、何かを発表して反応をもらう喜びを強く感じました。


これは病み付きになりそうです。


もしかして、オープンソースで活動してる人の中には、この喜びを原動力にやってる人もいるのかなぁ? と思ったり。

それでは、お休みなさい。

ななしななし 2011/04/02 01:04 一番上のu=の式には、dφは要りませんよ。

2011-01-19 ガチな数学

[]点線で楕円を描く・その2 02:28 点線で楕円を描く・その2 - cocoatomo衝動日記 を含むブックマーク

[追記] この記事には誤りが含まれています。訂正した記事はこちらです。



昨日の記事の続きです。

昨日は計算式までは出したのですが、実際に計算せずにはいられなかったのでやってみました。

Numpy とかあるのは知ってるのですが、標準の Python だけでどこまでできるかやってみました。

描画は gnuplot 使ってやってます。

ソースコード

ちゃちゃっと書いたので、コメントとかは省いてます。

import sys
import math

def delta(phi, du, k2):
    return phi + du / math.sqrt(1 - k2 * math.sin(phi)**2)

def draw(argv=None):
    if not argv:
        argv = sys.argv
    filename = argv[1]
    a = float(argv[2])
    b = float(argv[3])
    du = float(argv[4])

    k2 = 1 - (b/a)**2
    phi = 0

    with open(filename, 'w') as out_file:
        print >> out_file, '#x\ty'
        i = 0
        while phi <= 2 * math.pi:
            i += 1
            i %= 10
            if i < 5:
                print >> out_file, '{0}\t{1}'.format(a * math.cos(phi), b * math.sin(phi))
            else:
                print >> out_file, ''
            phi = delta(phi, du, k2)

                

if __name__ == '__main__':
    draw(sys.argv)

コマンド

$ python ellipse.py ellipse.dat 1.0 0.5 0.01
gnuplot> plot "ellipse.dat" w l

plot 結果

f:id:cocoatomo:20110120022542j:image

あとがき

思ったより誤差が発散しなかったので楽でした。

今日ばっかりは俺ってすげーって思いました :P

それでは。

2011-01-18 ガチな数学

[]点線で楕円を描く 02:32 点線で楕円を描く - cocoatomo衝動日記 を含むブックマーク

[追記] この記事には誤りが含まれています。訂正した記事はこちらです。




今日は 1 つネタをもらったので, ガチな数学をやろうと思います.


お題は「点線で楕円を描く」です.

円の場合は, 等角度ごとに区切って点線を書いていけば良いので簡単です.

たいていの場合, 三角関数は標準ライブラリにあるのであまり苦労しません.

しかし楕円の場合となると, 円がつぶれた形をしているので一筋縄ではいきません.


話の流れを追いつつ, どう解決していったか見ていきましょう.

発端

募集:PIL で点線の楕円を描画するのが得意な人。つーか、arc (円弧描画)関数だけで点線が書ける人。

http://twitter.com/#!/tk0miya/status/26986376482267136

楕円の場合は角度あたりの弧の長さが均等にならないよね。つまり点線を描画するにはどうすればいいんだ? 平面幾何なんてさっぱり分からないんだから、こんなん解決できないよ!

http://twitter.com/#!/tk0miya/status/26987619082571776

@tk0miya 楕円の弧長の話ですよね? その計算は楕円積分と言って, 数学で有名な積分計算です. 円もそうですが初等関数にならないので, きっちり計算する以上に楽な方法はありません. 計算式書きましょうか?

http://twitter.com/#!/cocoatomo/status/26991426927599616

実は, この楕円の弧長を求めるという問題は数学でも大きな問題でした.

いったいこれはどんな性質を持っているのか? 三角関数のようなものなのか?

数学のはなし

これを研究していた人たちにヤコビやワイエルシュトラスがいます.

彼らは

¥begin{align*}¥begin{cases}x = a ¥cos ¥varphi ¥¥ y = b ¥sin ¥varphi¥end{cases}¥end{align*}

という楕円の周を (a, 0) から左回りにたどったときの長さを求める積分

¥begin{align*}E(k,¥quad ¥varphi) = ¥int_0^{¥varphi} ¥sqrt{1 - k^2 ¥sin^2 ¥varphi} d ¥varphi ¥¥ (k^2 = ¥frac{a^2 - b^2}{a^2}) ¥end{align*}

逆関数に着目し, その性質を調べ数学的な業績を挙げました.

その逆関数¥varphi(k,¥quad u) とするとその微分は以下のように求まります. (みなさん高校でやりましたね!?)

¥begin{align*}¥frac{d ¥varphi}{du}(k,¥quad u) &= ¥frac{1}{E’(k,¥quad ¥varphi)} ¥¥ &= ¥frac{1}{¥sqrt{1 - k^2 ¥sin^2 ¥varphi}} ¥¥ (u = E(k,¥quad ¥varphi)) ¥end{align*}

これを微分の形から差分の形に直して

¥begin{align*} ¥Delta ¥varphi &= ¥frac{¥Delta u}{¥sqrt{1 - k^2 ¥sin^2 ¥varphi}}¥end{align*}

これをさらに総和の形に直すと

¥begin{align*}¥varphi_0 &= 0 ¥¥ ¥varphi_n &= ¥varphi_{n-1} + ¥Delta ¥varphi_{n-1} ¥¥ &= ¥varphi_{n-1} + ¥frac{¥Delta u}{¥sqrt{1 - k^2 ¥sin^2 ¥varphi_{n-1}}} ¥¥ (¥varphi_n ¥approx ¥varphi(n * ¥Delta u) ¥) ¥end{align*}

となる.

なので, ¥varphi (k,¥quad u) の値を求めるときは n を十分大きく (つまり ¥Delta u = u/n 十分小さく) とれば ¥varphi の値が差分の総和を計算することで求まり,  x = a ¥cos ¥varphi,¥quad y = b ¥sin ¥varphi という計算で座標の値に戻せる.

誤差評価を行ってないので収束あたりがまだあやしいけれど, 一応目処は立った.

これからは誤差が出てしまったときの対処が残っているかな.

あとがき

こんなんでどうでしょう, tk0miya さん.

2011-01-10 高木貞治プロジェクト & 大学数学の第一歩

[][]高木貞治プロジェクト・代数整数論 21:48 高木貞治プロジェクト・代数的整数論 - cocoatomo衝動日記 を含むブックマーク

高木貞治プロジェクトとは

2011年1月1日をもって高木貞治先生の著作権が切れ, 著作物の内容を様々な形で利用できるようになりました.

そこで著作物の内容を Web 上で公開していくプロジェクトが開始されました.

ここがプロジェクト・ホームになると思います. http://oku.edu.mie-u.ac.jp/~okumura/blog/node/2574

事の起こりの流れは Togetter にまとめられています. http://togetter.com/li/86256


公開している場所としては Wikisource が適切だろうということで, Wikisource:高木貞治プロジェクトで公開されています.

私はちょうど所有していた「代数的整数論」という本の目次だけ書いたものをひとまず Wikisource に作ってみました.


ただ他の著作と同じく著者である高木貞治先生の没後に改訂が入っていて, 本の著作権の状態が不明になっています.

そのため出版社に問い合わせのメールを送ることになりました.

質問メール文面の公開

@jin_in さんが共立さんと岩波さんに送る著作権に関する質問メールの本文を参考に (というかほぼそのままですが) 私も文面を作成し公開したいと思います. まずい箇所などあればご指摘ください.

株式会社岩波書店御中


高木貞治先生の没後50年が経過したことにより、2011年で高木先生の著作物に対する著作権の保護期間が切れました。これに伴い、高木先生の著作をインターネット上に入力するプロジェクトが開始されています。


青空文庫

http://www.aozora.gr.jp/

http://www.aozora.gr.jp/index_pages/person1398.html


Wikisource

http://ja.wikisource.org/

http://ja.wikisource.org/wiki/Wikisource:高木貞治プロジェクト


三重大学奥村先生のブログ

http://oku.edu.mie-u.ac.jp/~okumura/blog/node/2574


本プロジェクトでは、「代数整数論」も対象になっており、入力に際しては第2版を利用する方針にしております。入力に際しては初版を利用すれば問題ないのですが、初版は第2版に比べ大学の図書館等でないと入手しにくいことや、読みやすさを考えますと、御社発行の「代数整数論第2版」を底本としたいと考えています。この本の補遺に「第2版 跋」という節が設けてあり、初版からの改訂箇所が列挙してあるのですが、署名部分が「(1971年3月,S. K. 記す)」となっていて、改訂が行われた部分の著作権の扱いがどうなっているか理解できておりません。


本プロジェクトを遂行していく上で、後日問題にならないように、御社の考えを頂戴できれば幸いです。


昨年「定本 解析概論」が出版され、高木先生の著作が電子化されることへの懸念はあるかもしれませんが、WikisourceにはPDF出力機能があるももの品質はあまりよくなく書籍の品質にはかないません。むしろ本プロジェクトによって、整数論に興味をもつ方が増えるのではないかと考えています。


なお、本質問内容はWeb上 ( http://d.hatena.ne.jp/cocoatomo/20110110/1294663688 ) に公開しており、できましたら御社からの回答内容も同ブログにて公開させていただきたいと考えております。

追記: @random_oracle さんの指摘を受け, 公開場所を明記しました.

追記 [2011/01/12]: メールを送信しました.

私的な話

私自身はここらへんの奥村先生の Tweet でプロジェクトの存在を知りました.

有名な解析概論はもちろんプロジェクトの対象になっていたし, 代数学講義と初等整数論講義もプロジェクトの対象になっていました.

しかし, 代数的整数論という本が対象に入っていなかったので, じゃあ作るかと自分で目次を作ってみました.


この本は高校の図書館に, ある夭折した卒業生から寄贈された本で構成された文庫があり, そこで出会ったのが最初の出会いでした. そしてその文庫にはあの加藤和也先生の解決!フェルマーの最終定理―現代数論の軌跡もあり, その2つの書籍のおかげですっかり数論に魅せられてしまいました. (内容なんてこれっぽちも分かってなかったのに^-^;)


そんなことがあり大学では整数論を選んで進んでいくのですが, その後挫折した話はまた別の機会にでも話せたら話します. まぁ人生色々ありますね.

siodgpsiodgp 2013/08/01 11:08 せっかく無料公開された高木貞治プロジェクトもTPPで全て公開停止にされる。著作権延長で70年に保護期間が延長されれば数十年公開できなくなり、今絶版の欧文論文集や初等幾何の教科書なども全て読めなくなるだろう。

著作権 《死後50年経っている数学者(没年順)》
高橋卯之助 (1833-1902)
菊池大麓 (1855-1917)
佐原純一 (1841-1920)
樺正董 (1863-1925)
北条時敬 (1858-1929)
藤沢利喜太郎 (1861-1933)
林鶴一 (1873-1935)
70年の壁
隈本有尚 (1860-1943)
竹内端三 (1887-1945)
藤原松三郎 (1881-1946)
吉江琢児 (1874-1947)
掛谷宗一 (1886-1947)
岡村博 (1905-1948)
秋山武太郎 (1884-1949)
窪田忠彦 (1885-1952)
谷山豊 (1927-1958)
高木貞治 (1875-1960)
辻正次 (1894-1960)
小倉金之助 (1885-1962)

これだけの数学者の著作権が切れているのに、70年にされれば高木貞治や竹内端三のような大物が全て弾圧される。竹内端三の楕円函数論は有志がTeXで組んでPDFとして無料公開しているのに、違法ダウンロードということで検挙されるだろう。すでにepubによる数式の表示は実用レベルに達し、このような著作権切れの文献を公開するにはうってつけのフォーマットであるのに、どこの電子書籍屋も対応しない。Kindleですら数式表示を一切やる気がない。1年以上数式に対応するようにアマゾンに抗議しているのに未だ数式表示に対応しない。みんなもっとアマゾンに電凸し、Kindleは数式に早く対応しろと抗議しないといけない。唯一対応しているのはアップルのiBooksだが、竹内端三の楕円函数論は未だ公開されない。すでに有名なアイザック・ニュートンのプリンキピアのラテン語版は無料公開されているのに、日本語の理工書や科学雑誌が一切存在しない!青空文庫のような著作権切れの文献を積極的に公開しようとするプロジェクトですら数式に対応しない。彼らは数式表示をやらずに、数式一つが1ページを占めるようなアプリを未だ公開し続けている。数式を含む文章は横書きのが読みやすいのに対応しない。html5ではMathMLのようば数式表示技術が完成しているのに、未だにepubのような技術が普及しない。著作権切れの数学書を宣伝媒体とし、epub技術の優位性を証明せねばならない。未だに数式表示が対応しているという事実が未だに普及していない。寺田寅彦の著作も、欧文論文集のみはなぜか全く公開されない。岩波は欧文論文集をずっと絶版のままにし続けている、高木貞治の欧文論文集も同様だ。小平邦彦の論文集も絶版のままだ。著作権が切れている理工書は全く公開されない。考へ方とかの参考書も同様だ。全く復刊されない。このままでは竹内端三の新撰解析幾何学や高等微分学といった名著が全て読めなくされる。高木貞治の欧文論文集や初等幾何の教科書なども潰されるだろう。日本の出版社や東京図書のような悪魔のブラック企業が跋扈しており、崇高な古典的名著を全て絶版にして下らない高校レベルの大学の教科書を氾濫させている。本来こういう下らない低レベルな参考書を読まなければついていけない学生は全員留年・退学処分にせねばならないのに、連中を生かして、もっと高度なことを勉強したいという意欲ある学生を迫害する出版社。有能な人間は弾圧されて勉強したいといっただけで潰される異常な社会を変えなければいけない。そのためにも著作権切れの古典的名著を最新epub技術で全て無料公開していくという活動がリフローepubの宣伝を含め非常に有益であるのに、著作権が延長されればこのような試みも潰され、うきこぼれは完全に殲滅され尽くされるだろう。

2010-09-20 SSSP と並列処理

[][][] Dijkstra 法がなぜ並列処理に向かないか? 08:11  Dijkstra 法がなぜ並列処理に向かないか? - cocoatomo衝動日記 を含むブックマーク

※[2010/09/21 9:00] 用語を「並列」(parallel) に統一しました. まだ「並行」「並列」「分散」の使い分けがいまいち飲み込めてないので, 変だったらツッコミをいただけると幸いです.

さてここでは前のエントリで書いた Dijkstra アルゴリズム がなぜ Hadoop などの並列処理に向かないかを書いていきます.

玉入れとリレー

まずは比喩で話を進めていき, 並列処理に向いているアルゴリズムとそうでないアルゴリズムの区別を考えていきましょう.

運動会の種目から「玉入れ」と「リレー」という 2 つの競技を取り上げます. これらはどちらも団体でそれぞれ入れた玉の数やタイムを競うものです.


ただし, 同じ団体競技でもその性質は違います.

f:id:cocoatomo:20100920231401j:image

玉入れは競技人数を増やせば増やすほど得点の期待値は上がります. 例えば, 10 人で玉入れをしているチームと 20 人で玉入れをしているチームが競争すれば, 20 人のチームの方が断然有利でしょう. さらに 40 人, 80 人と増やしていけば, 落ちている玉を拾うコストがボトルネックになるまでスケールアウトできます.

極端なことを言えば, 玉入れの玉や籠を増やすという手段も採れます. こうしてしまえば際限無く得点の期待値を上げていくことができます.

f:id:cocoatomo:20100920231546j:image

逆に, リレーでは人数を増やしても玉入れほどには劇的にはタイムの期待値は上がりません. スタートとゴールがあらかじめ決められてしまっているため, 増えた人数の分だけ 1 人あたりの距離が短くなります. ある程度までは選手の疲労が少なくなる効果でタイムは伸びるでしょうが, すぐにバトンパスのコストがボトルネックになりタイムは落ちていくはずです.

そして, 玉入れの玉や籠を増やすようなボトルネックの解消手段がありません.

玉入れとリレーの違いは??

さて, なぜ玉入れとリレーでスケールアウトする/しないが分かれたのでしょうか?


それは処理の性質にありました.

玉入れでは玉が十分に転がっていれば玉を取り合うこともなく, 別の人の動作が自分の動作をじゃましません.

しかしリレーでは, バトンという 1 つしかないリソース (Singleton!) に対して各選手が処理を行っているため依存関係が生じ, どうしてもそれぞれの処理を並列で動かすことができません.


これを小難しく数式で書くとアムダールの法則とグスタフソンの法則になります. とは言ってもこの式は算数レベルの話なので, 覚えるほどの価値はありません. 式の字面を覚えるのではなく「並列処理基盤に載せても, 並列に処理できるとこしか処理時間の圧縮はできないよ」という式の意味の方を, 自分の言葉で噛み砕いて脳みそに染み込ませておきましょう. どうせ現実問題はこれより複雑で, とうてい計算なんぞできる代物ではないので.


余談ですが, 最近拾った面白い話にこんなのがありました.

秀吉とMapReduce : サルノオボエガキ

これも見事に部下の人数に対しスケールアウトするようにジョブを組んだ秀吉の頭脳の勝利と言えるでしょうか.


Dijkstra 法を復習

前置きがだいぶ長くなりましたが, 「処理の順序に依存関係があるかどうか?」という視点で Dijkstra 法を見ていきましょう.

Dijkstra 法では「スタートノードからの距離が最小のものから順に, 最短経路を確定していく」のでしたね. 忘れていたら前回のエントリで復習しておいてください.


以下のようなグラフに対して Dijkstra アルゴリズムを適用します.

f:id:cocoatomo:20100920232446j:image


まずスタートノードへの最短経路が決定します. 今回からは最短経路が決まったノードには色を付けていくことにします.

f:id:cocoatomo:20100920232506j:image

次に, 最短経路が決定したノードたちから 1 ステップで行けるノードのうち, スタートノードからの距離が最短のノードを探します.「い」ノードが選ばれ, 最短経路「S→い」, 最短距離 1 が確定します.

f:id:cocoatomo:20100920233425j:image

さらに同様に処理をしていくと,「は」への最短経路「S→は」と「S→い→は」, 最短距離 2 が確定,

f:id:cocoatomo:20100920232521j:image

「ろ」への最短経路「S→は→ろ」, 最短距離 3 が確定,

f:id:cocoatomo:20100920233548j:image

「に」への最短経路「S→は→に」, 最短距離 4 が確定,

f:id:cocoatomo:20100920232545j:image

「ほ」への最短経路「S→は→ろ→ほ」, 最短距離 5 が確定,

f:id:cocoatomo:20100920232559j:image

となり無事全てのノードの最短経路と最短距離が求まりました.

途中説明を省略したところはちょうど良い練習問題なので, どういったアルゴリズムで決定されていったか考えてみてください.

(というのが講義などでの便利な言い回しですよね〜.)

どこがボトルネックなのか?

さてここで問題ですが,「上の Dijkstra 法での解放では S, い, は, ろ, に, ほ, の順に最短経路が決まっていったが, この順序は前後することがあるか? もしくは前後させることができるか?」についてはどうでしょう?

つまり, Dijkstra 法は「玉入れ」なのか「リレー」なのか? という問いです.

答えは少し下に書くのでちょっと考えてみてください.















分かりましたか? 答えは「リレー」です.

その理由も答えられますか?


Dijkstra 法のポイントは, 『まだ最短経路が決定していないノードのうちスタートノードからの最短距離が「最短なもの」』を選んでいくことにあります. 最短という言葉がたくさん出てきましたが, 着目すべきは鉤括弧でくくった「最短なもの」です.

並列処理が得意な処理は, 小分けにできてそれぞれが独立している処理です. しかしこの Dijkstra 法では各ステップは「最短なもの」という 1 つしかないものを扱うことになります. 1 つのものはどうやったって小分けにはできません.

確かにどれが「最短なもの」かどうか調べるのに並列処理が使えますが, 最短かどうか比較するデータが全て出揃わないと「最短」が決定できません.

こういった他の処理の待ちが発生してしまってはせっかくの並列処理の恩恵が減ってしまいます.

ちょっと難しい言い方をすると,「ローカルな処理に還元するのが並列処理の特徴なのだが, グローバルなデータが必要になってしまってそのメリットを阻害している」となります.

(ちょっと自信が無いのですが, 「グローバルなデータ」の「グローバル」は CAP 定理 (仮説) で言うところの Consistency でしょうか?)

かと言って勝手に処理を進めてしまっては,「最短なもの」だと思って処理を進めていたが実は違った, という事態が発生し計算のやり直しになります.

どう解消したらいいのか?

上で述べた通り, そもそもアルゴリズムが並列処理に向いてないので, そのまま使うのは諦めます. (これこそ CAP 定理か?)

今欲しい並列処理のメリットは速度なので, そのために以下のデメリットを甘受します.

  1. 解の完全性を捨てる
  2. 対象とするグラフを絞る

1 番目の方法は, 最短経路が完全に決まる前に「これが最短なものだ」と仮定して, 次の探索を始めてしまう方法です. この方法ならそこそこ速く解が求まりますが, 再計算が必要になる可能性があるのが痛いところです.

2 番目の方法は, グラフの形をある程度規定してしまってアルゴリズムのチューニングをする方法です. 「解の完全性」と「求解のスピード」のトレードオフをチューニングする感じです.


ここから先はさらに個別の話になるので, また次の機会に記事を書こうと思います.

コメントでも Twitter でも感想もらえると嬉しいです! さらなる要望だともっと嬉しいです!!

つ【http://twitter.com/cocoatomo

それではっ!