Daniel Marcus Graph Theory を読む。
￥
https://github.com/for-2ch/for-2ch/blob/master/Chapter_C.ipynb
https://github.com/for-2ch/for-2ch/blob/master/Chapter_D.ipynb
by Daniel A. Marcus
https://www.amazon.com/dp/0883857723
￥
あ、簡単でしたね。
https://anaconda.org/for_2ch/chapter-c/notebook
306 名前：１３２人目の素数さん[] 投稿日：2017/06/07(水) 12:44:01.61 ID:54f7ZpML
http://imgur.com/UVl9MdB.jpg
与えられた次数列をもつ2部グラフが存在するかどうかの問題です。
解答をお願いします。
307 名前：１３２人目の素数さん[] 投稿日：2017/06/07(水) 12:52:53.09 ID:54f7ZpML
>>306
これは試行錯誤するしかないっぽいですね。
308 名前：１３２人目の素数さん[] 投稿日：2017/06/07(水) 12:56:32.29 ID:54f7ZpML
C26
(a)
次数をすべて足すと = 42
42 / 2 = 21
次数列を構成している次数はすべて偶数だから2部グラフは存在しない。
311 名前：１３２人目の素数さん[] 投稿日：2017/06/07(水) 19:37:58.59 ID:54f7ZpML
>>310
ありがとうございます。
https://github.com/for-2ch/for-2ch/blob/master/Chapter_C.ipynb
314 名前：１３２人目の素数さん[] 投稿日：2017/06/07(水) 21:25:35.66 ID:54f7ZpML
http://imgur.com/6ecwXxa.jpg
↑の問題C28の意味が分かりません。
どういう解答を期待しているのでしょうか？
(4, 3, 3, 3, 3, 3, 3, 2, 2)
という次数列だけからでは、2部補グラフがどのような次数列を持つかが
分からないように思います。
321 名前：１３２人目の素数さん[] 投稿日：2017/06/07(水) 22:17:21.49 ID:54f7ZpML
>>314
2部補グラフを考えることにより、問題が簡単になるようには思えません。
グローバル変数の net というのは、関数の中で呼び出されている関数の中でも
使えるんですか？
760 名前：デフォルトの名無しさん[] 投稿日：2017/06/12(月) 15:09:49.85 ID:yuw+moiO
あ、できますね↓
glvar = "abc"
def myfunc1():
■■■■myfunc2()
def myfunc2():
■■■■print(glvar)
myfunc1()
761 名前：デフォルトの名無しさん[] 投稿日：2017/06/12(月) 15:11:05.87 ID:yuw+moiO
しかし、この斎藤っていう人、こんあひどいコードをよく恥ずかしげもなく公開できますね。
762 名前：デフォルトの名無しさん[] 投稿日：2017/06/12(月) 15:11:58.06 ID:yuw+moiO
なんでこの斎藤っていう人の本は高評価なんですか？
こんなひどいコード見たことがないです。正直言って。
763 名前：デフォルトの名無しさん[] 投稿日：2017/06/12(月) 15:12:31.37 ID:yuw+moiO
意図的に人を混乱に陥れようとしているかのようです。
764 名前：デフォルトの名無しさん[] 投稿日：2017/06/12(月) 15:22:22.17 ID:yuw+moiO
def f(W):
■■■■return cross_entropy_error(softmax(np.dot(x, W)), t)
↑こう書けば、x, t がグローバル変数ですが、理解可能だったと思います。
765 名前：デフォルトの名無しさん[] 投稿日：2017/06/12(月) 15:37:37.83 ID:yuw+moiO
もっと先でどうなっているのか知りませんけど、
コードの再利用を絶対しなければならないとかいう強迫観念があるかのようですね。
￥
↓このプログラムですが、ひどすぎないですか？
斎藤康毅のディープラーニングの本のコードです。
def softmax(x):
■■■■if x.ndim == 2:
■■■■■■■■x = x.T
■■■■■■■■x = x - np.max(x, axis=0)
■■■■■■■■y = np.exp(x) / np.sum(np.exp(x), axis=0)
■■■■■■■■return y.T
■■■■x = x - np.max(x) # オーバーフロー対策
■■■■return np.exp(x) / np.sum(np.exp(x))
def cross_entropy_error(y, t):
■■■■if y.ndim == 1:
■■■■■■■■t = t.reshape(1, t.size)
■■■■■■■■y = y.reshape(1, y.size)
■■■■■■■■
■■■■# 教師データがone-hot-vectorの場合、正解ラベルのインデックスに変換
■■■■if t.size == y.size:
■■■■■■■■t = t.argmax(axis=1)
■■■■■■■■■■■■
■■■■batch_size = y.shape[0]
■■■■return -np.sum(np.log(y[np.arange(batch_size), t])) / batch_size
347 名前：デフォルトの名無しさん[] 投稿日：2017/06/12(月) 18:39:18.66 ID:yuw+moiO
def numerical_gradient(f, x):
■■■■h = 1e-4 # 0.0001
■■■■grad = np.zeros_like(x)
■■■■
■■■■it = np.nditer(x, flags=['multi_index'], op_flags=['readwrite'])
■■■■while not it.finished:
■■■■■■■■idx = it.multi_index
■■■■■■■■tmp_val = x[idx]
■■■■■■■■x[idx] = float(tmp_val) + h
■■■■■■■■fxh1 = f(x) # f(x+h)
■■■■■■■■
■■■■■■■■x[idx] = tmp_val - h
■■■■■■■■fxh2 = f(x) # f(x-h)
■■■■■■■■grad[idx] = (fxh1 - fxh2) / (2*h)
■■■■■■■■
■■■■■■■■x[idx] = tmp_val # 値を元に戻す
■■■■■■■■it.iternext()
■■■■■■■■
■■■■return grad
あまりの初心者むけに評判がいいんだよ！
http://imgur.com/9QGwvmM.jpg
http://imgur.com/j3Dp32V.jpg
http://imgur.com/iJhKoqM.jpg
↑は浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）です。
重大な誤りを発見しました。
G が二部グラフであるための必要十分条件は、G を幅優先探索したときに同じ深さの補木辺がないことであると書かれていますが、
完全な誤りです。
具体的に言うと、「同じ深さの点を結ぶ補木辺がないときは、この色の割当てが実際に2彩色になっている。」と書かれていますが、
間違っています。
反例は3枚目の画像を参照してください。
394 名前：デフォルトの名無しさん[] 投稿日：2017/06/21(水) 11:00:57.46 ID:CsbvaOkp
訂正します：
http://imgur.com/9QGwvmM.jpg
http://imgur.com/j3Dp32V.jpg
http://imgur.com/iJhKoqM.jpg
↑は浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）です。
重大な誤りを発見しました。
G が二部グラフであるための必要十分条件は、G を幅優先探索したときに同じ深さの点を結ぶ補木辺がないことであると書かれていますが、完全な誤りです。
具体的に言うと、「同じ深さの点を結ぶ補木辺がないときは、この色の割当てが実際に2彩色になっている。」と書かれていますが、
間違っています。
反例は3枚目の画像を参照してください。
395 名前：デフォルトの名無しさん[] 投稿日：2017/06/21(水) 11:11:21.29 ID:CsbvaOkp
商品の説明
内容紹介
ネットワーク・人工知能の基礎となるグラフ・ネットワークを学ぶ
アマゾンに商品説明として、↑のように書かれています。
人工知能とグラフ・ネットワーク理論に何の関係があるのでしょうか？
この出版社は、「世界標準MIT教科書」などとタイトルに書いたり、売るためには
手段を選ばない出版社ですね。
￥
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）ですが、この
本には強連結成分分解のアルゴリズムは書いてあるのですが、その正しさについて
の説明がありません。
「アルゴリズムの正当性については演習問題とする。」などと書かれているだけです。
そして、解答がありません。
解答をつけないほど簡単な問題でしょうか？
エイホ、ホップクロフト、ウルマン著『データ構造とアルゴリズム』に分かりやすい説明がありました。
414 名前：デフォルトの名無しさん[] 投稿日：2017/06/26(月) 15:09:29.86 ID:wjem+ipT
あ、よくみたら解答がありました。
415 名前：デフォルトの名無しさん[] 投稿日：2017/06/26(月) 15:14:33.33 ID:wjem+ipT
強連結成分分解のアルゴリズムはグラフ理論的な観点からは興味深いですが、
応用についてはあまりないようですね。
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）の「はじめに」に
「強連結成分分解はシステムの故障診断や効率的解析への応用があると言われている。」
などと書かれいます。浅野さん自身は応用について具体的な詳細を知らないと宣言して
いるようなものですね。
417 名前：デフォルトの名無しさん[] 投稿日：2017/06/26(月) 15:32:39.93 ID:wjem+ipT
ところで、LEDAというライブラリはお勧めですか？
〜〜〜芳雄氏が言う『研究者としての基本的態度』とは一体何だろうか〜〜〜
佐藤幹夫：自分自身の素朴な疑問に真剣に耳を傾ける。⇒不滅の金字塔を打ち立てる。
糞父芳雄：人間関係を駆使し他人を操り根回しを行う。⇒ハリボテお教授として君臨。
隠蔽の財務省、嘘吐きの文科省、そして問答無用に屈服させる官邸。コレでも先進国？
（佐藤師がしてたのは本物の研究だ。だが）芳雄氏がしてたのはケケケ、ケンキュウ。
外見を繕って偉そう見せさえすれば何でもヨロシ。ほんで教授になりさえすれば研究の
中身なんて何でもヨロシ。そもそも論文なんてモンは、外国の権威ある雑誌に掲載され
さえすれば、その中身のギロンなんて何でもヨロシ。そやし適当に書いてしまえ〜〜〜
中身がダメだと知ってて、ソレでもSTAP論文を外国に投稿して受理される。発覚したら
適当に言い逃れる醜い態度。オツムのダメな大学院生に「虚偽の良品ラベル」を貼って
世間に出荷するハリボテ大学は詐欺行為そのもの。世間に媚びを売って客商売に徹し、
『売れさえすれば学生の脳の質なんて何でもヨロシ』と居直る大学。そしてブランド名
だけを見て仕入れる世間。●●は一流大学やさかい、きっと優秀なエリートやろｗｗｗ
中身を何も説明しないで、問答無用に上から押し付ける。ソレをイチャモンで騒いで、
そして邪魔して潰そうとする周囲の下々。大学教員も国会議事堂も、そして馬鹿板人の
遣ってる事も皆同じだ。日本人はバカ民族であり、今は外国にもちゃんとバレてるので
海外からも軽蔑されるだけであり、そのうちにどの国からも信用されなくなるだろう。
近視眼的で打算的な人生観を息子に押し付ける父親と、大脳に栄養が足りてない連中が
跋扈する永田町や霞が関に支配される国に住む不幸、一体どうしてくれるというのか。
■■■馬鹿板を続けたらオツムがスポンジ脳になるのでサッサと足を洗うべき。■■■
￥
おまえがいけ
おまえがちゃんとあやまってこり
これいじょうわたしをおこらせるな！
102 :
右や左の名無し様
2017/06/26(月) 16:51:43.50 ID:DV/Fl9ZZ
このハゲー ちゃうだろ！
おなじことをいわせるな
はげてるんですううううう
すみません ｽﾐﾏﾝｾﾝ ｽﾐﾏｾﾝ
￥
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。
G のトポロジカルラベリングについては説明があるのですが、トポロジカルソートの応用例が
全く書かれていません。
勉強するモチベーションが全くありません。
著者は一体何を考えているのでしょうか？
424 名前：デフォルトの名無しさん[] 投稿日：2017/06/27(火) 19:32:13.18 ID:NGLAHv1W
あ、その後の有向無閉路ネットワークの最長パスを求めるアルゴリズムで
トポロジカルラベリングが使われていました。
なかなか面白い応用ですね。
この本、説明にちょっと粗雑なところもありますが、見せ場があって楽しいですね。
425 名前：デフォルトの名無しさん[] 投稿日：2017/06/27(火) 19:34:40.25 ID:NGLAHv1W
有向無閉路ネットワークという制限が強すぎますね。
でもこの制限のおかげでちょっと面白いトポロジカルラベリングの応用例が見れたわけですね。
>>430
そのインド人の本は、アルゴリズムの正当性のまともな説明がありません。
計算量の評価についてもまともな説明がありｍせん。
セジウィックの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 であるような連結なグラフは木であるから、そうような部分グラフは木である。
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。
↓は、ある点から各点への最長パスを求めるプログラムのメイン関数です。
「出発点を入力してください」などと出力していますが、出発点は 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;
}
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。
ひどいバグを発見しました。
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とする
■■■■■■■■}
■■■■}
}
↑の 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]の初期設定
でなければなりません。
>>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回くらい
オンエアするんだよね。多くない？」と疑問を口にする。続けて、
精神的苦痛を受ける人も世間にいると伊集院は持論を展開し「ハゲてる人
はこたえてると思うよ、相当ね」「あと、ああいう圧に耐えながら仕事
している人は、怖ぇと思うんだけどな」と指摘したのだった。
あ、もう一つバグがありました↑
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 です。
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）
ホップクロフト - カープのアルゴリズムのところを読んでいます。
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();
}
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。
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 という値が使いたいだけです。
ひどいコードです。
100〜のスレッドの続きを読む