週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
論文の引用の仕方を忘れております。

読んだのは今井先生のを大体と、Ahujaのアルゴリズムの部分の半分。

今井先生のは基本は最大流アルゴリズムの速度の実測。ランダムグラフとグリッドと、それから実際のグラフ(鉄道網)を使っています。 選んだアルゴリズムにGoldberg-Tarjanがないのが残念。

速度の実測方法がわかったのが一番の収穫です。正確に言うと実測方法は別にたいしたことなくて、 たいしたことない実測方法で実測して論文になるとわかったのが一番の収穫です。 これを読むまでは、ランダムなグラフをどのように生成すればいいかいろいろ悩んでました。 一応グラフの連結などを調べたほうがいいかとか。 しかし論文を見た感じでは、余り何も考えなくてもよいようです。 たとえばグラフの連結性は各頂点の次数がある程度確保されれば自動的に満たされます。

それから、グリッドをグラフとして利用することは思いつきませんでした。 グラフが疎か密か位しか想定していなかったので、これも助かります。 次元を増やしたり、むしろN次元上にランダムに頂点を撒いてボロノイ図で接している兆点間を結んだりとかいろいろなパターンができそうです。

Ahujaのほうは、Ahuja-Orlinだと思っていたアルゴリズムがGabowのアルゴリズムだったことが一番の衝撃です。Ahuja-Orlinとして紹介されているアルゴリズムはまったく違う、Goldberg-Tarjanと同じポテンシャルを使うものでした。本人が書いているのでおそらくそれが正しいのでしょう。

スポンサーサイト
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/343-59905cc3
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。