データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net

**デフォルトの名無しさん転載ダメ©2ch.net** · 2016/06/19(日) 14:47:29.63

このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。

アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。

　　　　　　　　　　　　　　　　　　京都大学霊長類研究所

データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2
http://echo.2ch.net/test/read.cgi/tech/1362301811/

【関連スレ】
3Dアルゴリズム全般
http://toro.2ch.net/test/read.cgi/tech/1164171086/
＜集大成＞アルゴリズム大辞典
http://toro.2ch.net/test/read.cgi/tech/1086272325/
アルゴリズム総合スレ in ム板
http://toro.2ch.net/test/read.cgi/tech/1217773415/

アルゴリズムとデータ構造 - Kaneko Lab.
ttp://www.kkaneko.com/adp/algo/index.html
アルゴリズムとデータ構造 - ソースコード探険隊
ttp://www.codereading.com/algo_and_ds/
各種アルゴリズムの C++ による実装 - Spaghetti Source
ttp://www.prefield.com/algorithm/
アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP
ttp://vipprog.net/wiki/algo_and_data_const.html

**デフォルトの名無しさん** · 2017/06/21(水) 13:33:59.73

要するに、↓が間違っているわけです。

「補木辺は、同じ深さの点を結んでいるか、あるいは深さが 1 異なる点を結んでいることに注意しよう。」

**デフォルトの名無しさん** · 2017/06/21(水) 13:55:32.90

ここじゃなくて著者なり出版社なりに連絡しなよ
その方がちゃんと議論できるだろうし修正されればあとから読む人の為になるよ

**デフォルトの名無しさん** · 2017/06/21(水) 14:30:39.96

>>400
幅優先で探索木作ったら同じ深さを結ぶ補木辺ができるから二部グラフでないことがわかる

**デフォルトの名無しさん** · 2017/06/21(水) 16:12:29.38

>394
三枚目の図は、反例になっていない。
あなたが幅優先探索を理解できていないだけで、書籍の記述は間違っていないよ。
根でない2つの頂点は、どちらも、根から辺が張られていて、根と隣接しているのだから、同じ深さの位置にある。

**デフォルトの名無しさん** · 2017/06/21(水) 18:57:35.69

あ、勘違いしました。

無向グラフでしたね。

**デフォルトの名無しさん** · 2017/06/21(水) 19:28:34.24

教科書だって間違いはいくらでもある。
だからといって、間違いらしきものを見つけて喜々としてあげつらうのではなく、
自分の解釈ではこうだが違うのだろうかという態度で質問しておけばよかったね。

**デフォルトの名無しさん** · 2017/06/21(水) 22:04:49.64

何がいんだろ

**デフォルトの名無しさん** · 2017/06/23(金) 09:05:15.05

>>393-394
他人の誤りを指摘するときに
自分でも誤るとか恥ずかしくないか

**デフォルトの名無しさん** · 2017/06/23(金) 13:07:58.26

間違いを恐れるな

**デフォルトの名無しさん** · 2017/06/23(金) 13:38:13.56

馬鹿、アスペを恐れるな

**デフォルトの名無しさん** · 2017/06/23(金) 19:23:07.84

KIZLA7]]]

%≒72%,M,L,TO"JYOJA"

**デフォルトの名無しさん** · 2017/06/26(月) 15:07:57.81

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）ですが、この
本には強連結成分分解のアルゴリズムは書いてあるのですが、その正しさについて
の説明がありません。

「アルゴリズムの正当性については演習問題とする。」などと書かれているだけです。
そして、解答がありません。

解答をつけないほど簡単な問題でしょうか？

エイホ、ホップクロフト、ウルマン著『データ構造とアルゴリズム』に分かりやすい説明がありました。

**デフォルトの名無しさん** · 2017/06/26(月) 15:09:29.86

あ、よくみたら解答がありました。

**デフォルトの名無しさん** · 2017/06/26(月) 15:14:33.33

