【掲示板ご利用上の注意】

 ※題名は具体的に!
 ※学校の課題の丸投げ禁止!
 ※ソースの添付は「HTML変換ツール」で字下げ!
 ※返信の引用は最小限に!
 ※環境(OSとコンパイラ)や症状は具体的に詳しく!
 ※マルチポスト(多重投稿)は慎んで!

 詳しくはこちら



 本当はこんなに大きく書きたくはないのですが、なかなか守っていただけなくて…。
 守ってくださいね。お願いします。(by管理人)

C言語ソース⇒HTML形式ツール   掲示板2こちら


管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.21088

最大フローを求める際に計算時間を遅くしたり早くしたりしたい
投稿者---ヘタレプログラマー(2005/05/18 23:18:44)


最大フローを求める際に計算時間を遅くしたり早くしたりするには、
増大路を選択する際に残余容量の値をなるべく小さく(or大きく)なるような
経路を選択するべきだろうと考えてプログラムをつくったのですが、
いつまでたっても結果がでてこないので、
printf文をソースに挟めるなどでどこがおかしいか調べたら、
ラベリング後の経路選択のために導入した関数に原因があるようなので、
いろいろいじったのですが、結局改善されませんでした。

どうソースを変更すれば、改善されて、目的をみたすプログラムが
できるのでしょうか?どなたかご教授願います。

コンパイラ:Borland C++ Compiler
OS:WindowsXP

※プログラムは一緒に貼ろうと思ったら本文の既定をオーバーしてしまったので
 別に貼ろうと思います。
 ソースは、計算時間を遅らせる場合のもののつくりかけです。


この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> 作りかけのプログラムのソース 21090 ヘタレプログラマー 2005/05/18 23:42:41


No.21090

作りかけのプログラムのソース
投稿者---ヘタレプログラマー(2005/05/18 23:42:41)


あまりに長くて削っても削ってもエラーになるので、
ソースは↓に置きました。
http://tool-ya.ddo.jp/2ch/trash-box/file/20050518233531212.txt

また、出したい実行結果の例も記しました。
(参考になるかどうかはわかりませんが・・・)

/*------望まれる実行結果---------
容量を乱数で指定しますか?
0:容量を乱数できめる 1:adj.datで指定した容量にする
1
グラフの種類  1:有向グラフ 0:無向グラフ
1

 * Flow augmented by  1 through  4 +  3 +  2 +  1
 * Flow augmented by  1 through  4 +  2 +  3 +  1
 (↑これの100回繰り返し)

number of nodes is 4 and number of edges is 5.
input source s and sink t are 1 and 4,respectively
That is, n=4,m=5;  s=1,t=4
tail    head     cap    flow
   1       2     100     100
   1       3     100     100
   2       3       1       0
   2       4     100     100
   3       4     100     100
flow value = 200

augmented count = 200
executed time = ?.?????? sec

*/



この投稿にコメントする

削除パスワード

No.21092

Re:作りかけのプログラムのソース
投稿者---アンドロオイド(2005/05/19 02:25:03)


単なるアドバイスです。
この質問の仕方では誰も理解してくれませんよ。
 私は趣味でグラフ理論を勉強していますし、関連するプログラムも
作っていますので言っていることはわかりますが、ここのレベルとはかけ離れているようです。

無向グラフに関するプログラムはいろいろ作っていますが、有向グラフはまだなので、ソースは参考にさせてもらいます。
そもそも、有向グラフの構造をきちんと定義できてから最大流問題などの
応用に取り組むべきですがその辺は大丈夫なのですよね。
それから、興味本位ですが、問題の背景を教えてもらえればうれしいです。同好の士だったら情報交換したいですね。
プログラマーということは業務のプログラムですか。そうならば、ここよりも上司にきいたほうが早いのでは。
それから最大流問題はNP完全じゃなかったかしら。
そうならば、ノード数が20程度でも何日もかかるかもしれないですね。
勿論アルゴリズムしだいですが。


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