Daniel Marcus Graph Theory を読む。 [無断転載禁止]©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
Daniel Marcus Graph Theory を読む。 419 名前:デフォルトの名無しさん[] 投稿日:2017/06/27(火) 13:16:02.75 ID:NGLAHv1W
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』(近代科学社)を読んでいます。
G のトポロジカルラベリングについては説明があるのですが、トポロジカルソートの応用例が
全く書かれていません。
勉強するモチベーションが全くありません。
著者は一体何を考えているのでしょうか?
424 名前:デフォルトの名無しさん[] 投稿日:2017/06/27(火) 19:32:13.18 ID:NGLAHv1W
あ、その後の有向無閉路ネットワークの最長パスを求めるアルゴリズムで
トポロジカルラベリングが使われていました。
なかなか面白い応用ですね。
この本、説明にちょっと粗雑なところもありますが、見せ場があって楽しいですね。
425 名前:デフォルトの名無しさん[] 投稿日:2017/06/27(火) 19:34:40.25 ID:NGLAHv1W
有向無閉路ネットワークという制限が強すぎますね。
でもこの制限のおかげでちょっと面白いトポロジカルラベリングの応用例が見れたわけですね。 431 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 05:10:12.09 ID:6P8PW2pA
>>430
そのインド人の本は、アルゴリズムの正当性のまともな説明がありません。
計算量の評価についてもまともな説明がありmせん。
セジウィックのAlgorithms 4th Editionはいい本ですが、計算量の評価については
まともな説明がないように思います。
432 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 05:17:01.98 ID:6P8PW2pA
D40
T をグラフ G の全域木とする。
C を G のサイクルとする。
AB を C および T に含まれる辺とする。
このとき、 T から AB を除去し、辺 UV を追加したときに、
依然として G の全域木であるような辺 UV が C の中に
含まれることを示せ。
433 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 06:24:05.46 ID:6P8PW2pA
>>432
T は木であるからサイクルを含まない。
よって、 C には T に含まれないような辺が少なくとも一つは存在する。
T は全域木であるから、そのような辺の両端点を結ぶ T の辺のみからなる(一意的な)パスが存在する。
仮に、 T に含まれないような C の辺たちの両端点を結ぶ T の辺のみからなるパスたちがすべて AB を含まない
と仮定すると、 A から B への T の辺のみからなるパスで辺 AB を含まないようなものが存在することになる。
A, B という A から B へのパスは、辺 AB を含み T の辺のみからなる。よって、 A から B への T の辺のみから
なるパスが2つ以上存在することになるが、これは木の性質に反する。
よって、 T に含まれないような C の辺たちの両端点を結ぶ T の辺のみからなるパスたちの中には、 AB を含む
ようなものが存在する。そのようなパスを U, …, A, B, …, V とする。 T から AB を除去し、辺 UV を追加し
たときにできる部分グラフは明らかに T と同じ数の辺をもち、依然として連結なままである。点の数が v で
辺の数が v - 1 であるような連結なグラフは木であるから、そうような部分グラフは木である。 435 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 10:22:23.33 ID:6P8PW2pA
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』(近代科学社)を読んでいます。
↓は、ある点から各点への最長パスを求めるプログラムのメイン関数です。
「出発点を入力してください」などと出力していますが、出発点は 1 でないとダメです。
なぜかというと depth_first() 関数がかならず 1 から深さ優先探索を開始するからです。
↓を見ると、あたかも、出発点に選択の余地があるかのようです。なぜ、こんなことを
しているのか意味不明です。
int main(void){
■■■■directed_network_input();
■■■■// 有向ネットワークの辺数m,点数n,各辺の始点,終点,長さが決定される
■■■■dicomp_incidence_list_construct(); // 接続辺リストが構成される
■■■■printf("出発点を入力してください\n");
■■■■scanf("%d", &s);
■■■■printf("出発点 = %d \n", s); // sからすべての点が到達可能であることを仮定
■■■■depth_first(); // 深さ優先探索をして後行順ラベルを求める
■■■■tpsort(); // トポロジカルソートを行う(tporder[1]==sとなることを仮定)
■■■■longestpath_from(s);// sからの到達可能な点への最長パスが計算される
■■■■longestpath_output();// sからの到達可能な点への最長パスが出力される
■■■■return 0;
} 436 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 10:54:52.65 ID:6P8PW2pA
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』(近代科学社)を読んでいます。
ひどいバグを発見しました。
void longestpath_from(int s){// sからの到達可能な点への最長パスを計算する関数
■■■■int a, j, v, w;
■■■■dmax[s]=0; // sからsへの最長パスの長さは0である
■■■■path[s]=0; // sからの到達可能な点への最長パス木の根がsである
■■■■for (j = 1; j <= n; j++) {// トポロジカルソートに基づいて
■■■■■■■■v= tporder[j];
■■■■■■■■// sからvまでの最長パスの長さdmax[v]とパス上でvの直前の点path[v]の計算
■■■■■■■■a=revedgefirst[v]; // vを終点とする辺のリストの先頭の辺がaである
■■■■■■■■w=tail[a]; // wはaの始点
■■■■■■■■if(j == 1) printf("v = %2d, a = %2d, w = %2d", v, a, w); //debug
■■■■■■■■dmax[v]=dmax[w]+length[a]; // 式(4.2)に基づくdmax[v]の初期設定
■■■■■■■■path[v]=w; // 式(4.2)に基づくpath[v]の初期設定
■■■■■■■■a=revedgenext[a]; // aの次の辺をaとする
■■■■■■■■while (a != 0) {// vを終点とする辺のリストの末尾の辺になるまで繰り返す
■■■■■■■■■■■■w=tail[a]; // wはaの始点
■■■■■■■■■■■■if (dmax[v] < dmax[w]+length[a]){// wを経由したほうがより長いとき
■■■■■■■■■■■■■■■■dmax[v] = dmax[w]+length[a]; // wを経由するほうに更新する
■■■■■■■■■■■■■■■■path[v]=a; // aに更新する
■■■■■■■■■■■■}
■■■■■■■■■■■■a=revedgenext[a]; // aの次の辺をaとする
■■■■■■■■}
■■■■}
} 438 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 11:02:48.67 ID:6P8PW2pA
↑の for 文は j = 1 から始まっています。
v == tporder[1] == 1 です。
a == revedgefirst[1] == 0 です。
ところが、この本では配列のインデックスは 1 からしか利用していません。
インデックスが 0 の要素は初期化すらしていません。
どうも配列を初期化しないと値は不定だそうですが、実際には 0 で初期化されることが
多いようです。
仕様では不定であるはずの
tail[0]
dmax[0]
length[0]
がたまたま 0 で初期化されるため、偶然、問題なく動作しています。
正しくは、
for 文は j = 2 から始めなくては駄目です。
439 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 11:19:51.44 ID:6P8PW2pA
あ、もう一つバグがありました↑
path[v]=w; // 式(4.2)に基づくpath[v]の初期設定
となっていますが、
path[v]=a; // 式(4.2)に基づくpath[v]の初期設定
でなければなりません。 441 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 12:34:24.00 ID:6P8PW2pA
>>440
そうですが、
for(j = 1;
とすると
意図せず配列[0]を使うことになってしまいます。
この値がたまたま 0 で初期化されていて、かつ 0 であれば正しく動くため、
問題が表面化していないだけです。
442 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 12:37:24.37 ID:6P8PW2pA
有向無閉路ネットワークの最長パスをトポロジカルラベリングを利用して、
求めるアルゴリズムって他の本に載っていますか?
あまりにも特殊すぎて載っていないのではないかと推測しますが。
この本は、鮮やかに解けるように問題を特殊化して見せ場を作っていますね。
443 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 13:17:27.40 ID:6P8PW2pA
>>426
その本を読むのでしたら、
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』(近代科学社)
のほうがCプログラムも載っていますし、面白いと思いますよ。
オイラーグラフの一筆書きのプログラムがあったりします。 番組冒頭、伊集院は豊田氏による元秘書への暴言を録音した模様を、テレビが
短時間に何度も流すことに言及していた。元秘書の男性が運転中に録音した
ボイスレコーダーには、豊田氏とみられる女性の声で「このハゲーー!!」
違うだろ!!」などと罵倒するほか、この男性を殴ったとみられる打撃音も
収められている。
伊集院は「『ハゲーー!!』ってところを3〜5分のニュースで4回くらい
オンエアするんだよね。多くない?」と疑問を口にする。続けて、
精神的苦痛を受ける人も世間にいると伊集院は持論を展開し「ハゲてる人
はこたえてると思うよ、相当ね」「あと、ああいう圧に耐えながら仕事
している人は、怖ぇと思うんだけどな」と指摘したのだった。 439 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 11:19:51.44 ID:6P8PW2pA
あ、もう一つバグがありました↑
path[v]=w; // 式(4.2)に基づくpath[v]の初期設定
となっていますが、
path[v]=a; // 式(4.2)に基づくpath[v]の初期設定
でなければなりません。
441 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 12:34:24.00 ID:6P8PW2pA
>>440
そうですが、
for(j = 1;
とすると
意図せず配列[0]を使うことになってしまいます。
この値がたまたま 0 で初期化されていて、かつ 0 であれば正しく動くため、
問題が表面化していないだけです。
442 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 12:37:24.37 ID:6P8PW2pA
有向無閉路ネットワークの最長パスをトポロジカルラベリングを利用して、
求めるアルゴリズムって他の本に載っていますか?
あまりにも特殊すぎて載っていないのではないかと推測しますが。
この本は、鮮やかに解けるように問題を特殊化して見せ場を作っていますね。
443 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 13:17:27.40 ID:6P8PW2pA
>>426
その本を読むのでしたら、
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』(近代科学社)
のほうがCプログラムも載っていますし、面白いと思いますよ。
オイラーグラフの一筆書きのプログラムがあったりします。
447 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 18:29:25.09 ID:6P8PW2pA
>>444
このプログラムだけ見てももちろん分からないと思います。
a == revedgefirst[1] == 0 なので、 tail[a] == tail[0] です。
448 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 18:29:51.34 ID:6P8PW2pA
訂正します:
>>445
このプログラムだけ見てももちろん分からないと思います。
a == revedgefirst[1] == 0 なので、 tail[a] == tail[0] です。
449 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 18:33:38.48 ID:6P8PW2pA
さらに、
v == tporder[1] == 1 です。 456 名前:デフォルトの名無しさん[] 投稿日:2017/07/01(土) 09:37:54.54 ID:OLSj8alI
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』(近代科学社)
ホップクロフト - カープのアルゴリズムのところを読んでいます。
do {// マッチされていない左端点からマッチされていない右端点へのパスがある限り
■■■■levelgraph(); // レベルグラフの構成
■■■■if (t_found != n+2) augmentation(); // パスがあるときにはマッチングの更新
} while (t_found != n+2);
などというコードがあります。
do {// マッチされていない左端点からマッチされていない右端点へのパスがある限り
■■■■levelgraph(); // レベルグラフの構成
■■■■if (t_found == n+2) break;
■■■■else augmentation(); // パスがあるときにはマッチングの更新
} while (1);
と書いた方が分かりやすいですよね。
augmentation() 内では、グローバル変数 t_found の値は変更されません。
なので、以下のように書くのが標準的だと思います。
levelgraph();
while(t_found != n + 2){
■■■■augmentation();
■■■■levelgraph();
} 457 名前:デフォルトの名無しさん[] 投稿日:2017/07/01(土) 09:42:20.68 ID:OLSj8alI
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』(近代科学社)を読んでいます。
a = edgefirst[v1];
while(a != 0){
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
a = edgenext[a];
}
などというコードが本書のソースコードのいたるところで使われています。
↓のように書くべきですよね。
for(a = edgefirst[v1]; a != 0; a = edgenext[a]){
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
}
458 名前:デフォルトの名無しさん[] 投稿日:2017/07/01(土) 09:46:11.85 ID:OLSj8alI
茨木俊秀さんの本でも感じましたが、ひどいコードを書く人が多いですよね。
一番、驚いたのが野崎昭弘さんの本です。
goto 文を使わなくていいところで常用しています。
461 名前:デフォルトの名無しさん[] 投稿日:2017/07/01(土) 09:59:03.29 ID:OLSj8alI
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』(近代科学社)
ホップクロフト - カープのアルゴリズムのところを読んでいます。
for (v = 1; v <= n; v++) parent[v] = unvisited;
というコードがあります。
点 v の親の処理ですが、深さ優先探索で使う定数である unvisited == -1 を流用しています。
親は訪問するものではないにもかかわらずです。
単に -1 という値が使いたいだけです。
ひどいコードです。 微積分ばかり読んで馬鹿アスペは大丈夫な人なのでしょうか? Graph Minor Theorem まで読み終わった 真田重雄は地獄へ落ちて幾十年だな
この世と地獄では時の流れが違うだろうけど ■ このスレッドは過去ログ倉庫に格納されています