強連結成分分解のアルゴリズムはグラフ理論的な観点からは興味深いですが、
応用についてはあまりないようですね。

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）の「はじめに」に
「強連結成分分解はシステムの故障診断や効率的解析への応用があると言われている。」
などと書かれいます。浅野さん自身は応用について具体的な詳細を知らないと宣言して
いるようなものですね。

**デフォルトの名無しさん** · 2017/06/26(月) 15:27:14.29

ステマ乙としか

**デフォルトの名無しさん** · 2017/06/26(月) 15:32:39.93

ところで、LEDAというライブラリはお勧めですか？

**デフォルトの名無しさん** · 2017/06/26(月) 16:23:39.69

病人が粘着してる

**デフォルトの名無しさん** · 2017/06/27(火) 13:16:02.75

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。

G のトポロジカルラベリングについては説明があるのですが、トポロジカルソートの応用例が
全く書かれていません。

勉強するモチベーションが全くありません。

著者は一体何を考えているのでしょうか？

**デフォルトの名無しさん** · 2017/06/27(火) 14:05:21.18

NGにしてほしいんじゃね

**デフォルトの名無しさん** · 2017/06/27(火) 14:08:46.74

勉強しなきゃいいのに

**デフォルトの名無しさん** · 2017/06/27(火) 15:22:28.20

馬鹿のアスペの気持ちなんか分からん

**デフォルトの名無しさん** · 2017/06/27(火) 17:51:10.93

本人だったりして

**デフォルトの名無しさん** · 2017/06/27(火) 19:32:13.18

あ、その後の有向無閉路ネットワークの最長パスを求めるアルゴリズムで
トポロジカルラベリングが使われていました。

なかなか面白い応用ですね。

この本、説明にちょっと粗雑なところもありますが、見せ場があって楽しいですね。

**デフォルトの名無しさん** · 2017/06/27(火) 19:34:40.25

有向無閉路ネットワークという制限が強すぎますね。

でもこの制限のおかげでちょっと面白いトポロジカルラベリングの応用例が見れたわけですね。

**デフォルトの名無しさん** · 2017/06/27(火) 21:47:11.43

プログラミング・コンテスト・チャレンジブック、第2版、2012

ほとんど全てのアルゴリズムを網羅。
問題数も多く、パズル感覚で楽しめる。
AIやシミュレーションゲームの参考になる

**デフォルトの名無しさん** · 2017/06/27(火) 21:55:21.79

>>426

網羅からはほど遠いと思います。

**デフォルトの名無しさん** · 2017/06/27(火) 21:58:43.82

>>426

それとアルゴリズムの正当性のまともな説明がありません。

計算量の評価についてもまともな説明はありません。

**デフォルトの名無しさん** · 2017/06/27(火) 22:34:26.12

一から百まで説明しないとダメな奴、すなわち無能

**デフォルトの名無しさん** · 2017/06/28(水) 02:20:53.63

入門データ構造とアルゴリズム、2013、オライリー
Narasimha Karumanchi(インド人) 著

アルゴリズムなら、セジウィックでも読めば？

プログラミング・コンテスト・チャレンジブックは、
コンテストの問題を集めた本だから、便利

一々、ウェブサイトの問題を見なくても良いから、楽

**デフォルトの名無しさん** · 2017/06/28(水) 05:10:12.09

>>430

そのインド人の本は、アルゴリズムの正当性のまともな説明がありません。

計算量の評価についてもまともな説明がありｍせん。

セジウィックのAlgorithms 4th Editionはいい本ですが、計算量の評価については
まともな説明がないように思います。

**デフォルトの名無しさん** · 2017/06/28(水) 05:17:01.98

D40

T をグラフ G の全域木とする。
C を G のサイクルとする。
AB を C および T に含まれる辺とする。

このとき、 T から AB を除去し、辺 UV を追加したときに、
依然として G の全域木であるような辺 UV が C の中に
含まれることを示せ。

**デフォルトの名無しさん** · 2017/06/28(水) 06:24:05.46

>>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 であるような連結なグラフは木であるから、そうような部分グラフは木である。

**デフォルトの名無しさん** · 2017/06/28(水) 06:52:24.02

