週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
とりあえずさくっとEdmonds-Karp, Dinitz, Ahuja-Orlin, Goldberg-Tarjanを書いて uva 1459に投稿してみました。グラフはすべて隣接行列で表現して、vector<vector<int> >に保存しています。 結果はそれぞれ1547, 157, 1360, 344 ms。pkuは最適化してくれないのでvectorで多次元配列を作ると最大100倍くらい遅くなった記憶がありますが、その中では適当な速さで動いているようです。ところでDinitz何か壊れてませんか?何でこんなに爆速なんでしょう。

Ahuja-Orlinはちゃんと論文を読んでないのでおかしい可能性が高いです。 それから、Ahuja-Orlinは流量を1づつしか増やせないようなグラフだと効果はないですよね。よくわかってませんが。

Goldberg-Tarjanは頂点の選び方もheuristicsも何もしていません。queueにexcited verticesを保存して順に取り出しただけ。これをpriority_queueにすると頂点をもう少しまじめに選べるはずです。そのほかのheuristicsはまったくわかっていません。文献は元論文でいいのでしょうか。

次はベンチマークです。速度計測のために最大流問題をたくさん生成するの必要があります。 たとえばグラフの形状だと、頂点数をNとして辺の数がO(N), O(N^(1.5)), O(N^2)くらいの完全ランダム、二部グラフあたりを用意すればよさそうです。一方容量はよくわかりません。ランダムからはじめますか。それとは別にいくつかのアルゴリズムに対する病的ケースが必要ですがこれもわかりません。 nyaasanはどういうグラフを作ったのか気になります。

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