0001132人目の素数さん2017/06/09(金) 20:17:59.42ID:qUOneyKn
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
有向無閉路ネットワークという制限が強すぎますね。
でもこの制限のおかげでちょっと面白いトポロジカルラベリングの応用例が見れたわけですね。
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]の初期設定
でなければなりません。
番組冒頭、伊集院は豊田氏による元秘書への暴言を録音した模様を、テレビが
短時間に何度も流すことに言及していた。元秘書の男性が運転中に録音した
ボイスレコーダーには、豊田氏とみられる女性の声で「このハゲーー!!」
違うだろ!!」などと罵倒するほか、この男性を殴ったとみられる打撃音も
収められている。
伊集院は「『ハゲーー!!』ってところを3〜5分のニュースで4回くらい
オンエアするんだよね。多くない?」と疑問を口にする。続けて、
精神的苦痛を受ける人も世間にいると伊集院は持論を展開し「ハゲてる人
はこたえてると思うよ、相当ね」「あと、ああいう圧に耐えながら仕事
している人は、怖ぇと思うんだけどな」と指摘したのだった。
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 まで読み終わった
0117132人目の素数さん2020/10/04(日) 22:37:52.35ID:3NNl8xHn
真田重雄は地獄へ落ちて幾十年だな
この世と地獄では時の流れが違うだろうけど