>>432

ヒントとして、「T - AB は2成分からなる森である」と書いてあるのですが、
このヒントを利用した解答はどうなるのでしょうか？

**デフォルトの名無しさん** · 2017/06/28(水) 10:22:23.33

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。

↓は、ある点から各点への最長パスを求めるプログラムのメイン関数です。
「出発点を入力してください」などと出力していますが、出発点は 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;
}

**デフォルトの名無しさん** · 2017/06/28(水) 10:54:52.65

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。

ひどいバグを発見しました。

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とする
■■■■■■■■}
■■■■}
}

**デフォルトの名無しさん** · 2017/06/28(水) 10:57:07.89

366 :nobodyさん 2017/05/29(月) 16:07:39.16 ID:6v4UcGhE
今回の民法改正、ソフトウェア受託開発の場合、(検収後ではなく)バグ発見後１年瑕疵担保責任があるということで、地獄かよ、と思ったが、
元々問題が起きがちな受託案件がビジネス的に成立しなくなることで強制的に業界再編につながるなら良いことかもと思うようになった。
一部で地獄を見ても。
https://twitter.com/yukihiro_matz/status/869061879389343744

367 :nobodyさん 2017/05/29(月) 16:28:06.55 ID:6v4UcGhE
ニュース - 改正民法が成立、「瑕疵担保責任」などシステム開発契約に影響大：ITpro
http://b.hatena.ne.jp/entry/itpro.nikkeibp.co.jp/atcl/news/17/052601508/

372 :nobodyさん2017/05/29(月) 19:10:37.12 ID:???
Railsでシステム作って納品する
↓
Railsはマイナー、メジャーのアップデートが半年以内に必ずある
↓
客がアップデートする。アップデートによるエラーやバグ、動作の不具合に気づく
↓
気づいてから1年以内に通知すれば、5年間無料保証ゲット
↓
つまりRailsがアップデートするたびに、無償の修正作業を発生するということかな

376 :nobodyさん2017/05/30(火) 09:20:20.09 ID:L5po86sS
>>378>>379>>375
客が瑕疵担保責任法の法改正を知ってくると思うから、今後5年無償保証をお願いされるだろう
営業がそれでも仕事を取ってこれるか？たぶん無理だろう。無限の直していたら赤字になる。
こういう保守に弱い言語、ころころ仕様が変わる言語は仕事として発生しなくなってくる。
これは変わり目だ。お前らも早く逃げたほうがいいぞ。RubyやPHPなど動的言語は確実に廃れる。
保守に強い言語のみ生き残れる。

**デフォルトの名無しさん** · 2017/06/28(水) 11:02:48.67

↑の for 文は j = 1 から始まっています。

v == tporder[1] == 1 です。
a == revedgefirst[1] == 0 です。

ところが、この本では配列のインデックスは 1 からしか利用していません。
インデックスが 0 の要素は初期化すらしていません。
どうも配列を初期化しないと値は不定だそうですが、実際には 0 で初期化されることが
多いようです。

仕様では不定であるはずの

tail[0]
dmax[0]
length[0]

がたまたま 0 で初期化されるため、偶然、問題なく動作しています。

正しくは、

for 文は j = 2 から始めなくては駄目です。

**デフォルトの名無しさん** · 2017/06/28(水) 11:19:51.44

あ、もう一つバグがありました↑

path[v]=w; // 式(4.2)に基づくpath[v]の初期設定

となっていますが、

path[v]=a; // 式(4.2)に基づくpath[v]の初期設定

でなければなりません。

**デフォルトの名無しさん** · 2017/06/28(水) 12:31:24.06

>>438
>インデックスが 0 の要素は初期化すらしていません

配列[0] を使わないのなら、初期化する必要はない

**デフォルトの名無しさん** · 2017/06/28(水) 12:34:24.00

>>440

そうですが、

for(j = 1;

とすると

意図せず配列[0]を使うことになってしまいます。

この値がたまたま 0 で初期化されていて、かつ 0 であれば正しく動くため、
問題が表面化していないだけです。

**デフォルトの名無しさん** · 2017/06/28(水) 12:37:24.37

有向無閉路ネットワークの最長パスをトポロジカルラベリングを利用して、
求めるアルゴリズムって他の本に載っていますか？

あまりにも特殊すぎて載っていないのではないかと推測しますが。

この本は、鮮やかに解けるように問題を特殊化して見せ場を作っていますね。

**デフォルトの名無しさん** · 2017/06/28(水) 13:17:27.40

>>426

その本を読むのでしたら、

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）

のほうがCプログラムも載っていますし、面白いと思いますよ。

オイラーグラフの一筆書きのプログラムがあったりします。

**デフォルトの名無しさん** · 2017/06/28(水) 14:35:33.86

外部変数は0で初期化される。

**デフォルトの名無しさん** · 2017/06/28(水) 15:46:50.33

j=1で始まってんのに意図せず配列[0]を参照するの意味がわからん

**デフォルトの名無しさん** · 2017/06/28(水) 16:26:43.89

それでも馬鹿のアスペの荒らしをスルーできない

**デフォルトの名無しさん** · 2017/06/28(水) 18:29:25.09

>>444

このプログラムだけ見てももちろん分からないと思います。

a == revedgefirst[1] == 0 なので、 tail[a] == tail[0] です。

**デフォルトの名無しさん** · 2017/06/28(水) 18:29:51.34

訂正します：

>>445

このプログラムだけ見てももちろん分からないと思います。

a == revedgefirst[1] == 0 なので、 tail[a] == tail[0] です。

**デフォルトの名無しさん** · 2017/06/28(水) 18:33:38.48

さらに、

v == tporder[1] == 1 です。

**デフォルトの名無しさん** · 2017/06/29(木) 11:58:28.12

http://imgur.com/A84Qz1i.jpg
http://imgur.com/NsXCsS1.jpg
http://imgur.com/Bm7ANHm.jpg
http://imgur.com/iSqMNes.jpg

↑は浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）です。
1枚目と2枚目の画像が連結な有向オイラーグラフの一筆書きを求めるアルゴリズムです。
3枚目と4枚目の画像がそのアルゴリズムの正しさの証明です。

「連結グラフ G が一筆書きできるための必要十分条件は、 G がオイラーであることである。」

という定理の証明において、十分性は、↑の3枚目と4枚目の画像の定理5.3により分かるということが書いてあります。

↑の3枚目と4枚目の画像を読めば分かりますが、十分性について証明されていないように思います。

どうでしょうか？

**デフォルトの名無しさん** · 2017/06/29(木) 12:19:34.40

むしろ、十分性が成り立つことを前提にしてアルゴリズムの正しさを証明しているように思います。

**デフォルトの名無しさん** · 2017/06/30(金) 09:51:08.15

粘着

**デフォルトの名無しさん** · 2017/06/30(金) 13:39:18.75

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）

ホップクロフト - カープのアルゴリズムのところを読んでいます。

段々、面白いアルゴリズムが登場してきていますね。

日本語のアルゴリズムの本は本当に初歩的な本が多いですが、なぜなのでしょうか？

例えば、ホップクロフト - カープのアルゴリズムが載っている本はあるでしょうか？

日本語の本に載っているのは、

リスト、ハッシュ、ヒープ、2分探索木、平衡木、ソート、最短経路、文字列

とかそんなもんだけですよね。

**デフォルトの名無しさん** · 2017/06/30(金) 19:08:50.27

初歩的な問題すら理解できずにドヤ顔で間違った反例晒すやつがいるからだよ

**デフォルトの名無しさん** · 2017/06/30(金) 20:21:27.99

それ以上の難解アルゴリズムに挑戦する頭脳があれば英語の習得は容易いので、結果すでにある英語本を買うようになると予想

**デフォルトの名無しさん** · 2017/07/01(土) 09:37:54.54

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）
ホップクロフト - カープのアルゴリズムのところを読んでいます。

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();
}

**デフォルトの名無しさん** · 2017/07/01(土) 09:42:20.68

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。

a = edgefirst[v1];
while(a != 0){
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
a = edgenext[a];
}

などというコードが本書のソースコードのいたるところで使われています。

↓のように書くべきですよね。

for(a = edgefirst[v1]; a != 0; a = edgenext[a]){
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
}

**デフォルトの名無しさん** · 2017/07/01(土) 09:46:11.85

茨木俊秀さんの本でも感じましたが、ひどいコードを書く人が多いですよね。

一番、驚いたのが野崎昭弘さんの本です。

goto 文を使わなくていいところで常用しています。

**デフォルトの名無しさん** · 2017/07/01(土) 09:53:17.51

粗さがしが得意みたいだから、出版社で校正でもやったら良いのでは？

**デフォルトの名無しさん** · 2017/07/01(土) 09:55:39.01

伏字かと思ったらインデントかよ。
これが見やすいと思ったんだろうか？ここに辿り着くまでの思考過程を見てみたいわ。

**デフォルトの名無しさん** · 2017/07/01(土) 09:59:03.29

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）
ホップクロフト - カープのアルゴリズムのところを読んでいます。

for (v = 1; v <= n; v++) parent[v] = unvisited;

というコードがあります。

点 v の親の処理ですが、深さ優先探索で使う定数である unvisited == -1 を流用しています。
親は訪問するものではないにもかかわらずです。
単に -1 という値が使いたいだけです。

ひどいコードです。

**デフォルトの名無しさん** · 2017/07/01(土) 12:24:50.45

>>460
基地外の思考過程なんて見たらSAN値下がるぞ。

**デフォルトの名無しさん** · 2017/07/01(土) 12:35:14.71

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）
ホップクロフト - カープのアルゴリズムのところを読んでいます。

このプログラムですが、意味不明に冗長なところがあるので超分かりにくいです。

もし、この本を読む人は、注意した方がいいです。

分かりやすい等価なコードにすこしずつ変えながら読んでいます。

**デフォルトの名無しさん** · 2017/07/01(土) 20:40:17.40

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）
ホップクロフト - カープのアルゴリズムのところを読んでいます。

プログラムに、非常に非効率な部分を発見しました。

深さ優先探索で最短パスを探す部分があるのですが、一つの最短パスを
発見した後も、うろうろと探索を続けています。 return 文で呼び出し元へと
遡って戻るべき箇所です。

具体的にいうと、p.95の void bipartite_dfs(int) 関数内の

bipartite_dfs(w1);

は、

bipartite_dfs(w1);
if(pathfound) return;

とすべきです。

**デフォルトの名無しさん** · 2017/07/01(土) 22:15:24.31

俺様のアスペ日記

**デフォルトの名無しさん** · 2017/07/01(土) 23:27:45.18

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）

のHopcroft-Karpのアルゴリズムのプログラムを一切変更を加えずに使用して、
Aizu Online Judgeの2部グラフのマッチングの問題を解かせてみたら、
1問目から正しい結果が得られませんでした。

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）

では一つの例に対して、プログラムをチェックしているだけです。
その例に対しては正しい結果が得られます。

著者はおそらく他の例についてはチェックしていないと思われます。

これから原因を究明しようと思います。

ちなみに

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）

での例ですが、この著者の旧著でも全く同じ例を使っています。

使いまわしですね。他の例は一度もチェックしていないようです。 👀
Rock54: Caution(BBR-MD5:0be15ced7fbdb9fdb4d0ce1929c1b82f)

**デフォルトの名無しさん** · 2017/07/01(土) 23:59:37.67

あ、勘違いでした。

入力のフォーマットが会津と浅野の本で違いました。

**デフォルトの名無しさん** · 2017/07/02(日) 12:42:08.55

マッチングといっても、いろいろな問題があるんですね。

安定マッチングと最大マッチングは互いに何の関係もない全く異なる問題ですね。

↓の講義は、安定マッチングについてですが、簡単ですね。

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/video-lectures/lecture-7-matching-problems/#vid_related

MITの微分積分の講義を見ると学生のレベルが低いという印象ですが、この講義を見ると
そうでもないような印象です。

**デフォルトの名無しさん** · 2017/07/02(日) 13:22:29.16

>>468

なんか明らかなことをダラダラと証明していますね。

**デフォルトの名無しさん** · 2017/07/03(月) 08:45:45.65

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）

を読んでいます。

定理：
G のマッチング M に対して、 M が最大マッチングであるための必要十分条件は M に
関する増加パスが存在しないことである。

という定理が書いてあります。

十分性の証明が長すぎます。見た目はちょっとすっきりとしていていいのですが、長くて
素朴な証明法ではありません。

**デフォルトの名無しさん** · 2017/07/03(月) 08:46:22.05

以下のような証明が素朴なよい証明だと思います。

G のマッチング M に対して、 M が最大マッチングであるための必要十分条件は M に関する増加パスが存在しないことである。

必要性は明らかである。

十分性について証明する。

G は連結である場合に証明できれば、 G が連結でない場合にも、明らかに定理は成り立つ。
そのため、 G は連結であると仮定する。

G には、 M に関する増加パスが存在しないと仮定する。
M の辺に接続されていない点をFreeな点と呼ぶことにする。

G にFreeな点が2点以上存在することはないことを背理法によって証明しよう。
a, b を G の任意のFreeな2点とする。 G は連結だから、 a, b を結ぶ単純なパスが存在する。
a = a_1, …, a_k = b をその単純なパスとする。
このとき、　a_1, …, a_i に含まれるFreeな点の数が 2 であるような i ≧ 2 が存在することは明らかである。
単純なパス a_1, …, a_i は明らかに増加パスである。
これは、 G には、 M に関する増加パスが存在しないという仮定に反する。

よって、 G にFreeな点が2点以上存在することはない

G にFreeな点が1点存在する場合には、 G の点の数は、奇数であり、明らかに M は最大マッチングである。
G にFreeな点が1点も存在しない場合には、 G の点の数は、偶数であり、明らかに M は最大マッチングである。

**デフォルトの名無しさん** · 2017/07/03(月) 08:55:27.46

なんか他の本を調べてみても、

>>471

のような素朴な証明法が載っていませんね。

ソートするアルゴリズムが存在することを示せ

という問題があったとして、答えとして、バブルソートをあげれば十分であるにもかかわらず、
ヒープソートをあげるようなもんですね。

**デフォルトの名無しさん** · 2017/07/03(月) 12:01:19.36

>471

頂点a b c d eがあって、
辺が、
a b
a c
a d のとき、
Mとして
a bを選べば、増加パスはないけど、
cとdはFreeな頂点になるのでは？

**デフォルトの名無しさん** · 2017/07/03(月) 12:17:16.61

>>473

ありがとうございます。

>>471
は間違いですね。

**デフォルトの名無しさん** · 2017/07/03(月) 22:09:21.73

>>474

ズコーッ

**デフォルトの名無しさん** · 2017/07/03(月) 23:57:03.23

>>474

ヽ(･ω･)/ｽﾞｺｰ

**デフォルトの名無しさん** · 2017/07/06(木) 14:52:18.01

松坂君はおつむ弱いなー

**デフォルトの名無しさん** · 2017/07/07(金) 10:19:21.25

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。

ネットワークフローについてですが、
ソースから流出する総フローが、
シンクに流入する総フローに
等しいということを自明のこととして、
証明していません。

これはOKなのでしょうか？

**デフォルトの名無しさん** · 2017/07/07(金) 10:33:49.72

おつむが弱いアスペ参上

**デフォルトの名無しさん** · 2017/07/07(金) 11:03:27.05

やはり証明は必要なんですね。
↓の本に証明が載っていました。

組合せ数学入門 II (共立全書)
C.L.リウ
https://www.amazon.co.jp/dp/4320005422

**デフォルトの名無しさん** · 2017/07/07(金) 11:04:16.11

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）

は、計算量の評価の説明がひどすぎます。

ほとんど結果しか書いていません。

**デフォルトの名無しさん** · 2017/07/07(金) 11:53:23.95

>>478

少し後のところで、
ソースから流出する総フローが、
シンクに流入する総フローに
等しいという結果を特別な場合として
含むような結果を示していました。

ソースから流出する総フローが、
シンクに流入する総フローに
等しいということが自明なことならば、
そのより一般化された結果も自明です。

著者の態度は矛盾していますね。

**デフォルトの名無しさん** · 2017/07/07(金) 13:13:44.59

僕の肛門から流出するソースの総フローがシンクに流入します

**デフォルトの名無しさん** · 2017/07/07(金) 17:37:48.39

今、ウィルソンのグラフ理論の本を見てみたのですが、内容がスカスカですね。

アルゴリズム的なグラフ理論の本のほうが分かりやすいし、面白いですね。

**デフォルトの名無しさん** · 2017/07/07(金) 19:30:12.19

「29歳既婚、2年前に会社を辞めた。ボードゲーム作りを始めて3700万円を
売り上げたけど何か聞きたいことはある？」回答いろいろ
http://labaq.com/archives/51880196.html
日本ボードゲーム界の異端児に聞く！ボードゲームデザイナーとして生きていくには？
https://bodoge.hoobby.net/columns/00013
カードゲームを自作する1　【自宅でカード印刷】
http://tanishi.org/?p=801
100円ショップでボードゲームを自作しよう
https://sites.google.com/site/jun1sboardgames/blog/makeyourbg
ノーアイデアでボードゲームを作ろう第1回「100円ショップで物を買う」
http://boardgamelove.com/archives/boardgame-make-1/
ボードゲーム市場がクラウドファンディングの出現で急成長を遂げ市場規模を拡大中
http://gigazine.net/news/20150820-board-game-crowdfunding/
自作ゲーム即売会「ゲームマーケット」に１万人超
http://www.nikkansports.com/general/nikkan/news/1750500.html
ボードゲームの展示イベント「ゲームマーケット」の成長記録からこれからの
市場に必要なことを妄想してみた。6年間の来場者数推移（2016年4月時点調べ）
https://bodoge.hoobby.net/columns/00001

**デフォルトの名無しさん** · 2017/07/08(土) 06:00:28.99

>>484
あ？　スカトロが何だって？

**デフォルトの名無しさん** · 2017/07/08(土) 09:51:52.03

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）の
Ford - Fulkerson　のアルゴリズムのプログラムを読んでいます。

ひどいプログラムです。

たとえば、深さ優先探索を行う関数を見てください↓

void dfs(int v, int path[]){// vからの深さ優先探索
■■■■int afwd, abk, w;
■■■■afwd = edgefirst[v];
■■■■while (afwd != 0 && rescap[afwd] == 0) afwd = edgenext[afwd];
■■■■while (t_found == false && afwd != 0) {// 増加パスはまだ発見されいない限り
■■■■■■■■w = head[afwd];
■■■■■■■■if (path[w] == unvisited) {// wが未訪問であったらwへ前進
■■■■■■■■■■■■abk = afwd+1; // abkはafwdの逆向きの辺
■■■■■■■■■■■■if (afwd % 2 ==0) abk = afwd-1;
■■■■■■■■■■■■path[w] = abk; // afwdの逆向きの辺abkをpath[w]に記憶する
■■■■■■■■■■■■if (w != t) dfs(w,path); // wからの深さ優先探索へ進む
■■■■■■■■■■■■else {// w == t なので増加パスPが見つかった
■■■■■■■■■■■■■■■■t_found=true; // dfs(v,path)の強制終了へ
■■■■■■■■■■■■}
■■■■■■■■}
■■■■■■■■if (t_found == false) { // dfs(v,path)が強制終了になっていないときのみ
■■■■■■■■■■■■ afwd = edgenext[afwd]; //次の辺に移る
■■■■■■■■■■■■ while (afwd != 0 && rescap[afwd] == 0) afwd = edgenext[afwd];
■■■■■■■■}
■■■■}
}

**デフォルトの名無しさん** · 2017/07/08(土) 10:04:34.97

基地外こえーな

**デフォルトの名無しさん** · 2017/07/08(土) 10:07:07.69

↓は、↑と等価なプログラムです。

すっきりとしていて分かりやすいですね。↓

void dfs(int v, int path[]){
■■■■int afwd, abk, w;
■■■■afwd = edgefirst[v];
■■■■for(afwd = edgefirst[v]; afwd != 0; afwd = edgenext[afwd]){
■■■■■■■■if(rescap[afwd] == 0) continue;
■■■■■■■■w = head[afwd];
■■■■■■■■if(path[w] == unvisited){
■■■■■■■■■■■■if(afwd % 2 == 0){
■■■■■■■■■■■■■■■■abk = afwd - 1;
■■■■■■■■■■■■}else{
■■■■■■■■■■■■■■■■abk = afwd + 1;
■■■■■■■■■■■■}■■■■■■■■
■■■■■■■■■■■■path[w] = abk;
■■■■■■■■■■■■if(w != t){
■■■■■■■■■■■■■■■■dfs(w, path);
■■■■■■■■■■■■}else{
■■■■■■■■■■■■■■■■t_found = true;
■■■■■■■■■■■■■■■■return;
■■■■■■■■■■■■}
■■■■■■■■}
■■■■}
}

**デフォルトの名無しさん** · 2017/07/08(土) 10:10:00.82

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）のプログラムは
すべて↑こんな感じなので、いちいち自分でまともな等価なプログラムに改善してから
読む必要に迫られます。

**デフォルトの名無しさん** · 2017/07/08(土) 10:29:14.58

海苔弁プログラムと呼ぶことにしよう

**デフォルトの名無しさん** · 2017/07/08(土) 10:35:19.17

アホのアスペ日記

**デフォルトの名無しさん** · 2017/07/08(土) 14:20:34.28

for-2ch-codes/FlowLibrary.h

↓こちらが浅野さんの Ford - Fulkerson のアルゴリズムのソースコードです：
for-2ch-codes/asano_fordfulkerson.c

↑なぜ、こんな分かりにくいコードを書けるのか不思議です。
アルゴリズムの研究者なのに、プログラミングをしたことがないのでしょうか？

↓こちらが浅野さんのコードを読みやすくした等価なコードです：
for-2ch-codes/my_fordfulkerson.c

**デフォルトの名無しさん** · 2017/07/08(土) 14:21:50.45

https://github.com/for-2ch/for-2ch-codes/blob/master/FlowLibrary.h

↓こちらが浅野さんのソースコードです：
https://github.com/for-2ch/for-2ch-codes/blob/master/asano_fordfulkerson.c

↑なぜ、こんな分かりにくいコードを書けるのか不思議です。
アルゴリズムの研究者なのに、プログラミングをしたことがないのでしょうか？

↓こちらが浅野さんのコードを読みやすくした等価なコードです：
https://github.com/for-2ch/for-2ch-codes/blob/master/my_fordfulkerson.c

**デフォルトの名無しさん** · 2017/07/08(土) 14:46:01.89

■■■■■■■■■■■■■
■■このスレ闇が深すぎ■■
■■■■■■■■■■■■■

**デフォルトの名無しさん** · 2017/07/08(土) 15:34:28.51

すみません、松坂くんて誰ですか

**デフォルトの名無しさん** · 2017/07/08(土) 16:30:54.37

◆QZaw55cn4c · 2017/07/08(土) 18:49:23.91

>>497
高等な趣味だと思うよ，よく頑張っているね

**デフォルトの名無しさん** · 2017/07/08(土) 19:37:28.26

馬鹿アスペ同士仲良く

**デフォルトの名無しさん** · 2017/07/09(日) 17:28:01.51

お前ら、ちゃんと次スレ立ててやれよ？
隔離スレさえあればこっちに被害は及ばないからな

**デフォルトの名無しさん** · 2017/07/09(日) 17:29:01.52

お前がやれよ