離散最適化基礎論

岡本 吉央

テーマ：ネットワークフロー

注意：内容は毎年変わります

ショートカット： 講義資料 | コメント | レポート課題 | 公式シラバス | スケジュール | 参考文献 | 関連リンク | 過去の講義

実施形態

学生の皆さんの受講形態としては，「教室で授業を受ける」形を推奨しますが，自宅や研究室等からオンラインでリアルタイム受講しても構いませんし，オンデマンド型の受講をしても構いません．ただ，オンデマンド型では，質問をする機会が限られることにご注意ください．

内部シラバス (学務情報システムから見ることができるシラバス) で，Google Classroomのコードを確認し，参加をしてください．

講義資料

• 1/23 (14) 最小費用流問題：費用スケーリング法
  • スライド
  • 講義動画
• 1/16 (13) 最小費用流問題：容量スケーリング法
  • スライド (1/21修正)
  • 講義動画 (前半修正版) 容量スケーリング法
  • 講義動画 (後半教室版) 主双対法
• 1/9 (12) 最小費用流問題：逐次最短路法
  • スライド (1/10改訂)
  • 講義動画
• 12/26 (11) 最小費用流問題：正カット消去法
  • スライド (12/29改訂)
  • 講義動画
• 12/19 (10) 最小費用流問題：負閉路消去法
  • スライド (12/19改訂)
  • 講義動画
• 12/12 (9) 最小費用流問題：線形計画問題として
  • スライド (12/13改訂)
  • 講義動画
• 11/28 (8) Push-Relabel法 (計算量評価)
  • スライド (11/28改訂)
  • 講義動画
• 11/21 (7) Push-Relabel法 (概要)
  • スライド (11/28改訂)
  • 講義動画
• 11/14 (6) 最大流問題：容量スケーリング法
  • スライド (11/14改訂)
  • 講義動画
• 11/7 (5) 最大流問題：Edmonds-Karpのアルゴリズム
  • スライド (11/8改訂)
  • 講義動画
• 10/31 (4) 最大流問題：線形計画問題として
  • スライド (11/8改訂)
  • 講義動画
• 10/24 (3) 線形計画法の復習
  • スライド (10/25改訂)
  • 講義動画
• 10/10 (2) 最大流問題：増加道法
  • スライド (10/11改訂)
  • 講義動画
  • 補足動画1 (流の増加：証明)
  • 補足動画2 (増加道法が停止しない例)
• 10/3 (1) 最大流と最小費用流：定義
  • スライド (10/4改訂)
  • 講義動画

• 1/23 (14) 最小費用流問題：費用スケーリング法
  • 期末レポートの締切，予定は2月9日(土)と書いてありましたが，2/9は金曜日だと思います．2/10(土)ですか？　卒論発表の日が2/9(金)なので，それよりも前にやらないといけなくて涙(なみだ)です😭
    --すみません，2月10日(土)のつもりでした．ご指摘ありがとうございます．
  • 今回の授業で最後だと聞いて，久しぶりに授業に参加したのですが，知らない単語も増えていて分からないことが多かったです．頑張って期末レポートまでに勉強したいです．
    --突然授業に出席しても分からないのは当然だと思います．
  • レポートの採点後，点数を返却していただけるみたいで助かります．2つのレポートに関して，離散数理工学のような先生からの講評やコメントは掲載される予定はありますか？
    --すみませんが，講評やコメントが掲載される予定はありません．
  • 半年間ありがとうございました。難易度的に咀嚼しきれない部分もありましたが、全体として楽しい授業でした。期末レポートも頑張ります。
    --はい，私がよく間違えるぐらいですから，皆さんにとっては難しかったと思います．
  • 半年間ありがとうございました．たくさんの質問や雑談に答えていただけるので毎週の楽しみでしたが，なくなると思うと寂しいですね．これ以降に質問が湧き上がらないことを祈りながら復習とレポート作成を頑張りたいと思います．
    --私も寂しいです．;-)
  • 初めて先生が担当される講義を受講して以来，先生のコメントを養分にしているものです．今年の離散最適化基礎論は特に豊作でとても楽しく読ませていただいたのですが，またしばらく供給がなくなってしまう…
    --楽しんでいただけたようで，それはよかったです :-) 供給については半年お待ちください．
  • 半年間お世話になりました！このコメントのコーナー，とても好きでした笑　講義もなくなり寂しくなりますが，先生もお体に気をつけてお過ごしください
    --お互いに．ご自愛ください．
  • 半年間ありがとうございました!! 受講形態、授業内容も含めてわかりやすく、受講しやすかったです。
    --こちらこそありがとうございます．受講形態については合う人も合わない人もいると思います．あまり万人受けするようなことはしていないので，その点はご了承ください．
  • 4ヶ月ほどですが、ありがとうございました。一つ見つけた視点に固執してしまうので、少し広い視野で別の視点を見つけられるようになりたいと思いました。
    --いろんな視点を持つということは大事だと思っています．そのために，皆さんはいろんな種類の勉強をしているのだと思ってください．
  • 1学期間、クッソお世話になりましたぁあああ！！！！
    --こちらこそありがとうございました．
  • 先生の好きな色って何ですか？いつも色味のある服を着ていると思ってます．そこに色の好みが現れているのかと思っていたのですが，赤・青・緑・オレンジそして今日黄色のものを着てきてて，気になりました．
    --好きな色があるわけではありません．色味がついているのは，汚れが目立たないからです (黒も白も汚れが目立つと思ってます)．ただ，服を買うときに色がまとまらないようにはしています．
  • 最近のマクドナルドの期間限定ソースで，1.感情に訴えかけてくる「文系」焦がしニンニク醬油ソース，2.緻密に配分が計算され尽くした「理系」カマンベール＆パルメザンチーズソースというものがあるそうです．私はチーズが嫌いなのですが(ピザは食べます．チーズの臭みが苦手です)，チー牛という印象がやはり持たれているのでしょうか？私は文系女子が新大久保あたりでキャーキャー韓国料理(チーズが適当にかけられて辛いもの)を食べているのを見て，この人たちこそチーズやんって思ったりします．悔しい気持ちです．先生はどちらのソースを食べてみたいですか？
    --見た目だけでその人を「文系女子」だと判断しているならば，人を見た目で判断していることになり，よくないと思います．それはともかく「緻密に配分が計算され尽くした」という部分に「理系」を思い浮かべているのではないでしょうか．また「感情に訴えかけてくる」という部分に「文系」という性質を思い浮かべているように思います．いずれにせよ，これも偏見だとは思います．そもそも文系・理系とか男性・女性とか，そういう属性で人を分けようとする魂胆が好きではありません．男性・女性は生物学的なものなので仕方ないですが，文系・理系という分け方は私の本心では廃止したい．こんなくだらない概念が日常生活の細部にまで入り込んでいるのは，ばからしいと思ってます．
    さて，私がどちらを食べてみたいかと言われれば (なんでこんなに長く返事を書いてるのでしょう…)，チーズの方です．私はスイスに住んでいたので，チーズにはこだわりがあります．KFCから「チーズにおぼれるフィレバーガー」が期間限定で出ていますが，これはおいしかったです．
  • お昼ご飯を何にするのかでいつも悩んでいます．最近電通大近くで美味しかったご飯屋さんはありますか？
    --「最近」と言われると困ります．;-) 最近は西食堂かハルモニアでしか昼食をとってません．
  • 今敏さん監督の「千年女優」を見にいきました（リバイバル上映をしています）．回想する形で物語が始まり，記憶と現実が錯綜し展開していく様子が斬新で，考えさせられもしますし面白く，それらの表現の仕方に感動しました．
    --今敏監督作品だと，『PERFECT BLUE』と『パプリカ』を見ました．どちらもDVDですが．『千年女優』はまだ見ていないので，機会があれば見てみたいと思ってます．
  • これまで興味深い講義を行っていただきありがとうございました。この講義によって、グラフ理論（特に最小費用流問題）の知識の幅を広げることができたと実感しております。この講義で得たものがこれからの研究に活かせればと思います。
    --こちらこそありがとうございました．ぜひ研究に活かしてみてください．
  • 半年間ありがとうございました．レポート課題も頑張ります．気が早いですが，来年度もこの講義を担当されるのであれば，扱いたいと考えている内容は既に決まっているのでしょうか．
    --来年度もこの講義を担当することになると思いますが，テーマは検討中です．
  • 数学原理からアルゴリズムが導出されるという視点で数学を見たことがなかったです。新しく数学を学ぶときに、何らかのアルゴリズムが導出されるかなと考えながら具体例を考えると楽しそうです。でも自分でアルゴリズムが導出できる「奇跡」が想像できません。
    --そのような「奇跡」はなかなか起きないかもしれません．ただ，それが起きるときには割と綺麗に起きると思います．また，何か解かなくてはならない問題が出てきたときに，その背後にある数学原理に着目するということを続けていれば，起きる可能性は高くなると思います．
  • 約半年にわたる講義お疲れ様です。自分は元々ネットワークフローアルゴリズムを知らない身で参加しましたが、結果としては多くの学びが得られました。特に、線形計画問題から最大流・最小費用流問題を効率よく解くアルゴリズムが徐々に姿を現す過程は理論的に美しいと感じました。
    --最大流や最小費用流というトピックは，離散最適化の中でも理論的に美しいものの典型例です．一方で，離散最適化の中にはこれほど美しく理論展開ができていないものもあります．そのようなもののなかに美しい部分を見つけていくのが，研究の最先端になっているともいえます．
  • 半期間ありがとうございました。容量に適用したのと同じ工夫を費用にも適用することで計算量を改善できたことは面白いと思いました。
    --そうですね．スケーリング法はかなり汎用的です．皆さんもぜひ適用できそうなときには適用してみてください．
  • スケーリングによって最適な選択肢だけが生き残ることで計算量が減るというのはこれまでの授業でなんとなくわかったのですが、簡約費用がどんなに小さくても-1にできるという具体的で強い性質を見るとやっぱり不思議に感じてしまいました。
    --今回紹介した費用スケーリング法は私も不思議に感じます．すごく良い性質が都合よく成り立っているように感じます．
  • p.16のお気持ちのお陰で「なぜ0で止めるのか」がわかった気がします．一つ説明を追いきれてなかった部分があって，ある条件を満たす弧はWを広げるために使われるので存在しない...のような話をしていたと思うのですが，それはどういった条件だったかをもう一度説明していただきたいです．Wを広げられるかは補助ネットワークの弧の容量が関係していて簡約費用についてはあまり関係ないと思っていますが正しいでしょうか？
    --「Wから出ていく弧で簡約費用が0以下のものは存在しない」と言ったのだと思います．そういう弧があると仮定すると，Wの構成法から，その弧の終点もWの要素でないといけないので，その弧がWから出ていくことに矛盾するからです．Wを広げるために用いる弧は簡約費用が0以下の弧 (6ページから12ページでいうと，「右上」の図の弧) だけになります．
    また，ポテンシャルを更新することで，弧が消えることがあるようなことを授業中に口走りましたが，それはありえません．弧が消えるのは流が変更されたときのみです．
  • p.19の「高々C回」のところが難しかったです。Cかける頂点の次数以下になるのはすぐにわかるのですが、高々C回になるのがわかりませんでした。・・・と思ったのですが、ソースから辿り着ける頂点全てのポテンシャルを上げてるからC回以上起こり得ないことがわかりました。
    --はい，そのとおりです．ソースを始点とする簡約費用負の弧において，ポテンシャル更新後は，その簡約費用がすべて増加します．つまり，高々C回ポテンシャルを更新すると，そのような弧の簡約費用がすべて0以上になります．
  • 主双対法において，ソースからソースに流れる流を探すときに，ソースを始点とする破線弧を使わないのは，破線弧は消す必要がないため，ソースを始点とする破線弧を消そうとする作業が無駄になる（どの実線弧も消えずに，新たに破線弧が増える）可能性があるからという認識で正しいでしょうか（一方で，ソースを始点とする実線弧を使っても，どの実線弧も消えずに，新たに破線弧が増える場合は，講義内の例でも表れましたが，実線弧を消すことを目的とするならば，実線弧が増えないことが重要（停止性をきちんと考えようと思うと，必ず全部消えるところまで考慮する必要はありますがここでは省略）であるため，これは問題ないことは理解できていると思います）．それとも，ソースを始点とする破線弧を使ってしまうと，正しく動作しない例が存在するのでしょうか（破線弧を消すことも目的としてしまうと，停止しない例が存在するかもしれない？）．
    --前者です．後者ももしかしたら正しいのかもしれませんが，ちゃんと検討していません．すみません．
    「どの実線弧も消えずに，新たに破線弧が増える」ことがあるのは確かですが，これであっても，ソースを始点とする実線弧の簡約費用が真に増加していることが重要です．
  • 容量∞といっても需要供給のおかげで制約されるからいくらでも流れるということがないという感じなんですかね．その上で成立するように変換しているのかな？と思いました．変換の仕方を説明していただいた感じがして，無限大の直感があまり入ってこなかったかもしれないです
    --需要供給のおかげでいくらでも流れるということがないという理解は正しいです．無限大は「とても大きな整数」だと思っていただければよく，その方が理解しやすいかもしれません．
  • 前回間違えに気づかずに、容量スケーリング法の説明が分かった気になってしまっていましたことを痛感しました。（自分で考えた修正方法と授業のノートは全然違うので自分の考え方があってるかも検証してみます。流せるだけ流す時に流れる流量に注目できないかと考えました。）スケーリングを考えて高速化するときは何が普遍で何がどれくらいの速さで満たされていくかをしっかり考える必要を感じました。今回の授業のスケーリング法では正の簡約費用はどんな値になるかわからないけど、負の簡約費用は常に-1か0みとみなせ、さらに、ポテンシャルと費用の差（簡約費用）が2進法の上から埋まっていくことが、要点になるように感じました。
    --分かった気にさせる才能が私にはあるようです ;-)．間違っていたのはすみませんでした．
    容量スケーリング法では，スケーリングの途中で，需要と供給が釣り合わないことに気づいておらず，その部分をどう克服すればよいか私はかなり悩みました．そして，EdmondsとKarpの最初の論文を見たらちゃんと書いてあって「なるほど！」と思いました．
• 1/16 (13) 最小費用流問題：容量スケーリング法
  • 24/36ページにある「$A_{f_i} = A_{2f_i}$」は必ずしも正しくありません (正しくない場合があります)．容量スケーリング法では他にも注意すべき点があるので，補足・修正を後ほど行います．端的にいえば，私の理解が浅いため，間違っていました．(主双対法は大丈夫であるはずです．) スライドは一旦非公開にして，動画も取り直します．よろしくお願いします．
  • 残りの授業が1回と聞いて、少し寂しく感じます。
    --私も寂しく感じます ;-)
  • 次回が最後の講義と聞きあっという間だなと率直に感じた。レポートもあると思うので今のうちから復習をしておこうと思います。
    --歳をとるごとに時間の経過を早く感じるのだそうです．ジャネの法則と呼ぶそうです．
  • 先日チバニアンを観に行きました． まだ仮説らしいのですが，地球の磁気が逆転した仕組みが， 中学生レベルの知識で理解可能で面白かったです．
    --私は大学生のときに，地学巡検にいったことがあります．秦野の辺りで地層を見たりしました．また，2000年に噴火があった三宅島には，噴火の前 (1997年) に夜行フェリーでいって，雄山で噴石を拾ったり，南側の森林で植生調査をしたりしました．楽しく懐かしい思い出です．いろんな経験を若いうちにしておいてよかったと思ってます．
  • レポート2の足音が聞こえてきました。恐怖です。ちなみにレポート2の締切はいつ頃にする予定ですか。
    --締切の予定は2月9日(土)です．
  • 前半の適切なレポート問題の作成もたいへんそうでしたが、後半の授業の方がより難易度が上がってレポート問題の作成がたいへんそうと思いました。
    --しっかりと復習をしておいてください．
  • 主許容性や双対許容性といった線形計画法の言葉がネットワークフローにおけるbやポテンシャルなどの何に対応するのかを覚えておらず，p.29を見たときに何に対応するのか見直さないとな...と思いました．レポートももうすぐですし復習が必要そうです...
    --覚えることは重要ではなく，「忘れたときに復習すれば思い出せる」という程度の理解でよいと思います．29ページのところは，説明を端折ってしまったので，私がいけないのですが，主許容性はfがb-流であること，双対許容性はポテンシャルを考えていること，に対応していると思ってください．
  • 講義内容とは関係ない質問ですが、1回分の授業準備に平均してどれくらいの時間を要するのですか？私自身、研究室の発表1回で多くの時間を要しているため、毎講義様々なトピックを扱うのは大変だなと感じました。
    --7時間ぐらいは使っていると思います．これは教科書や論文を読んだり，手元で計算したりする時間を含んでいます．
  • 毎年・毎週かなりの量のスライドを作ってると思いますが、自分はここまでたくさん、かつ分かりやすいスライドを作る自信がありません。なにかコツや秘訣があれば教えてください。
    --分かりやすいかはともかく，図を多く使うことと例を使って説明することは心がけています．アルゴリズムはプログラムとして書けば理解できる，というものでもないと思っています．数学的な概念も定義が書いてあれば理解できる，というものではないと思っています．アルゴリズムや定義を理解するために，図や例をうまく使うことが大事だと思っています．みなさんも，いろいろなものを勉強するときに，「どのような図を使えば説明できるだろうか」とか「どのような例を使って説明すると分かりやすいだろうか」ということを考えるとよいと思います．
  • p.5 $b^0 = 0$ の $b$ は需要と供給の和を表しているということで正しいですか？その $b$ を0からもとのネットワークの需要・供給と同じようになるまで繰り返すという認識で大丈夫でしょうか（先週はわかっていた気がするのですが，今週見たら不安になっってしまいました...）
    --このページの書き方は直感に訴えているので，あまり厳密に考えるところではないつもりでした．分かりにくくてすみません．厳密に考えようと思う場合，そこの「$b$」は関数 $b\colon V\to\mathbb{R}$を表すと考えてください．「$b^0 = 0$」と書いているのは「関数$b^0$が$0$である」ことの意味で，$0$ で零関数 (何を引数にとっても$0$を返す関数) を表しているつもりです．水色の矢印で「単調増加」しているといっているのは，$b^i$のことではなくて，$|b^i(v)|$の和について述べていると思ってください．
  • スライド26ページの、O(n)+O(Kn)からO(n log max{U, B})に変形する過程はどのようなものでしょうか？
    -- n + Kn = (K+1)n なので，O(n) + O(Kn) = O(Kn) になります．Kの定義は K = max{1 + log U, 1 + log B} (厳密には切り捨て記号がつきます) なので，K = O(max{log U, log B}) = O(log max{U, B}) になります．そのため，O(Kn) = O(n log max{U, B}) になります．
  • 容量スケーリング法では途中で逐次最短路法を使うのに，計算量が逐次最短路法より少なくなるんですね．
    --そうですね．前回のコメントにもあったのですが，逐次最短路法においては，最短路が複数ある場合に，どの最短路を選ぶかの任意性があり，そこで流せる量が大きな最短路 (つまり弧の容量の最小値が大きい最短路) を選ぶと反復回数が少なくなります．容量スケーリング法は大きな容量の弧を優先して使うようになってるので，自動的に流せる量が大きな最短路を選べるようになっており，結果として，反復回数が小さくなります．
  • 容量スケーリング法はやっぱり普通の工夫に見えてしまいました。でも直感的に正しそうな工夫を数学的に確かめることの重要性も感じました。一般論ですが、明らかに見えることは、本当に自分が「あきらかと思えるくらい」理解しているか、自分が「あきらかと思えるくらい」理解していることは説明が必要ないのかあるのか、他の人が「あきらかと思えるくらい」詳しい説明が必要か、を吟味するこは大切ですね。
    --普通の工夫に見えるのならば，それはよいことだと思います．スケーリングの考え方に慣れてきたのだと思います．おそらく，もう少し授業ができて，スケーリングについてもう少し細かい話をする時間があるならば，スケーリングがうまくいかない問題を紹介すべきなのかもしれません．そうすると，スケーリングに関する直感がもっと養われることになると思います．
    一般論の方ですが，「明らかさ」は経験や技量にも依存する気がします．そのため，私が説明をするときには，相手 (聴衆) に合わせた説明の仕方を心がけているつもりです．授業においてはカリキュラムを大事にしていて，カリキュラム上，学生の皆さんが知っている (はずの) ことと馴染みのないことは何であるのか理解しようとはしています．
  • 最大流問題で習った容量スケーリング法と似ていたので、証明やアルゴリズムの流れがわかりやすかったです。またこれだけ最小費用問題のアルゴリズムを習ったので、主許容性、双対性、相補性の3つの条件を意識できると整理できて良いと思いました。
    --相補性定理は数理最適化の勉強を始める段階ではあまり強調されることがないかもしれません．しかし，アルゴリズムを設計するという状況においては，かなり強力に使える道具となります．最適化アルゴリズムを設計する機会があったら，相補性定理のことをぜひ思い出してください．
  • アルゴリズムってとっつきにくそう（個人の感想です）な気がしたのですが、触れるたびに愛おしくなってきました。特殊な例の簡単な計算でもいいからオリジナルの「アルゴリズム」を作りたくなりました。
    --勉強している甲斐がありますね．ぜひオリジナルのアルゴリズムを作ってください．:-)
  • 主双対法では簡約費用が負の辺を潰して0以上になるようにする方法だと認識しています．0になった辺は破線として残すのは0が特別な意味をもっているからだったりしますか？(正の場合は点線で残ったりしないのが気になりました)
    --その認識で正しいと思います．正のものが破線になって残ることはあります．スライドの35/39ページでは，そのような状況がでてきています．
  • 主双対法の仕組みはわかった気がするのですが、アルゴリズムが止まる仕組みがわかりにくいと予習をしてる段階では思いました。でも授業を聞いていたら止まる仕組みもわかった気がします。（気がするだけなので復習して理解を深めます。）破線を使う、使わないの理由がすぐにはわかりませんでした。
    --着目している頂点を始点とする破線を使わないことにしているのは，2つ理由があります．1つ目．流を見つけるときにそれを使わないのは，その弧を消すことを目的としていないからです．流が実線の弧を使うと，そこに沿って流すことで実線の弧が消える可能性があるのでそうしています．2つ目．ポテンシャルを更新するときにそれを使わないのは，使ってしまうと，ポテンシャルの増加後に，破線の弧が実線の弧になってしまう (簡約費用が0から負になってしまう) からです．この部分は説明があまりよろしくなかったのですが，次回により細かく説明することにもならない予定でいます．すみません．
  • 補助ネットワークの弧に対する簡約費用を「費用から，始点のポテンシャルを引き，終点のポテンシャルを足したもの」としてずっと説明されていたのに対して，「なんで，『始点と終点のポテンシャルの差（ただし，始点から終点を引いて求める）を費用から引いたもの』と説明しないのだろう」と思っていました（個人的には後者の説明の方がシンプルだと思うので）．ただ，主双対法が，その方針をどのように達成するのかを理解するうえでは「費用から，始点のポテンシャルを引き，終点のポテンシャルを足したもの」と説明された方が，分かりやすいと感じたので，前者の説明にもそういうよさがあったのか思いました．物事を理解しやすくするには，同じものであっても，時と場合に応じて適切に解釈を変えることは大事ですね（というか，この講義の内容（線形計画法の視点からアルゴリズムを理解する）がそもそも，それを実践する場になってますね）．
    --「始点と終点のポテンシャルの差を費用から引いたもの」と簡約費用を説明してもよいのですが，式として書いたときに括弧が余分についたりするため，そうしていませんでした．そちらのほうがシンプルだと思うという指摘には一理あると思います．
• 1/9 (12) 最小費用流問題：逐次最短路法
  • 明けましておめでとうございます。
    --明けましておめでとうございます．
  • あけましておめでとうございます．今年もよろしくお願いします．
    --今年もよろしくお願いします．
  • あけましておめでとうございます。今年もよろしくお願いします。
    --今年もよろしくお願いします．
  • あけましておめでとうございます。今年もよろしくお願いします。
    --今年もよろしくお願いします．
  • あけましておめでとうございます！あと1ヶ月と短いですが今年もよろしくお願いします！
    --今年もよろしくお願いします．
  • 残り３回ですが何卒よろしくお願い致します。
    --何卒よろしくお願いします．
  • あけましておめでとうございます。私は大掃除をして部屋の模様替えを行いましたが、先生は年末・年明けに何かされましたか？
    --前回と同じになりますが，私の過ごし方をいうと引かれるのでいわないことにします．
  • 歳をとるごとに年々、年末年始への楽しみが薄らいでいるような気がします。先生は年末年始どう過ごされましたか。
    --前回と同じになりますが，私の過ごし方をいうと引かれるのでいわないことにします．
  • 今冬は静電気でしょっちゅうバチッとなって痛い思いをよくしています…．先生は何か静電気対策を実践されていたりしますか．
    --指先で触る前に，壁などを触るようにしています．
  • あけましておめでとうございます。逐次最短路法は簡約費用を使うという思考に至ればあとは自然な流れのように感じました。話は変わりますが、前回のコメントで嚆矢という言葉を使用していたと思います。聞き馴染みのない言葉だったので調べてなるほどとなりました。常識的な単語と言われるかもしれませんが、先生はこのような言葉をどこで仕入れているのでしょう。少し気になりました。
    --「嚆矢」は『紅蓮の弓矢』に出てきます．まあ，そこで仕入れたわけではないのですが．
    一般論として，多様な言語体験をすると良いように思います．私も含めて，多くの日本人が日本語を使いこなせているわけではないと思っています．皆さんが日本語でコミュニケーションをとれている気になっているとき，それはおそらく気になっているだけです．自分の発したことばが自分の意図どおりに伝わる保証はまったくありませんし，伝わっていると確かめる手だてもありません．コミュニケーションをより確かなものに変えていく技法の一つが，多様な言語体験から獲得できると思います．今後，自動翻訳技術が発達してくればくるほど，母語 (または第一言語) の活用能力が重要になってくるでしょう．
  • $2$つの集合$A,B$の差を表す記号として$A \setminus B$ではなく$A - B$を使っている気持ちを教えていただきたいです．
    --どちらでも構いませんし，私も両方使います．ただ，授業では「$-$」を使うようにしています．代数などでは「$N \backslash G$」のような記法を使うことがあり，それと「$A \setminus B$」の見分けがつきにくいため，「$-$」を好んで使うようにしています (前者はバックスラッシュで，これは集合の差の記号とは違うものです)．
  • 年末年始にも最小費用問題の夢を見ました。やっぱりポテンシャルが引っかかってしまいます。自分なりにも解釈をしました。（かなりつたなく長い説明ですがここに書くことで私自身の理解を深めたいと思います。）まず、負の費用をもつネットワークも許します。コストと容量が与えられたネットワークの最小費用の下界とポテンシャルの関係を次のように考えました。新しい頂点をかんがえます。これは流量制約を超えるまたは足りない箇所を補うような頂点です。この頂点をQとしておきます。ポテンシャルを使って、もとのコストと容量が与えられたネットワークから新しいネットワークを作ります。これは全ての点から新しい点Qを結ぶ辺をどちらの方向にも考えます。その辺の容量は十分大きいとして、また、コストはQに向かう辺のコストは「マイナスその頂点のポテンシャル」として、Qから頂点に向かう辺のコストは「プラスその頂点のポテンシャル」とします。つまり、ポテンシャルの差はQを通ってたどり着いたコストになります。この新しいネットワークのb流は追加する前の辺で流れる量を決めれば決まります。超えた分、足りない分は、全部Qを通り調整されます。（そう考えるとQは足りない分を補充する、余った分を放出する大きい水槽のように見えます。）このQとポテンシャルにより与えられたネットワークの最小費用が双対問題の目的関数の値になります。当然新しい道を使った方がより安くなる、別の言い方をすると主問題の最適解がポテンシャルとQにより与えられたネットワークでの最小費用問題の許容解になるので弱双対定理が成り立つことがイメージできます。相補正定理をこのQを使ったネットワークでの最小費用流問題を通して考えると、Qを考えた新しいネットワークの最小費用流の最適解がQを全く通らないとき主問題の最適解になっていることがわかります。このQとポテンシャルを使ったネットワークを考えて、改めて授業の内容を確認しました。まず、負閉路除去によるアルゴリズムについて考えました。補助ネットワークについて、これはポテンシャルとQによって作られたネットワークと重ねるとQとつながる辺を使って安くできるかを判定するネットワークともみなせます。とくに負閉路があるときはどんなポテンシャルでもQを使ったネットーワークの最小費用の方が安くなってしまいます、言い換えると双対問題の目的関数の値と一致することはできないので最適値は取り得ません。負閉路がないときは、授業で扱った「負の距離を許す三角不等式」からQを通らないポテンシャルを構成することができます。これにより負閉路がないb流は相補正定理を満たす解となり、最適解、最適値となります。次に、正カット消去法についても考えます。これは、Qを通る流量が減っていくように（順番に）ポテンシャルを調整して最終的にQを通らない最小費用流が存在したときそれが最適解になるというアルゴリズムと解釈できました。今回の授業の逐次最短法もQを加えてイメージしやすいかを考えたいです。sとtを付け加えるとうまくいく？Qからst以外の頂点にながれないようにしながらsからQへの流量とQからtへの流量を減らしていくポテンシャルの調整をし続ける。正カット消去法とは違った視点でのポテンシャルの調整の方法だと考えられる気がしました。この考え方だと自然な考え方だと私は思いました。
    --夢を見てしまうほど うなされているのではないかと思って，心配になってしまいました．;-)
    素晴らしい解釈ですね．ありがとうございます．これはラグランジュ緩和と呼ばれるものと関係があるように感じました．ネットワークフローをラグランジュ緩和を通して考えるという発想がなかったので，面白い視点のような気がしてきました．
  • 逐次最短法は、s,tを加えたb流問題(sとtだけbの値が0じゃない問題に言い換える）を考え、さらに、sとtを結ぶ費用効率が十分大きい辺を加えた新しい最小費用流問題の閉路消去法の特別な場合（初期許容解をsからtへの直通のb流）のように見えたのですがあっていますか？・・・と思ったのですが、距離の取り方が大きく変わっていて違うと感じました。
    --負閉路消去法は「主許容性と相補性を保持して，双対許容性の成立を目指す」のに対して，逐次最短路法は「双対許容性と相補性を保持して，主許容性の成立を目指す」ので，その違いは大きいように思います．ただ，どちらも補助ネットワークを使っていますので，類似点もたくさんあるように思います．
  • 最大流問題の時もあったのですが、グラフを使って記述される最適化問題では「最短」を考えるとうまくいくことは定石ですか？それとも今回の授業の場合だけうまくいく方法ですか？
    --グラフに限らず，「最短」を考えることは案外多いです．今回の話でもあったように，最短性から距離の性質 (例えば，三角不等式) を使えるようになって，導ける性質が多くなります．
  • 逐次最短路法において実行例(スライド15ページ)のように最短s-t路が複数ある状況では，どの路を選ぶかで(容量などの違いにより)反復回数が変わることはあるのでしょうか。
    --変わることはあります．道の長さは費用 (簡約費用) だけで決まりますが，道に沿って流せる量は容量だけで決まるので，最短路が複数ある場合に，容量が大きな最短路を選べば，反復回数が小さくなることになります．これがまさに容量スケーリング法で行うことであり，次回のトピックになります．
  • スライドp.17について質問です。Step.6で最短s-t路に沿ってfを更新する際、最短s-t路上の頂点をあらかじめ記憶しておく必要があると思いました。特にプログラムでの実装を念頭に置くならば、Step.5でdijkstra法等を行う際に、通った頂点を配列に記録していくのが典型的な方法なのでしょうか？
    --そのとおりです．Dijkstra法は d(v) = min{d(u)+l(uv) | uvが弧} という形の更新を続けるのですが，この右辺の最小値を与えるuvを (配列等を用いて) 一つ覚えておくことにするのが普通です．そうすると，Dijkstra法が停止したときには，sを根とする木が得られることになります．このような木を最短路木 (shortest-path tree) と呼ぶことがあります．fを更新する際は最短路木をtから逆にsまでたどっていけばよいことになります．
  • 前回、前々回がカットや閉路に着目したのに対して、今回は経路に着目したのが最序盤の増加道法に帰ってきた感じがします。
    --そうですね．最大流問題の増加道法の発想に似ていると思います．最短路を使うことで，増加させている途中の状況でも，そのときの最小費用流が得られていることがポイントですね．
  • 少し文字数は増えますが「$p^i$が簡約費用最適性条件の条件を満たす」という文言は「$p^i$が簡約費用最適性条件に表れる不等式を満たす」と書くのはどうでしょう．
    --ありがとうございます．「簡約費用最適性条件の不等式を満たす」にしてみました．
  • 自然に感じるかというのは，論理的な飛躍が無いまたはそれを感じないということなんでしょうか？
    --世の中には誰にとっても自然であるというものがあるように感じます．例えば，「水は高いところから低いところに流れる」といったようなものです．これはまさに自然であって，おそらく「巨視的な物理現象」は誰にとっても自然であって，それは我々が日々慣れ親しんでいるからこそ得られる感覚なのだと思います．一方，コンピュータやアルゴリズムに関わる現象が自然と感じられるかどうかというのは，それに慣れ親しんでいる経験に依存するように思います．
    この講義では，皆さんに「数学的な原理からアルゴリズムが得られる」という感覚に慣れ親しんでいただきたいと思っています．これはネットワークフロー (最大流問題，最小費用流問題) やグラフの問題に限らず，さまざまな問題に対して適用される原理なので，他の場面でもその視点と感覚を持って適用できれば，この講義の目標はかなり達成できていると思います．
  • 逐次最短路法はパっと思いつく気がしないですね…．ゴールが満たしている条件（の一部）を不変条件としてアルゴリズムを作るという方針は一理あると思うので，そういう意味では自然なアルゴリズムであるようにも思えます．ただ，それがどのような操作に対する不変条件であるかということは，すぐにわかることではないはずなので，本当にすごいアルゴリズムだと思います．
    --逐次最短路法の説明 (解釈) にはいろいろなものがあって，実をいうと，最短路を見つけようとするときに，簡約費用を考えずに，補助ネットワークの費用をそのまま用いてもよいことが知られています (というか，そちらがもともとの逐次最短路法でした)．授業では簡約費用を用いる形のバージョンで説明しています．その方が簡約費用最適性条件がどのように使われているのか分かりやすいと思ったからです．一方で，補助ネットワークの費用をそのまま用いるバージョンでは，負閉路最適性条件に基づいて正当性の証明を行うのが普通であると思います．
  • 不変条件が大事だという話を，ついこの間数学セミナー（雑誌）で見かけて「簡約費用が非負であることがずっと変わってないなぁ」って思いながら例を見ていたら，まさに不変条件という言葉が出てきて「やっぱり大事なのか」って思いました．
    --はい，『数学セミナー』に書いたとおりです．(ご存じない方は，2023年4月号から，2024年3月号 (予定) まで，私が『アルゴリズムを勉強する前に読む12章』という連載をしていますので，そちらをご覧ください．図書館で購読しています．)
  • 逐次最短路法の考え方については，例を用いた説明でかなり理解しました．別件とはなりますが，提出レポートに対するコメントありがとうございました．自身が解ききれなかった問題の証明について模範解答もしくは解説があれば復習に役立てたいと思っています．
    --レポートの採点はいま行っている途中で，一部の人には採点途中の様子が見えてしまっていると思います．ただ，コメントはフィードバックを目的にしたものではないので，その点はご了承ください．また，模範解答や解説のようなものは用意しておらず，するつもりもありませんので，気になる点は直接お尋ねください．
• 12/26 (11) 最小費用流問題：正カット消去法
  • いよいよ年末ですね。良いお年をお過ごしください。
    --こちらこそ．
  • よいお年をお迎えください．
    --こちらこそ．
  • 良いお年を！
    --こちらこそ！
  • 先生は年末年始はどのように過ごされますか？自分は友達と高尾山で初日の出を見る予定です。
    --私の過ごし方をいうと引かれるのでいわないことにします．
    高尾山で初日の出はいいですね．高畑不動尊や深大寺も沿線にありますので，初詣にどうぞ．
  • 年末でまとまった時間が取れるのでしっかり復習しようと思います。良いお年を。
    --はい，ぜひ復習をお願いします．
  • 来年は我が家から流出する費用を最小にしていきたいです。一方で経済は豊かになってほしいので皆さんはたくさん出費してください。
    --素晴らしい心がけですね ;-)
  • 3か月でしたがこの授業を通じ、多くのことを学べたと思います。翌年も何卒宜しくお願い申し上げます。
    --こちらこそ，翌年もよろしくお願い申し上げます．
  • 結局，プレミア公開を利用されたのですね．
    --そうですね．一度試してみたかったので，そうしました．
  • 5~10分間隔で広告が挟まったりするのかなと思ったのですが、意外と大丈夫でした。
    --広告について，私はコントロールできないのですが，プレミア公開だと広告が途中で挟まらないのかもしれません．
  • 授業中に理解することが難しくなってきたので、冬休みは最小費用流問題の復習に充てたい気持ちがあります。
    --はい，ぜひ復習をしてください．
  • 最適ポテンシャルについて理解できました．非常にわかりやすかったです．
    --それはよかったです．:-)
  • スライドp.18の「よりみち、近道」の考え方がポテンシャルで費用の下界を与える幾何的イメージを考えられるように思いました。「寄り道、近道」を通した最小の費用が双対問題の目的関数の値になるように思いました。正カット消去法は「寄り道、近道」を使わなくなるまで、ポテンシャルを調整するように見えました。
    --おそらく「寄り道，近道を通した費用」が簡約費用に対応しているのだと思います．
  • 正カット消去法のポテンシャル増加量を1より大きい数にすると停止性に響くのでしょうか。
    --授業で使った例がよくなかったのかもしれませんが，ポテンシャルの増加量は1より大きくても構いませんし，1より小さくないといけない場合もあります．ポテンシャルの増加量はスライド40ページにあるように決めます．
  • 正カット消去法でカット内のポテンシャルを「すべて同じ数だけ増やす」操作をしているのは，なにかの条件を保つために必要だからそうしているという感じなのでしょうか？
    --そうですね．正カットSに両端点を持つ弧やSにどちらの端点も持たない弧の簡約費用 (c_uv-p_u+p_vのこと) を変えないようにするためにそうしていると思ってください．
  • 正カット最適性条件のシグマの下の$c_{uv}-p_u+p_v <0$の不等号のイコールが項によってついていたりついていなかったりするのが不思議だったのですが，複雑でしたが後の式変形できれいに示されていてすごいなと思いました．
    --ここはとても巧妙に「正カット」という概念を定義していることに由来します．正カットの定義だけを見ると，人工的で不自然なものに見えますが，証明を見ると自然に思えてくるのが不思議なところですね．
  • 「カットの容量はカットに入ってくるものとカットから出ていくものに依存する」ので，p29の(3)と(2)が残りましたと言われると当たり前のような気がしますが，感覚が数式によって示された感じがして気持ちよかったです
    --このようなシグマの取り扱いは慎重に行わないと間違えるので，注意が必要ですね．
  • p.25 の下2つの $b_v$ に関するものはそれぞれs -> v と v -> t の辺を表していますか？ (だとすると，上の $v$ の記号の位置に黒丸が揃ってるとよりわかりやすい気がします)
    --その辺を表していることは正しいです (20ページで同じ図を出していて，それを改めて25ページにも掲載しているという流れになっていますが，分かりにくかったかもしれません)．黒丸の位置は悩んだのですが，上のvとは別のものなので，あえて別の位置に置いています．
  • 講義動画内で仰られていたことの繰り返しのような気がしますが，スライド番号43/46のスライドにおいて，$$\sum_{\substack{uv \in \delta^+(S), \\ c_{uv} - (p_u + \delta) + p_v \leq 0}} u_{uv} \delta = \sum_{\substack{uv \in \delta^+(S), \\ c_{uv} - p_u + p_v \leq 0}} u_{uv} \delta$$ が成り立つのは，$\{uv \in \delta^+(S) \mid c_{uv} - (p_u + \delta) + p_v \leq 0 \}$と$\{uv \in \delta^+(S) \mid c_{uv} - p_u + p_v \leq 0 \}$が集合として等しくなる程度に，$\delta$を十分小さくとったからという理解で正しいでしょうか．もし，この理解が正しいとした場合，そのような$\delta$は任意の正カットに対して存在するのでしょうか．
    --はい，その理解で正しいです．そして，そのような$\delta$が必ず存在することは次のように考えれば分かります．まず，二つの集合の差を考えると，後ろの集合は前の集合の部分集合なので，それは $\{uv \in \delta^+(S) \mid c_{uv} - (p_u+\delta) + p_v \leq 0 < c_{uv} - p_u + p_v\}$ になります．これが空集合になるような$\delta$を取れればよいので，$0 < c_{uv} - p_u + p_v$ を満たす $uv \in \delta^+(S)$ がなければどんな$\delta > 0$をとっても空集合となりOKです．そうでないときには，例えば，$\delta = \min\{ (c_{uv} - p_u + p_v)/2 \mid uv \in \delta^+(S), c_{uv} - p_u + p_v > 0\}$と取ればよいはずです．
  • （ただの文句で申し訳ありません）スライド番号43/46のスライドにおいて，微小な正の値を$\delta$と書いていましたが，始点や終点を指定した弧の集合を表す記号にも$\delta$を使っていたので，まだ使っていない$\varepsilon$で微小な正の値を書いてくれたほうが，ほんの少し見やすくなるのかなと思いました（そもそも，このスライドの$2$種類の$\delta$は，集合と数という全然違うものを表しているので，そうそう混同されることも無さそうですが）．
    --ただの文句も大歓迎しておりますので，よろしくお願いします．
    確かに，$\delta$を無思慮に使っていました．すみません．スライド上では$\varepsilon$に修正しました．
  • 最小費用流問題の面白い応用例ありますか？最大流問題では個人的には応用例に驚きました。
    --何を面白いと思うのかということは主観的なので，その点はご了承いただくことにして紹介すると，私が好きなのはグラフ描画の屈折最小化です．これの嚆矢はTamassia (1987) の論文で，関連する研究でも最小費用流の考え方が使われています．
• 12/19 (10) 最小費用流問題：負閉路消去法
  • 対面でお会いできるのは今日が最後でしたね。来年もよろしくお願いします。
    --はい，来年もよろしくお願いします．
  • at first glanceに対応する日本語が出てこない話がありましたが、自分は日本語より先に英語が出てくることがないので、その差はどこから…という気持ちになりました
    --私は数学的なことを割と英語で考えるので，それにつられると，数学的なこと以外も英語で考えることになってしまい，日本語の感覚が弱くなると，とっさに日本語がでてこなくなることがあります．
  • 一気に冬めきましたね。週末は最低気温が氷点下になるそうなので、なるべく屋内で過ごそうと思います。
    --ようやく冬っぽくなってきましたね．:-)
  • 来週からカイロを持ってきます…
    --はい，防寒の準備をしてください．
  • ニット帽がお洒落ですね \(°∀°)/
    --これは防寒の準備です．:-)
  • 寒い中お疲れ様ですm(__ __)m
    --こちらこそ！
  • 積読の解消法を教えてください
    --特に困っているわけではないなら，気にしなければよいと思います．必要だと思って買っているのならば，必要になったときに読めばよいですし，不要だと思って買っているのならば，不要なので売ってしまえばよいです．
  • レポート難しかった；；
    --難しくないと勉強にならないので，ちょうどよかったのでしょう．
  • レポート課題の出来（全体）はどうだったか知りたいです。
    --採点中なので，出来 (全体) はまだお知らせできません．すみません．
  • レポートのおかげで復習をしっかり取る時間ができ、提出も無事できたので、ゆっくり休みたいと思います。
    --はい，ごゆっくりと．:-)
  • 今まで講義で使ってきたグラフは全て目の子で確認していたのですか？
    --実はそうです．;-)
  • 今日はとても味わい深い授業でしたね、これからもっと味わい深くなっていくのかもしれないし、味わい深さがわかるようになるのかもしれない…
    --味わいを感じたならば，すでに味わい深さをわかっているのかもしれませんし，これから深くなっていく味わいもまた分かるのかもしれません．
  • 先週「s-t流は双対問題を考えるときにs,tを特別扱いする必要があり、あまり好ましくないように思える」のようにお答えいただきましたが、最大流もb-流を考えれば双対問題が書きやすくなりますか？（もしくは最大b-流のようなものは存在しませんか？）
    --「最大b-流」の定義にもよりますが，「bを変数として，b-流の中で|b(v)|/2の和を最大にする問題」を考えることはできます．これによって双対問題が書きやすくなるかと言われると，そうでもない気がします．理由の一つは，主問題の変数がかなり増える (各頂点vに対してb(v)も変数になる) ため，双対問題の制約がかなり増えるからです．もう1つは，双対問題の解釈自体が難しくなりそうだということです．最大s-t流を考えたときは，双対問題が容量最小のs-tカットを求める問題であると説明したのですが，最大b-流の場合は双対問題が何を表すのかすぐに判断するのは難しくなりそうです．これは最小費用流問題のときも同様で，最小費用流問題の双対問題が何を求めているのか，ということは，いままで議論していませんし，今後もあまり議論しないことになります．最大s-t流を考えていたときのように，簡単な意味付けは難しそうなのです．(意味付けができないことを主張しているわけではないので，ご注意ください．)
  • 「ポテンシャルを一つ決めると主問題の下界がわかる（？）という直感があまりわきませんでした。」と先週質問して回答を先生から頂きました。自分でも「制約がなくなるという観点、または制約が新たに付け加えるという観点」から考えてみました。まず、ポテンシャルって何かなって考えて、ある点からある点に送るために必要な最小のコストがポテンシャルの差になるように定めたものがポテンシャルだと思いました。($u$の条件は考えずに)このポテンシャルの条件とbの条件と流水制約を満たす流を考えると、$b_v y_v$の和が下界になるはず。実際のb流を考えて、ポテンシャルの条件を満たす流の差の下界は$u_a z_a$の和になる。と、考えたのですが何かが腑に落ちない気がまだしてます。
    --次回 (正カット消去法) では，この観点の話を考えることになると思うので，それを見ると，もう少しまとまるかもしれません．私もまだ考えがまとまっていないので，授業を構成しながらできるかぎり考えをまとめてみたいと思います．
  • 証明につかった図が分かりやすかったです．
    --図による証明はイメージにすぎないので，そのイメージをことばで表現することについては，皆さん自身で行ってください．授業ではイメージを大事にして，まずはそれをお伝えできるようにしています．
  • 負閉路があると最短経路は-∞になるのではと思ったのですが、そうならないようになっていましたね。
    --同じ頂点を何度も通ってよいとして，最短経路の長さが-∞になることもある，という考え方を定義として採用することもあります．この授業では，その考え方ではなくて，経路において1つの頂点は一度しか通ってはならないものとしました．定義に関わる部分ですので，他の文献を参照するときには，どの定義に基づいて最短経路を考えているのか確認しながら理解するようにしてください．
  • 負閉路がなければポテンシャルを作れるところがよくわかりませんでした。擬似sからの距離のイメージがあまりわきません。
    --電気回路のイメージで説明してみます．負閉路があると，その部分は「全体として電気抵抗が負」になっていることになります (もちろん電気抵抗は負になれませんが，イメージですので)．どれだけでも流せることになってしまって，電位 (ポテンシャル) が定まらなくなります．
  • 「距離を-1倍したものがポテンシャルになります！」あまりに唐突で、どうしてそんなこと思いつくんだろう、となりました。今日の浮かび上がってくる怖いポイントでした。先人は偉大ですね。
    --距離に関する三角不等式と簡約費用最適性条件に現れる不等式が似ていることが注目点だと思います．
  • 負の長さを考えるときに，「長さ」って単語に「距離」のイメージが付随してしまうのが「うーん」って思ったので，何か別の言葉をあててみたいものですが，直感と一致する言葉がなかなか見つからないものですね…
    --そのとおりだと思います．一方で，実生活の中で「進むと負になる」状況は案外あったりします．数学的な概念がそのような場合をうまく捉え切れていないのではないかと思います．
  • 考えれば考えるほど，弧の長さが負であるって相当大変なことが起こってると思えてきました．
    --そのため「負閉路が存在しない」という条件はとても重要になります．
  • 今日の講義は，驚かされることがたくさん紹介されたので，とても楽しかったです．咀嚼しきれていないところ（負閉路と三角不等式に関する補題で，証明が省略された部分等）もあるので，じっくりと味わってみたいと思います．
    --はい，じっくりと味わってみてください．:-)
  • 競技プログラミングの文脈では「負の辺や負閉路検出はベルマンフォード」みたいなパターンマッチングがありますが、大学院の授業で出てくるか来ないかくらいの内容だったのか…と結構専門的なことだったのだなと改めて思いました
    --専門的かどうかはともかく，何をどこで扱うのか，ということはカリキュラムのはなしになります．ベルマンフォードを大学1年生で学ぶというカリキュラムはありえます．この授業は「電気通信大学のカリキュラム，特に，情報系 (I類)，融合系 (II類)，情報・ネットワーク工学専攻のカリキュラム」に沿って組み立てているので，大学院の授業で出てくるか来ないかくらいの内容になっているのだとご理解ください．
  • 負閉路の選択の工夫次第で、アルゴリズムが遅くなるだけでなく、停止性にまで響くことは面白いと感じた。1回目のレポートはだいぶ苦労したので、後半の最小費用流問題はこまめに復習しておきたいと思った。
    --「選択の工夫次第で…」という部分は最大流問題に対する増加道法と同じですので，ぜひその箇所も復習してください．
  • 証明が複雑になってきましたね。レポート問題が大変そうです。
    --レポートのことはまず置いておいて，内容を楽しむようにしてください．:-)
  • 先生はレポートで挑戦問題のような解いても解かなくてもいいような難しい問題は用意しないのですか？この前のレポートでも出すのをやめた難しい問題が気になります。
    --レポート提出は，成績評価を目的として行っているので，解いても解かなくてもいいような難しい問題を用意するということはしていません．目的に合わないからです．
  • 最適化問題において，「××が○○を持たない」という形の最適性条件があるときに，「××から○○をひたすら無くす」という形の最適化問題を解くアルゴリズムかもしれないものが思い浮かぶのは，個人的にはそこまで怖くない気がします．（停止性は非自明ですが）停止してくれれば，正当性は容易に言えるところが関係していそうです．
    --むしろ「それを怖くないように感じるぐらい慣れてきた」ということなのかもしれません．アルゴリズムの考え方にあまり慣れていないと，そもそも最適性条件のようなものを考えるということに発想が及びません．それが自然であると感じられれば，最適化やアルゴリズムに対する感覚が研ぎ澄まされてきているのだと思います．
  • 負閉路に関する補題が負閉路最適性条件と簡約費用最適性条件を合致させたとき，証明が気持ちよく，心の中で「おぉ！」となりました．また，負閉路消去法でもそうですが，アルゴリズムに任意性があることで多くの研究アプローチが生まれるため，研究分野として面白そうだなと思っています．
    --そうですね．その辺りは「効率よく解ける最適化問題の数理構造」に関する話題と，「それがアルゴリズム設計にどう活かされるのか」という視点の交差点であって，数理最適化の醍醐味の一つだと思っています．
• 12/12 (9) 最小費用流問題：線形計画問題として
  • 途中でワイヤレス接続が切れてしまい，すみません．動画は再録して掲載する予定です．ただし，少し遅れます．ご了承ください．
  • UECWireless😭
    --「実施形態」に書いたネットワークトラブルがとうとう起きてしまいました．
  • 教授がZoomから落ちたのが「今日はもう授業を終わりにした方がいいかもしれない...」といった話になってすぐだったので、本当に授業が終わってしまったのかと思いました...。
    --滅多なことは言わない方がよい，ということなのでしょうね ;-)
  • 今回のようにzoomが落ちる可能性を考えるとやはり対面で受講するのが安心だと改めて実感しました。
    --大学にいるならば，対面で受講する方がよいように思います．
  • UECワイヤレス、不調でしたね (ノД`)・゜
    --これまでUECワイヤレスさんには頑張ってもらってきてますので，たまに不調になることもあるかと思います．ご了承ください．
  • 授業がスイスイ進むイメージがあるので、レポート課題が相対的に難しく感じます。実際難しいです。
    --そうですね．しっかりと復習しながら取り組んでください．
  • 複数人で協力してレポートを作成した場合についてです。「相談した結果、同じような答案」ができてしまうこともあると思うのですが、その際には、誰とどの部分を協力してそうなったのかを明記したうえで、自分の言葉で説明できるようになっていればいい という感じなのでしょうか。一歩間違えると不正を疑われる可能性があると思うと少し心配になります…
    --「その感じ」という認識で問題ありません．
  • 復習をしていて気になったのですが，第3回線形計画法の復習p.35の相補性定理の証明における1行目から2行目への式変形は，相補性を使用しているので=で結ばれるのではないでしょうか．
    --相補性を利用すれば「＝」で結ばれる，という理解は正しいですし，ここで相補性を使うことができるという理解も正しいです．授業の説明では，主許容性と双対許容性から導かれる「$\leq$」を使っています．どちらも正しいです．
  • 中間レポートを解くうえで過去の線形計画問題の講義資料をみていた際，線形計画問題の係数でなぜb,cという文字を使用しているのか気になっていました．今回の最小費用流を線形計画問題で表現する際に，bが偶然(?)b流のbに対応し，cが偶然(?)費用のcに対応していましたが，偶然でしょうか．
    --どちらかというと，線形計画問題で表現したときに，線形計画問題のbに対応するものを最小費用流問題でbと書くことにして，線形計画問題のcに対応するものを最小費用流問題でcと書くことにしている，という向きで一致させていると考えるのがよさそうです．また，そもそも線形計画問題でbとcを使う理由はアルファベット順で，制約の係数行列がA，制約の右辺がb，目的関数の係数がcと書いただけのような気がします．
  • $b$-流の$b$ってどういう由来があるのでしょうか．b-flow networkで検索してもそれらしい情報はすぐには見つけられなかったです…
    --直前のコメントのように，線形計画問題として書いたときに，線形計画問題における制約の右辺のベクトルbの役割を果たすからだと思います．
  • 最大流問題のときは双対問題の定式化の部分で理解に時間がかかりましたが、今回の内容は最大流問題に類似している部分が多かったのでよく理解できました。レポート問題でしっかり復習できる機会があったのが良かったように思います。
    --復習の甲斐があったようで，よかったです．(^^)
  • 細かいところですが，スライド番号6/39のスライドで，$b$の始域が$A$になってます．
    --ありがとうございます．修正しました．
  • 最小費用流問題は、「最大流問題の最適解(bがちょうど満たされる解)」中で最もコストの低いものを見つけるというイメージであっていますか？
    --はい，そのイメージで正しいです．
  • 最大流問題は「どれだけ流せるか」を探していたと思いますが、最小費用流では「これだけ流したときの最小コストは？」という形で流す量を固定したまま費用の最小化を狙うという点が似ているようで違う感じがしました
    --「最小費用流では『これだけ流したときの最小コストは？』という形で流す量を固定したまま費用の最小化を狙う」というのは正しいです．最大流と最小費用流にある，そのような少しの違いが，いろいろな部分で大きな違いを生んできます．
  • 問題が変わったので最大流問題のことは忘れて新たな気持ちで授業が聞けると思ったのですが、
    --入力が途中で切れてしまっていますか？
    最大流問題のことを完全に忘れてよいわけでもなく，そのときに培った考え方は使っていくので，それは思い出しながら理解するようにしてください．
  • 最小費用$b$流の定義を聴いていた時は，「この定義だけで，非自明な解がでてくるのだろうか」と思っていたのですが，考えてみたら，初回講義における定義での最小費用流で，講義中に口頭で述べられていたsupplyを流す量としたものとほぼ同じものが出てくると気づいて，なるほどと思いました（初回講義での定義は忘れるという話は置いといて…）．1回の講義で，最大$s$-$t$流から続けて話をするのであれば，初回講義の定義の方が，最小費用流を求めたいモチベーション（流す量を固定したときに，一番費用が安い流を探したい）が分かりやすくていいなと思いましたが，改めて最小費用流問題を定義しなおすのであれば，需要と供給が設定される頂点が複数あってもよいという意味で，初回講義の場合よりも一般的な場合が扱える$b$流の方も嬉しそうだなと思いました．
    --需要と供給が設定される頂点が複数あってもよいという場合を考えているのがb-流であるというのはそのとおりですね．一方で，bが与えられたときに，s, tという新しい頂点を付け加えて，b(v)が正であるすべての頂点vに対して (s,v) という弧を付け加えて，その容量をb(v)，費用を0とし，また，b(v)が負であるすべての頂点vに対して (v,t) という弧を付け加えて，その容量を-b(v)，費用を0とし，sからtに (Σ|b(v)|)/2 だけ流すことを考えると，第1回の設定に帰着できます．この意味で，第1回に定義した最小費用流と今回定義した最小費用流は同値になります．
  • 初回の最小費用流ではs-t流を使っていたと思うので、突然b-流が降ってきたような感覚があります。s-t流でなくb-流を取り扱うに至った意味がそのうち分かるようになるのかな？と思いながら聞いていました（増加道法が浮かび上がってくるのと同じような不思議さがありました。もしかしたら理解が浅いだけで自然なのかもしれません）
    --すみませんが，s-t流ではなくb-流を取り扱うに至った意味はあまり分からないかもしれません．今日の授業では，双対問題を書きましたが，s-t流で考えると，sとtを特別扱いにしなくてはならなくて，それがあまり好ましいように思えませんでした．一方，b-流で考えると，sとtのように特別な頂点がないので，双対問題が書きやすくなりました．そのような効能はあったように感じます．
  • スライドの主問題や双対問題を考えるときの $f_a$ は、弧 $a$ が与えられたとき、その上に流れている量を表す関数 $f(a)$ の略記という形で導入したと理解しています。主問題から双対問題を求める際に、一旦行列やベクトルを経由するので、fはベクトルになって、その後また関数に…という点がごちゃごちゃしてしまいがちで、追いかけるのが大変でした。ベクトルや行列を導入して双対問題を求めるけど、双対問題自体はベクトルや行列を使わなくても表せるというのが少しおもしろく感じました。
    --記法についてはすみません．はじめから全部ベクトルとして書けばよかったのかもしれません．
  • 補助ネットワークで順向きと逆向きの弧を考えていますが、元のネットワークの時点で順・逆向きの弧や自己ループがある場合はどうなるのでしょう。例えば弧$\{(v_1, v_2), (v_2, v_1)\}$があるときの二つの頂点$v_1,v_2$間の補助ネットワークの弧は最大で４本あるという認識で合ってますか？
    --最小費用流問題においては，その認識で合っています．実をいうと，元のネットワークにおいて，順向きの弧がたくさんあっても構いません．その意味では「弧 $uv$」のような記法は正確でなかったと反省しています．
  • グラフの問題を電気回路のような現実の物理現象に則したやり方で解いているのは面白いと思った。内容を咀嚼するために、授業のテンポをやや落として欲しいと感じた。
    --現実の物理現象に即したやり方で解いている，というよりは，それを使って直感をお伝えしていると捉えてください．授業のテンポはすみません．動画をうまく活かしてください．
  • ポテンシャルの単位はコストと同じで「価格/流量の単位」となる？
    --「ポテンシャルの単位はコストと同じ」というのは，そのとおりだと思います．ただ，その単位が「価格/流量」かどうかは状況に依存しそうです．費用は価格ではないかもしれないので．
  • ポテンシャルを一つ決めると主問題の下界がわかる（？）という直感があまりわきませんでした。
    --双対問題の目的は-Σu(a)z(a)+Σb(v)y(v)を最大化することですが，まず，双対問題の気分を説明します．第二項Σb(v)y(v)の気分は，外部から供給のある頂点 (b(v)が正である頂点v) のポテンシャルを大きくし，外部へ出ていく頂点 (b(v)が負である頂点v) のポテンシャルを小さくして，供給側から需要側にうまく流していこうとすることを考えていることと思ってください．そして，第一項-Σu(a)z(a)は，ポテンシャルを大きくしすぎることで容量制約を違反した場合のペナルティだと思ってください (u(a)もz(a)も非負なので，-Σu(a)z(a)は必ず非正です)．簡約費用最適性条件の証明でも出てきたように，yが与えられれば，そこからzをz(uv) = max{0, -c(uv)+y(u)-y(v)}と決められるので，zの役割はわりと従属的です．
    ポテンシャルから主問題の最適値の下界が得られる直感的な説明を，電気回路の類推で試みてみます (考えたことがなかったので即興でやっていて，適切ではないかもしれません)．
    電気回路では，抵抗と電位が分かっていれば，オームの法則とキルヒホッフの法則から，電流が分かります．いま，最小費用流問題でも，ポテンシャルが分かっていれば，そのようにして，流が分かるとします．しかし，これはオームの法則とキルヒホッフの法則 (等式) しか使っていないので，得られた流が容量制約 (不等式) を満たしていないかもしれません．そのため，その費用は最小費用よりも小さくなることがありえて，つまり，主問題の最適値の下界になります．
    いま書いたことの「オームの法則とキルヒホッフの法則から」といっている部分は，最小費用流の文脈でいえば，キルヒホッフの法則が流量保存制約，オームの法則が相補性条件に対応するはずです．あまりうまく説明できた気がしないのですが，参考にして．皆さんも考えてみてください．
  • 電流と電位が双対関係であるという話が気になりました。
    --電気回路における双対性は例えばwikipediaのこのページに書いてあります．眺めてみると雰囲気が分かるかもしれません．
  • 電流と電位が双対の関係にあると聞いて，双対についてもっと深く学んでみたいと思いました
    --双対性はいろいろな分野で現れます．この記事を見ると，その一端と有用性が分かるかもしれません．物理学に関わる側面は例えばこの本に書いてあったりします．
  • 最近，西4号館周辺の木々が割と色とりどりなので，西4号館に向かうついでに眺めるのがちょっとした楽しみになっています．
    --そうですね．季節の移り変わりを感じますね．
  • 急に寒くなったですね、研究室にも暖房をつけました
    --お体には気を付けてください．
  • 年末なので、身の回りの整頓をしなければと思いつつ、寒さを理由に先延ばしにしてしまっています。特に、書類やノートの整理は最後まで手を付けられないです。
    --暑いうちにやっておいた方がよかったのかもしれませんね．
  • 今度の出張はどちらへ行かれるんですか？
    --静岡県です．
  • 就活と課題でなかなか研究が進みません。やりたいことができないときの工夫や精神面の支えがあったら教えていただきたいです。
    --私も知りたいです．教えていただきたいです．
• 11/28 (8) Push-Relabel法 (計算量評価)
  • 本日もわかりやすいご説明ありがとうございました．
    --こちらこそありがとうございました．
  • 課題の出題から提出までどれくらいの期間を想定していますか？1週間くらいでしょうか？
    --2週間くらいです．
  • 中間レポートがそろそろとのことなので、今までの講義を一通り復習しておこうと思います。
    --はい，宜しくお願いします．
  • レポート課題についての先生の考え方を知りたいです。私の知り合いのある先生は、レポートは協力しても教えてもらってもいいけど、教えてもらったことを使って自分で計算すれば（証明問題ならば教えてもらったことを使って自分で証明を書き上げれば、プログラミングなら教えてもらったことを使って自分で実装すれば）問題ないと言っていました。協力して考えることや教えることで理解が深まるだろうとも言ってました。でも人から答えを教えてもらったものをそのまま提出したり、証明を人に書いてもらう（書いてもらったものを写す）のは時間の無駄だからやめた方がいいと言ってました。先生の課題は1人で考えるのが前提の課題ですか？それとも相談や協力してより課題と授業をより理解することも想定された課題ですか？
    --後者です．人間はひとりでは非力です．独力で何でもできるように努力することは重要ですが，実際はそのようにできないことが多いのです．問題の解決には，いろいろな技術や知識を持ち寄って取り組むべきです．そのように考えています．
    と書いておいて，ここから説教が始まります．そのような集団があったとして，技術や知識を提供できない人は，ただ単に切り捨てられます．表面上そう見えていないだけであっても，深い部分ではそうなっていて，時間が立つにつれて，深い部分にあったものが段々表面に現れてきます．ご注意ください．ぜひ，そのような集団において，提供できる何かを持てるようになってください．
  • 「まれによくあることですが」先生が課題を適当に出した結果、未解決問題が混ざってたり、授業の内容を遥かに超えていたりすることがあるので、授業で使ったことで証明できるって知っていると安心です。
    --確認した結果，出そうとしていた問題は難しすぎるという判断に至ったので，実際にでているレポート問題は割と取り組みやすくなっていると思います．
  • 離散数理工学と比べてコメント要素が多くて楽しく読んでいます。やっぱり先生がたくさん話しているとコメントしやすいのかな？と思ったりしました。
    --別の授業のことをいって恐縮ですが，来年度から離散数理工学の教授法を変えようと思います．
  • 前半はあまりに早くてついて行くことが大変でした…なんとか追いかけられたので良かったですが、かなり頭を回し続けた気がします…
    --おそらく，私の準備が不足していたからだと思います．すみませんでした．
  • 去年のグラフとネットワークの最初の方で出た握手補題さんと感動の再会を果たしました！
    --握手補題はグラフ・アルゴリズムの解析ではよくでてきます．アルゴリズムにおけるローカルな操作とグローバルな計算量評価をつなぐことができます．
  • 授業においては$d(u) \leq 2n-1$の証明はpush操作とrelabel操作でプリフローとlabelの定義を満たし続けるということを使った証明でした。push操作とrelabel操作から直接示すことはできそうですか？
    --できるかもしれないのですが，考えたことがないのでよくわからず，いまちょっと考えてみましたが，やはりよくわからなかったです．操作だけではなく，操作を行うことができるための条件が重要で，「アルゴリズムの実行中に，頂点 $u$ に流れが残ってしまう状態に何度なりうるか」ということを実際は見ている気がします．
  • 非飽和Pushの回数がO(n^2m)になる証明の方法は、自分にとって新鮮なものでした。今後の研究においてアルゴリズムを考える際に活用できればと思っております。
    --ぜひ活用してみてください！
  • 今回の不思議はΦはどうやって見付けてきたのか…というのが不思議でしたね
    --これは不思議です．こういうものを思いつくことが計算量評価におけるトリックになったりします．
  • スライドp.26で導入されたΦですが、「○○関数」のような固有名詞はないのでしょうか？
    --ある本には「ポテンシャル」と書いてあります．ただ，ネットワーク・フローの文脈において，ポテンシャルというのは別の概念に用いるのがふつうなので，授業ではその呼び方をしないことにしました．
  • (スライドNo.34) 非飽和pushの総階数の上限はΣ(Φの減少) + Σ(Φの増加)ではないのでしょうか？
    --これは正しいですが，それだと欲しい結論がでてきません．実際，授業で示している「Σ(Φの減少)」も正しい上界なので，そちらを使っています．
  • アルゴリズムの計算量解析の途中でちゃっかりpush-relabel法の停止性が示されたの面白かったです．
    --これは失礼しました．授業の準備をしているときに，これを説明することを忘れないようにしないといけないな，と思っていたのですが，忘れていました．忘れないように，しっかりと1ページ割いてちゃんと書いておくべきでした．
  • Relabel(u)の操作で、1 回あたりの計算量がO(|δ±(u)|)になる説明をお願いできないでしょうか。すでに授業で説明していたら申し訳ありません。あ
    --Relabel(u)では，d(u) を min{d(v) | uv が補助ネットワークの弧} + 1にします．uvが補助ネットワークの弧であるようなvの数は多くても|δ±(u)|になり，そのようなvに対してd(v)を調べるので，O(|δ±(u)|)になります．
  • 新たな視点を知れて賢くなった気がします．そういう意味で，学部のグラフとネットワークで扱った最大性論法を割と好んでいるのですが，先生は何かありますか？
    --最大性論法は私も好きです．数学に限らず，各分野には典型的な論法があるので，いろいろな分野でそのようなものを学んで，使えるようになってください．
  • 最後に軽く出てきた最大ラベルPush-Relabel法のように条件を一文つけるだけで計算量が結構減ることに驚きました。実装時には最大あるいは最小を選ぶのはよくある条件ですが、計算量的にも合理的であるというのは嬉しいと思いました。
    --そうですね．ただ，授業の中では述べませんでしたが，最大のものや最小のものを選ぶにはコストがかかる場合があります．Push-Relabel法においても，最大ラベルの頂点を効率よく選べるようにするには，データ構造に工夫が必要になってきます．その側面とのトレードオフもあるので，そこも注意しなくてはならないことになります．
  • 今回、最後の方に少しの工夫で計算量が減るという話がありました。思えばEdmonds-Karpの時と比べると、選択肢が複数あるときに何かを最大（最小）化させるというのが共通しているように感じました。これは工夫の一般論のようなものを知っているから、うまくいっていることの中に欠点や改善点を見出せたのかなと感じました。
    --任意性があると，アルゴリズムがなぜか「都合よく悪いものを選ぶ」ということができてしまいます．それを防ぐために，ある種の基準に従ってアルゴリズムに無理やり選ばせるようにすることが有効になることが多いのです．なお，何もアイディアがない場合，「選択肢が複数あるときにランダムに選ぶ」ということを行うことがあります．これが案外うまくいきます．例えば，クイックソートというものがありますが，ピボットの選択に任意性があります．ランダムにピボットを選ぶという方法を使うと，(期待値のオーダーの意味で) 最良のソート・アルゴリズムが得られます．
  • 削除マーカーを付けておく方法でデータを持つ話、実際にコードを書いたことある話だったので馴染み深く感じました
    --そういう経験と今回の話がつながってよかったです．いろいろなものがつながっていくと，自分の中で体系が組みあがっていく思います．そういうことを通じて，自分なりの視点ができていくように思います．
  • 借金（踏み倒し可能）
    --実際，授業で紹介した「借金」は返す必要がありません．ただ，本来は「貯金」にした方が意味合いとしては正しかったかもしれないと思っていて，説明がよくなかったように思っています．
  • 私も、卒業式で「頑張った、Push-Relabel法!」って叫びたいです
    --ぜひぜひ :-)
  • 授業と関係ありませんが、\$ を使うとLatexみたいな数式を表示できるというコメントを見たのでテストさせてください...。 $\Phi$はちゃんと大文字のΦになっているでしょうか。また$\{x_{1}, x_{2}\}$とすると1, 2は添え字になっているのでしょうか。
    --はい，このように表示されます．ただし，最初のドル記号はエスケープして，ドル記号として表示されるように私が手を加えました．
  • 先生の好きなコーヒーありますか？セブンイレブンのやつ美味しいです。
    --特に好きなものはありません．しいて言えば，濃い方が好きです．
  • 昨日は日中でも10数℃と冷え込んだ一方、今日は20℃を超えたりと不安定な気候ですね。風邪も流行っているので、体調を崩さないよう気をつけて過ごしたいです。
    --寒暖差が激しいですね．気をつけて過ごしてください．
  • 本日もありがとうございました。私事ですが、風邪を引いてしまい、なかなか治らないです...最近急に冷え込んできたので、先生もお気をつけください。
    --ありがとうございます．ご自愛ください．
  • 調布祭楽しかったです！
    --それはよかったです :-)
  • 調布祭を通して難しいことを誰にでもわかるレベルまで落とし込むことにチャレンジしましたが、情報の切り捨てと説明の整合性を両立しつつ本質を伝える、という点で難しさを感じました。先生が専門分野の説明をするときに心がけていることがあれば教えていただきたいです。
    --心がけていることは，相手に合わせることです．聴衆が誰であるかによって発表スタイルは変わりますし，変えています．前にも書いたかもしれませんが，私の授業のスタイルといわゆる学会発表のようなもののスタイルはかなり違います．(そもそも，学会発表のようなものでは証明のことは細かく話しません．) また，学会発表のようなものであっても，数学の場，アルゴリズムの場，人工知能の場，情報系一般の場，オペレーションズ・リサーチの場，大多数が学生である場，など，いろいろな状況があります．それぞれで話し方や話す内容を変えています．重要だと思っているのは，「聴衆の前提知識」と「聴衆の期待」です．自分が伝えたいことを一方的に伝えるのではなく，聴衆にとって役立つことを私の中で考えて，それを伝えられるようにと思って，話す内容と方法を考えています．
  • 先日、粘菌コンピュータというものを知りました（論文までは読んでません）。自然自体がある種の最適化機能を備えていることは改めて面白く、だからこそ多くの研究が行われているのかと思いを馳せていました。
    --生命の計算機構は小林先生や関先生がその専門家です．また，粘菌による計算は，鏡像降下法 (mirror descent) という最適化アルゴリズムと関係があることが知られています．例えばこのような論文があったりします．
• 11/21 (7) Push-Relabel法 (概要)
  • 今日も怖くなかったです。
    --私も今日は怖くなかったです．
  • 最近就活が忙しくなりメンタル的にきつくなってきました。先生なりのメンタル安定術があれば教えてほしいです。
    --私も知りたいです ;-) 毎日，毎週，毎月，毎年同じことをしていると気が滅入ってくるので，新しいことをしたりするとよいのかもしれません．
  • 昨日食べすぎてお腹が痛いです
    --これは単純で，食べ過ぎないようにしてください．:-)
  • 今日は人が少なかったですね、寒いからでしょうか？
    --寒いだけで人が少なくなると，今後はずっと人が少ないことになりますね．;-)
  • 最近の先生は何だかご機嫌に見えます。やはり、コメントの力なのでしょうか。
    --自分では気づいていないのですが，そうなのかもしれません．:-)
  • 今日誕生日です！！！☆*:.｡. o(≧▽≦)o .｡.:*☆ 先生は誕生日いつですか？
    --おめでとうございます (めでたいのかわかりませんが)．誕生日はわりと大きな個人情報なので，私は公にしていないようです．
  • ボジョレーヌーヴォー飲みました？僕たちは飲みました（＾ν＾）
    --飲んでいません．私は基本的に飲酒しない生活をしています．
  • 1905年11月21日、E=mc²の式が載ったアルベルト・アインシュタインの特殊相対性理論の第2論文がドイツの学術誌『アナーレン・デア・フィジーク』に掲載される。
    --E=mc²というと，私はすぐにホーキングの『ホーキング、宇宙を語る』を思い出します．まえがきに書いてあるエピソードとして，編集者に「数式を1つ入れるごとに読者が半減する」と言われて，数式をできるかぎり削ったが，E=mc²だけは削れなかった，というものです．いま調べたらWikipediaにもそのエピソードが書いてありました．これは研究室で発表練習をするときによく引き合いにだしています．数式は可能なかぎり減らして，それでも削れないものというのは余程の覚悟をもって入れるものだ，と．
    とか言っておきながら，授業のスライドにはたくさん数式があるじゃないかと思われるかもしれません．しかし，それは目的が違うのです．授業のスライドのように資料として見返すことが必要となるものと，10分や20分程度の発表で雰囲気やアイディアを伝えることが重要であるものは，その設計の基礎になる考え方が同じであるはずがありません．その点に注意して，場所，時間，聴衆，目的に合わせた発表資料を作る必要があると考えています．
  • このような場で，コメントを投稿してくださる方に向けてのコメントは本来よろしくないのですが… 時々，$\TeX$で処理されて欲しそうな文字列をコメントで見かけますが，インライン数式を書く時のように，処理してほしい部分をドル記号$1$つで囲ってあげると$\TeX$で処理されたような表示になります．もしかしたらドル記号$2$つで囲うと，別行立て数式として表示してくれるかもしれません．（以前，太字を書きたくて，bmパッケージを前提にした書き方をしてしまったのですが，偶々ソースコードを覗いたら，パッケージを使わないでできる太字表記の書き方に変わってました．手間を掛けさせてしまってすみません…）
    --一応，そのとおりですが，これはMathJaxを呼び出しているからできているだけなので，その機能に依存する形でしか表示できないことにご注意ください．そのため，うまく表示されないときは，私が手作業で (表示されるべき様子を推測して) 書き換えています．ご了承ください．
    なお，ダラー2つで囲むと $$ \sin(\alpha+\beta) = \sin\alpha\cos\beta + \cos\alpha\sin\beta $$ のように別行立てになります．
  • まとめのスライドがとても勉強になりました．何かが腑に落ちた気がします．
    --今回は，お気持ちの部分と細かい数学の議論のある部分が入り組んでいて分かりにくかったかもしれません．私自身の理解が浅いのだと思います．引き続き勉強していきます．
  • 証明が難しいです。
    --ぜひ復習をするときに，独力で証明しようとして試してみてください．そうすると，どういう証明の道筋で考えるとよいか見えてきて，授業で紹介した証明が割と自然なものであるように感じられると思います．
  • 講義だけでは理解が追いつかない箇所が出てきたので、復習頑張ります。
    --動画もありますので，有効に活用してください．
  • アルゴリズムの話は面白いと思った
    --アルゴリズムの面白さをお伝えできたようで，私もうれしいです．:-)
  • P14の前流の別称が「プリプロー」になってました。
    --これは意図どおり「プリフロー」と書いています．「プレフロー」という訳語でもよいと思いますが，ある本に「プリフロー」と書いてあったので，それをここでも書いてます．辞書によると発音はカタカナで「プリ」に近いようなので，間違ってもいないように思います．
  • 今回は定義づけが多い回でしたが理解しやすかったです．また，例も多くこちらもスムーズに理解することができました．
    --例は重視しています．まずは例を通して理解してください．
  • Push-Relabelは増加道を使うよりも直感的でいいですね。話は変わりますが、矛盾を示す際に使った稲妻のような矢印記号は一般的なものですか。初めて見たので少し驚きました。
    --矛盾を示す際に使った稲妻のような矢印記号について，これは私の学問的な背景に依存しているかもしれませんが，私が学生のときにはよく見ました．ただし，板書でしか使わない記号であって，論文や教科書で使うものではないと認識しています．Unicode (16進) では21afで，「↯」と表示され，使うことができます．
  • （感想）PDFのスライド34枚目は、背理法の代わりに対偶で示しても導けると感じました。（以下雑談）今週末は学園祭がありますが、おすすめのブースはありますか。
    --感想について：そのとおりですね．証明の流れの本質は授業で紹介したものと同じになるように思います．雑談について：すみません，私はブースを見たことがないので，何ともいえません．
  • push-relabel法のアルゴリズムの動作は面白いと感じました．ただ，スライドのように自分の力でpush-relabel法を行うとなると，必ずpushし忘れ等のミスをしそうです．余談ですが，講義途中の換気時の寒さが厳しくなってきました．
    --換気についてご意見ありあとうございます．換気の仕方を工夫するようにしたいと思います．
  • Push-Relabelアルゴリズムに関して，とりあえず詰まってもいいから始点から流せるだけ流したあと，流として適切でない部分をチマチマ直しているように見えて，効率がよくなさそうにも思えたですが，入力の頂点数に対するオーダーで比較すると，講義で紹介されたEdmonds-Karpのアルゴリズムよりも計算量が小さくなると予告されて，かなり不思議だと思いました．
    --そうですね．Push-Relabelの計算量がEdmonds-Karpよりよくなることを予見するのは難しいように思います．結果的にそうなっているだけのような気もします．ただ，増加道に基づくアルゴリズムでは，各反復で増加道が存在するか考えないといけないので，各反復でO(m)ステップ使うのは避けられないように感じます．一方で，(次回扱うことになりますが) Push-Relabelでは各操作を割と高速に実行できます．そのあたりも効率に関係しているように思います．
  • Edmonds-KarpよりPush-Relabelの方が計算時間が短いのは双対許容性を常に満たすようにしたからなのか、単に効率の良い方法を見つけただけなのかが気になります。
    --その2つから選ぶとなれば「単に効率の良い方法を見つけただけ」の方が近いと思います．線形計画法 (今回の場合は相補性定理) がアルゴリズム設計の指針を与えても，そこから効率まで導くことはいまの数理的技術で可能ではないように感じています．アルゴリズムの効率というものを数理的にうまく捉えることはいまだにできていないように思います．現状では，それほど計算理論というものが未発達なのだと認識しています．
  • Push-Relabel法は増加道法と比べてローカルに着目しているのに、計算量が少なくなることがあるのは目から鱗でした。全体最適化で全体にこだわりすぎるべきではないのは良い経験になりました。
    --そもそもs-t流を保持しないことでローカルな操作の積み重ねによって計算できるという発想が生まれるのは，私も面白いと感じました．なお，プリフローの概念はGoldberg-Tarjanよりも前にKarzanovが違う用途のために提案したものなのだそうです．その点はここで補足しておきます．
  • Ford-FulkersonとDinicは見たことあったのですが、push-relabelは初見だったので面白かった。プロフローの考え方が湧き上がってくるのは不思議でしたが、線形計画的な観点から見ると自然なのかもしれませんね…
    --線形計画法を違う形で使うと異なるアルゴリズムが得られるかもしれません．一つの問題をいろいろな角度から見れるのも，最適化アルゴリズムの面白さのひとつだと思います．
  • （Push-Relabelアルゴリズムの停止性の証明をまだ確認していないので，確信は持てないですが）$1$つの頂点の周辺に対する操作という，非常にローカルな操作だけで最大流が必ず見つかるというのは，すごく奇跡的に思えます．
    --そうですね．いままで考えていた増加道法よりも直感的には分かりにくいと思います．今回の授業では，線形計画法の相補性定理との関連を示すことで，Push-Relabel法が自然なものであることをできる限りお伝えしようとしてみました．
  • ローカルなやりとりで最大流が完成することに面白さを感じました。生命の体のなかでは局所的な操作しかできないはずだけど一体感のある動きができるような不思議な面白さを感じました。
    --そのとおりですね．生命のイメージをとりいれるときには，同期も重要になってきそうです．Push-Relabel法は局所的な操作の繰り返しで動きますが，その操作を2つ以上同時に行ったりすると，変なことが起きてしまいそうです．その意味では，並列分散的なアルゴリズムなのではなく，逐次的なアルゴリズムなのだけど，その操作が局所的であると考えるのがよいように思います．一方，生命体で，例えば細胞を考えると，それらがクロックを共有しているわけではないので，明示的に同期を取れず，複数の操作を同時に行ったりして，困ることが起きてしまうこともありそうです．しかし，物質を通じた制御によって，うまく同期が取れているように見えているのだと思います．生命を情報の視点から捉えたり，生命現象を情報処理に用いるという考え方は活発に研究されている分野ですので，興味があれば調べてみてください．
  • Relabelを行える条件（Push(a) を行える弧 a ∈ Afがない）がRelabel と距離ラベルの証明のどのように現れているのか気になりました．
    --「Push(a)を行える弧 a∈ Afがない」ときにしかRelabelを行わないようにしないと，距離ラベルの更新を延々と繰り返そうとして，アルゴリズムが止まらなくなる可能性があります．次回はRelabelが何回行われる可能性があるのか考えて，計算量解析につなげていく予定です．
  • 相補性定理において，許容解であるという条件は「当たり前やろ」って思ってて軽く見ていたのですが，まさか増加道法における補助ネットワークの動きを観察するために役に立つとは思わなかったです．
    --おそらく，線形計画法に対するアルゴリズムを普通に作ろうと思うと「主許容性と双対許容性を満たすものを保持して，相補性を満たすようにする」と考えると思います．しかし，実情は違うようで，例えば有名な単体法 (シンプレックス法) は「主許容性と相補性を満たすものを保持して，双対許容性を満たすようにする」という動きになっています (そのように理解したり記述されることはあまり無いように思いますが)．どのような動きであっても，相補性定理 (つまり，最適性条件) が重要な役割を果たしているという共通の原理があります．最小費用流に対する話では，いろいろな形で相補性定理を使うことになる予定です．
  • 主問題と双対問題のどちらから始めるか、という違いが最終的なアルゴリズムの違いにも反映されるというのはとても興味深いです。いずれにせよ、相補性がそれを支えるカギになってることもよくわかりました。
    --線形計画法を学ぶとき，相補性定理はあまり強調されないような気がします．しかし，相補性は「効率よく厳密に解ける最適化問題」に対して極めて有効な考え方であるだけでなく，難しい問題であっても，相補性条件を満たす点を見つけることが問題解決の鍵になることがあります．
  • $z_{uv}$と$y_u$と$y_v$の変数で少し混乱しました。$y_u$と$y_v$がきまれば自動的に双対問題の目的関数の値が決まるようなイメージを持っていたのですが少し違うような気もしてきました。
    --ある意味では，自動的に決まると思っていただいてよいです．適当な $y$ が与えられたとき，各弧 $uv$ に対して，$z_{uv} = \max\{0,y_u-y_v\}$ とすれば，$y,z$ が双対問題の許容解になります．制約を満たすだけならば，$z_{uv}$ は $\max\{0,y_u-y_v\}$ より大きくてもよいのですが，そうすると目的関数値も大きくなってしまうので，できるだけ小さくしようとすれば，このように決めるのがよいと思います．
  • 距離ラベルdが双対許容解を満たしていることはどのようにイメージすれば良いでしょうか。双対問題のzやyと対応づけられるということなのでしょうか。
    --対応づける，とまでは言えませんが，距離ラベル d から，双対問題の許容解 y, z を作ることができます．
    適当な整数 k (ただし，0 ＜ k ≦ n) を定めます．ここで，頂点 v に対して，d(v) ≧ k のとき，y_v = 1 として，そうでないとき (つまり，d(v) ＜ k のとき)，y_v = 0とします．このとき，S = {v | y_v = 1} とすると，d(s) = n，d(t) = 0 であるため，Sはs-tカットであることが分かります．s-tカットと双対問題の関係は第4回の講義で述べたとおりで，s-tカットから双対問題の許容解 z を作る方法もそこで紹介したとおりにできるわけです．これで距離ラベルdから双対問題の許容解y, zが作れたことになります．
    これは第4回の講義 (というか，そこで終わらなくて第5回のはじめの方で紹介することになった) 乱択丸めの話に似ています．そこでは z を使って距離を定義したのですが，その考え方が距離ラベル d にも現れていると思うと想像しやすいかもしれません．
  • 講義の最初の方で，Push-Relabelアルゴリズムは，実装において各々が考えた工夫をする余地があると仰っていましたが，例えば，Relabelを施すことが可能な頂点が複数あるときに，どの頂点から行うかは工夫の余地がありそうだと思いました．既にその類の研究はよく行われてたりするのでしょうか．
    --はい，そのとおりで，既にその類の研究がよく行われています．それによって計算量評価が変わってきます．次回の講義で，時間があれば少し触れようと思います．
  • よく復習して、中間レポートに備えようと思います！
    --はい，よく復習をしてください．
  • レポートが片付いたら、授業で習ったアルゴリズムから何か一つを選んで実装したい気持ちが芽生えてきました。
    --それは素晴らしいです．ぜひ実装して何か分かったら教えてください．
• 11/14 (6) 最大流問題：容量スケーリング法
  • 先週とは打って変わって，冷え込みが厳しくなりましたね．
    --冬が近づいてきたのだと思います．はっきりとした四季があるのは日本の特色ですので，しっかりと味わってください．
  • 先週との気温差が凄いので風邪引きそうです。先生も体調に気を付けてください。
    --ありがとうございます．皆さんもご自愛ください．
  • 急激に寒くなったため体調を崩してしまいました。最近インフルエンザも流行っているらしいので先生も健康にはお気をつけください。
    --私はインフルエンザのワクチンを接種しました．ワクチンを打てば罹らない，というわけではありませんが，ワクチンを打たずにおびえる必要はないので，その点は効果があると感じてます．
  • いきなりの寒さで体調が良くない日が続いたのですが、何か先生のおすすめ対策ありますか。
    --規則正しい生活を送ること，でしょうか．私自身はうまく実践できていませんが．
  • 世界糖尿病デー（せかいとうにょうびょうデー、World Diabetes Day、WDD）は世界保健機関（WHO）が定めた国際デーである。11月14日で、インスリンの発見者フレデリック・バンティングの誕生日に当たる。
    --医療の発展は偉大だと思っています．歴史を通して，社会における多くの問題が技術によって解決される様子を私たちは見てきました．皆さんはその歴史の一部になっていくのだと自覚して，ぜひ勉強していってください．
  • 最近料理を始めようかと思っています。先生は普段料理をされますか？また、得意料理はありますか？
    --私は料理をしない生活を選びました．ということで，ほとんどしません．たまに気分転換のために料理をしますが，たいしたものは作りません．魚を焼くぐらいです．
  • 今日は急遽2限にゼミがあり、リアルタイムで講義を受けられませんでした。オンデマンドで配信があることがありがたいです。
    --大学院生はいろいろと急な予定が入ることがあったり，急でなくても学会・研究会参加などのために授業を休む必要があることは予見されます．動画はそのときのための対策としてもお使いください．
  • dopalのlは何の略ですか？
    --algorithmの2文字目です．「何の略ですか」という質問は，そもそもそれが略であることを想定した質問になっています．略ではない可能性もあるわけなので，そのような聞き方はあまり適切でないかもしれません．「何を指していますか」「何を表していますか」のような表現の方が聞き方としては適切であるように思いました．
  • 今日は怖くなかったです。
    --それはよかったです :-)
  • 今日の話は前回よりも分かりやすかったです！(これはみんな書きそうでつまらないコメントかも)
    --私自身もそう感じました！
  • 前回の授業より分かりやすい内容だと思ったが、前回が悪夢のようだったとは思っていませんでした。
    --「悪夢」は言い過ぎだったと反省しています (-_-;
  • 寝不足で来てしまったため，どこかで追いつけなくなるかもしれないと心配でしたが，先週ほど複雑怪奇な議論はなかったので助かりました．
    --「複雑怪奇」ぐらいの表現が適切だったかもしれません．「アルゴリズムの動きを理解する」ことと「アルゴリズムの性質を理解する」ことは割と違うことなので，その点はここ数回の授業で強調できているのではないかと思います．
  • val()が線形だということの気持ちをもう一回教えてほしいです
    --val(f) の定義を見ると，それは f(a) の線形結合でした．そのため，val(2f) は 2f(a) の線形結合となって，それは f(a) の線形結合の2倍です．これが線形であることの気持ちです．
  • 容量スケーリング法のアルゴリズムと計算量についてもよく理解することができました．
    --それはよかったです．容量スケーリングは最小費用流問題でも考えるので，そこでまた復習することになります．
  • 容量u(a)の丸めをビット演算と見るところ(スライドp20)、個人的には見通しが良くて好きです
    --私自身も好きです．私がはじめて容量スケーリング法を勉強したときは，その気持ちがよく分からなかったのですが，2進表現を使った説明を教えてもらって，よく分かるようになった気がします．
  • ビットスケーリングの簡単な工夫で計算量が指数時間から多項式時間で解けるようになることはとても嬉しいと感じた。Edmonds-Karp含め、計算量の証明は特にしっかり追っておきたい。
    --計算量の証明は難しい部分もあるので，まずはアイディアを理解するようにしてください．自分で証明できるようになる必要はないと思いますが，同種の考え方が必要になったときに，勉強しなおして理解できるような能力を重視するようにしてください．
  • 容量スケーリング法は途中までざっくばらんな解なのに最終的に最適解になるのが不思議でした。
    --実をいうとそんなにざっくばらんな解でもないのです．例えば，第1反復では容量を0か1に丸めてしまっているのですが，これは容量を非常に荒く近似していると見ることができます．その近似の度合が，反復を進めるごとに細かくなっていくのです．そして，途中で得られているs-t流もだんだんと最大s-t流に近づいていくことになります．何も関係のないところから，最大s-t流が突然登場してきているわけではないわけです．
  • スケーリングを行い、計算量の短縮を行う工夫は別の問題でも活用できると感じました。
    --私の理解が正しければ，ネットワークフローの研究は「スケーリングとの攻防」という側面が強かったように思います．いろいろな量をスケーリングの対象にできるため，何をスケーリングの対象として，どのようにスケーリングすると高速なアルゴリズムが得られるのか，ということが熱心に研究されていたように思います．また，この授業で扱っているのは線形の問題 (線形計画問題として書ける問題) なのですが，そうでない非線形なネットワークフローの問題もあって，その場合には扱いがさらに難しくなります．しかし，そうであっても，スケーリングを行うための巧妙な方法が考えられたりしています．
  • 近似で最大流が出るのが面白いと思いました。今回はついていけてよかったです。
    --前のコメントの回答の続きになります．今回扱った容量スケーリング法では，各反復の最後で得られているs-t流が，最大s-t流の近似になっているという性質が重要な役割を果たしています．しかし，非線形なネットワークフローに対しては，そのような都合のよい性質が成り立つとは限りません．そのために，スケーリング法を適用しようとするときには，都合のよい性質が成り立つように入力を変換したり，別の問題を解いたりして，うまくいくような工夫が必要になります．この点はかなりややこしいのですが，どうしてそれでうまくいくのか，という点が私にはあまり直感的に分からず，奥深さを感じています．
  • いろいろなアルゴリズムがあってそれぞれの長所と短所があってアルゴリズムを複数考える必要性を感じました。でも、前回のEdomonds-Karpのアルゴリズムの感動が凄すぎて容量スケーリング法が「当たり前の工夫」に見えてしまいました。（話は変わりますが、当たり前に見えるくらい分かりやすい授業をありがとうございます。）
    --当たり前であることはよいことだと思います．基本的な考え方として，アルゴリズムはシンプルであればあるほどよいと思っています．ただ，シンプルであるだけだと，計算量が大きくなってしまったり，望ましい性質を持たなかったり，いろいろと困ることも起きえます，望ましい性質を持ち，かつ，シンプルであるような方法を追求することが，アルゴリズム研究の王道であるように思います．
  • 前回のEdmonds-Karpのアルゴリズムの証明と比較して，今回の容量スケーリング法の証明の理解度はとても高いです．特に，容量スケーリング法の概要（動作例）と証明（数式）がうまく繋がり，解釈しやすかったです．
    --アルゴリズムの説明は例から入った方が分かりやすいと思っていて，そのような説明法を採用しています．式や疑似コードだけを見て，動きを想像することはなかなか難しいと感じます．
  • 増加量が最大の増加道を選ぶ方法ではどのように増加量が最大の増加道を選ぶのでしょうか。最大流問題を解くのでしょうか。
    --以下のように二分探索を利用します．補助ネットワークが手元にあるとします．ある量 $\theta$ を考えて，容量が $\theta$ 以上の弧だけ使って，増加道が構成できるか判定します．これは，容量が $\theta$ 未満の弧をすべて取り除いて，s から t に向かってグラフ探索をすれば分かります．もし増加道があったら，$\theta$ を増加させます．増加道がなかったら，$\theta$ を減少させます．これによって，「増加道が存在するような最大の $\theta$」が二分探索等の方法で分かります．そのような $\theta$ が最大増加量になります．
  • 弧容量関数から評価される計算量は現実の世界では欲しい計算の精度と言い換えることができますか？
    --「言い換え」と言ってしまうと強すぎる主張になってしまう気がしますが，そのような解釈はできます．例えば，あるkに対して，第k反復で計算を打ち切ってしまって，その反復の最後で得られているs-t流を出力してしまう，というアルゴリズムを考えることができます．その場合，出力は最大s-t流ではないのですが，ある程度の近似になっていることが保証できます．反復回数は O(m log k) になります．容量スケーリング法では k = K まで計算を真面目に行うわけですが，そこに至る前に計算を止めてしまえば，計算量を短縮することができるわけです．近似で十分ならば，そのような方法を採用することもできるわけです．
  • Uのような青文字変数になる条件は max u(a) などを求めるのが定数時間ではなさそうなものを指定するという解釈であってますか？(P.12 青文字変数の選び方を聞き逃してしまったかもしれません) / UはO((nやmの式))で表すとn,mに関する多項式なのか，指数関数なのか，それとも定数なのかわからないのに log Uという形でlogをつけると弱多項式というのが不思議に感じました (軽くスルーしていたので2^{log U}だけ違うということを言いたかっただけなのかもしれない？と思いました)
    --分けて答えます．(1) すみません，容量を表す文字を青にしてるだけです．一方で，流を表すものは赤，費用を表すものは緑にしています．分かりにくくて (説明していなくて) すみません．(2) Uはn, mと関係を持っているか分からないので，計算量はn, m, Uに対する依存性で測ります．いままで考えているアルゴリズムの計算量は (反復回数)×(各反復の計算量) で表されますが，各反復の計算量はO(m)になります．反復回数だけがアルゴリズムによって異なるのですが，それがn, mだけに依存するのか，n, m, Uに依存するのか，という点で，Uが計算量に入ってくるかどうかが変わります．それが強多項式時間と弱多項式時間の分かれ目です．Uの入り方が「log U」として入ってくれば，計算量は弱多項式時間になり，「U」として入ってくれば，計算量は擬多項式時間になります．「log U」か「U」か，が弱多項式と擬多項式の分かれ目になります．「弱多項式」といっている理由は，「入力サイズに関して多項式」であることを考えているからだと思ってください．入力サイズはスライドの12ページに書いてあるものです．
  • UがlogUを基準にすると指数になるために，Uがあると擬多項式になるというのは，スッキリしませんが理屈は分かりました．
    --「擬多項式」という呼び方が混乱を招く元凶のような気もします．擬多項式時間アルゴリズムは多項式時間アルゴリズムではないので注意してください．「多項式時間アルゴリズム」と呼ぶときには，「入力サイズに関する多項式」を考えているのだということはポイントなので，理解してください．
    一方で，これは案外根深い問題です．(正の) 整数を表現する方法はいろいろとあり，もちろん2進法だけでなく，3進法や4進法を考えることもできます．しかし，そのどれであっても，その方法で整数Uを表現するときの桁数は O(log U) になります (定数だけが変わります)．一方で，1進法というものがあり，これはつまり，「0」しか使えないのですが，整数Uを表現しようと思ったら，「0をU個並べる」ことになります．この場合，桁数は O(U) になります．つまり，1進法と2進法では桁数に指数関数的な違いがでるのに，2進法と3進法，3進法と4進法，…，では，桁数は定数倍しか違わないのです．これは「入力の符号化法が計算量に影響を与える」という可能性を示唆しています．そして，実際，入力の符号化法によって，計算量が変わってしまう例が知られています．今回の授業では整数を2進法で表すことを暗に仮定していますが，そうしなくてはならないわけではなく，ただ単にそれが標準的な方法であるからここでもそうしているだけだと思ってください．
  • Push-Relabel法も楽しみです。一概にはいえないのかもしれませんが、Edomonds-Karpのアルゴリズムとどちらが難しいですか。
    --一概に言えないのはそのとおりなのですが，まず，比べるべきものはPush-Relabel法と増加道法になります．増加道法の工夫のひとつとして得られるのがEdmonds-Karpのアルゴリズムなのですが，Push-Relabel法にもいろいろな工夫が存在しています．そのため，工夫する前の増加道法と工夫する前のPush-Relabel法を比較するのが公平かと思います．
    その観点で比較すると，増加道法の方が考え方は自然であり，わかりやすいと思います．一方で，Push-Relabel法は (工夫がなくても) 必ず停止します．実装自体はPush-Relabel法の方が簡単だと思います．Push-Relabel法に工夫をいれると (数学上も実装上も) 計算量が改善するのですが，その場合を考えるのは増加道法に対してEdmonds-Karpのアルゴリズムを考えたときと同じように難しくなります．
  • 弱多項式時間かつ証明が易しいというのは嬉しいですね。増加道法に基づかない来週の内容は少し楽しみです。
    --ぜひ楽しみにしていてください．
  • Push-relabel法に楽しみです。
    --ぜひ楽しみにしていてください．
  • 昨晩、京王線が停電で容量0になってしまいある許容解で帰りましたが、最適かどうかわからなかったのでしっかり学ぼうと感じました。
    --まずは，許容解が存在してよかったです．;-)
  • 先生が研究職を目指されたきっかけや動機はなんですか？
    --はっきりと覚えていませんが，おそらく知的好奇心が第一だと思います．第二は教育に携わりたいと考えたからだと思います (これは「研究職を目指した」という質問の意図とは離れて，現在の職を目指したことに対する動機を答えているようにも思います)．知的好奇心を刺激し，満たすということは，現在の職において大いに達成されているように感じます．これを社会に還元する一つの方法として教育を取っています．
  • テスト無しの授業でテストをやるってどう思いますか？？僕は許せません
    --状況がよく分かりませんが，テストをやるなら，それは「テスト有りの授業」なのではないでしょうか．
  • そろそろ第1回目のレポート課題が出る頃でしょうか。
    --そうですね．しっかりと復習をしておいてください．
• 11/7 (5) 最大流問題：Edmonds-Karpのアルゴリズム
  • 一番前の席なのに、2人してウトウトしてました(*´ー｀*)
    --内容が分からないとウトウトしがちになる気分は分かります．;-)
  • 証明は私には難しすぎました。
    --証明自体はすぐに理解できなくてもよいと思います．このような論法 (証明の方法) があることをまず理解してください．
  • 難しくなってきました、付いていけるように頑張ります
    --たぶん，次回はもう少し簡単になります．
  • 今回の内容は難しく、わかるようなわからないような感じになっているので復習したいと思います。
    --はい，復習をよろしくお願いします．
  • 復習するたびになんとなく理解が進んできた気がするので復讐にもっと力を入れようと思いました。。
    --復讐に力をいれるのは勘弁してください．;-)
  • 証明で登場する記号が多くなり、追い着くのが大変になったので、しっかりと復習しておこうと思いました。
    --無理に時間内に収めようとしたのがよくなかったかもしれません．復習をお願いします．
  • 弧数が必ず増加するところの証明難しかったです
    --はい，私も難しいと思います．
  • 増加道の概念について理解できました．また，アルゴリズムの具体的な例が非常にわかりやすかったです．
    --例は重視しています．自分でも例をつくって考えてみてください．
  • 双対問題のあたりや証明は聞きながら追えず、とても難しく感じました。動画を見て復習して、わからなかったら来週質問を投稿しようと思います。よろしくお願いします。
    --はい，質問は過去のものに遡ったものでも構いません．ぜひ質問をお願いします．
  • 今朝電車の中で予習しているときに衝撃が走りました。アルゴリズムが止まる工夫が「必ず弧の数が最小の増加道を選ぶ」という「単純」なものだなんて！だけどその発想からアルゴリズムが止まることは自分では示せませんでした。証明を眺めてみても弧数の単調性が自明に見えなくて・・・。授業で聞いたけど証明やっぱり難しいです。
    --このような単純な工夫でうまくいってしまうのが，アルゴリズムについて研究したり勉強したりするときの楽しみだったりします．ついでに，証明まで単純だと言うことはないのですが．ただ，その分野における技術が研ぎ澄まされたり，理解が深くなっていくと，簡単な証明が見つかってくるということは，数学やそれを使う学問分野においてはよく起きます．今日扱った内容の証明も，もっと単純なものが見つかっていくのかもしれません．
  • 証明を吟味するだけでも大変でしたが、証明した人は特に異次元だと感じました。
    --急いでしまったために，あまり直感をお伝えしなかったのがよくなかったです．直感としては，増加道を選ぶと逆向きの弧がどんどん出来てくるので，sからtに行きにくくなっていくことになります．そのため，「弧数最小の増加道における弧の数は減ることがない」，という直感が出てきます．一方で，弧数最小の増加度における弧の数が増えないとすると，増加道法の動作から，ある弧の向きが何度も変わることになります．これが起こると，距離の単調性が失われて矛盾が得られるので，実際は，あるタイミングで弧数最小の増加道における弧の数が増えることになるのです．この直感をちゃんと考えて証明したとお考え下さい．
  • アルゴリズムの停止問題を初めて考察しました。
    --皆さんはアルゴリズムの授業を受けたりすることが今まであったり，これからもあったり，あるいは，自分でアルゴリズムを考えることもあると思うのですが，アルゴリズムが本当に停止するのか，とか，どうなったら停止するのか，とか，停止するためにはどういう仕組みが備わっていないといけないのか，ということは，しっかりと考えていただきたいと思います．アルゴリズムの授業ではその辺りがいい加減になっている場合があると思います．いい加減ではよくないので，見直してみて，自分でもぜひ考えてみてください．なお，アルゴリズムの授業がいい加減であるという認識があるので，その反省も込めて『数学セミナー』で連載をしています．興味があればご覧ください．
  • 怖かったです
    --怖いことばかり起きてしまい，すみません ;-)
  • 双対問題の最適解のスライドで，孤の距離（1/8など）がどう決まっているのかというのを聞き逃してしまいました．
    --これは，双対問題に対して既に見つかった最適解を表していると思ってください．授業でやっているのは，そこから容量が最小のs-tカットを構成する方法の説明です．
  • 第4回の36/45のスライドで，最短路長の例を示すときに，$s$から先生が選んだ頂点への道の長さがどれも同じで「うーん」って思っていたように見えましたが，多分，あの例は，どの頂点を選んでも，$s$からその頂点への道の長さはどれも同じになっていそうです(そうであることに何か意味があるのかもしれないのですが…)．
    --この例ではそうなっていました．遠回りするような経路がある例をつくるべきだったと感じました．
  • cap(S)が双対問題の最適値になることについて、積分を考えた証明を考えたのですけど、確率を使った証明とよくみたら同じでした。（確率を積分と言い換えたような証明です。）確率というと少し仰々しく感じる人がいるように思う、一方で、積分や微分というとアレルギーを起こす人もいると思います。確率で説明した決め手はなんですか。
    --積分を使う必要がなく，積分を使うことでむしろ見にくくなると思ったからです．もちろん期待値は積分を使って定義されるわけですが，今回は別に積分をしたいわけではありませんし，積分で書いたとしても一様分布に従う場合しか考えていないので積分で書く利点はあまりないと思っています．そのため，より直感的に理解できる期待値で説明しています．
  • 今日の資料15ページの図が画面に出ている図と違う気がしたのですが、合っていますでしょうか。
    --すみません．これは元の図が間違いだったので，手元では直したのですが，掲載したものを直すことはできませんでした．今は直したものを再掲載しました．
  • 結論は変わらないのですけどp.21で$d_{i+1}(u)+1=d_{i+1} (v)$とあるのですが、イコール付き不等号までしかわからないような気がします。何か見落としているのでしょうか？
    --$(u,v)$ が $s$ から $v$ へ向かう弧数最小の道が使う弧であるからイコールになります．「最短経路の部分経路も最短経路である」という性質を使っていると思ってもらってもよいです．
  • p.22 の「(u,v)はG_f_i の弧ではない→(v,u)がG_f_iの弧」というところで、そもそも弧が張られていないという可能性はあるのでしょうか？（必ず(v,u)が張られていると言えますか？）
    --この証明の中の状況では，必ず弧があります．$(u,v)$ は補助ネットワーク $G_{f_{i+1}}$ の弧であるので，$(u,v)$ かその逆向き $(v,u)$ は元のグラフ $G$ の弧です．そのため，$(u,v)$ かその逆向き $(v,u)$ は補助ネットワーク $G_{f_i}$ の弧であることになります．
  • 背理法を使う証明は，どの段階の仮定（最終的に証明したいことなのか，証明に利用したいために仮定したことなのか）に矛盾しているのかに気を付けないと，あっという間に訳が分からなくなりますね…．
    --その通りですね．スペースや時間を節約しようとして，そのあたりを割と曖昧にして進めてしまいました．
  • 今日の講義は，最大性（最小性）論法や標示確率変数といった，学域3年生の時に受講した先生の講義で重要だと述べられていた道具が躍動していて楽しかったです（同時に難しくもありましたが…）．
    --そのとおり，躍動しましたね :-) 基礎的なことを応用する場面が現れた，ということだと思います．
  • 弧数増加の十分条件の証明（2/2）が，呑み込み切れなかったので，復習してきます．
    --私も途中で詰まりましたからね (-_-;
  • 今回扱ったアルゴリズムとは逆に，弧数が最大のものを選び続けた場合でも増加道法は必ず停止するのでしょうか。
    --これを私は考えたことがなく，誰も考えていないと思うのですが，おそらく停止しない場合があります．停止しない場合があると思う理由は，第2回の補足動画で扱っている停止しない例は，毎回「弧数がほぼ最大」の増加道を選んでいるからです．また，誰も考えていない理由なのですが，「弧数が最大のs-t道を見つけること」が難しい (専門用語を使って言えばNP困難) であるからです．そのため，これが停止するとしても多項式時間アルゴリズムが得られないことになります．(「多項式時間アルゴリズム」については次回解説します．)
  • ダイクストラの最短経路アルゴリズムのように限定しないとどのアルゴリズムだか分からない…確かに…となりました。ダイクストラさんは有名な最短経路のアルゴリズム以外も提案していたというのは知らなかったです
    --ダイクストラはプログラミング言語や並行システム・分散システムの研究でも知られています．「GOTO文の悪さ」を説いて，構造化プログラミングの重要さを指摘しはじめた人の中の一人でもあります．分散計算の研究に対する著名な賞にはダイクストラの名が冠されています．
  • 開発したアルゴリズムに名前が残るのはかっこ良いですね
    --3人以上になると頭文字で表すことが多いように思います．例えば，文脈自由言語のパージングを動的計画法で行うCYKアルゴリズムは，CockeとYongerとKasami (嵩) の名をとっています．(ただし，「Cocke」がつく由来となった論文はCockeとSchwartzの共著であるようです．)
  • エドモンズさんはすごく面白そうな人です。
    --検索したら，そのような写真が出てきたので ;-)
  • 第5回の5/41のスライドにある，Edmondsさんの写真がとても楽しげですが，これがWikipediaに載ってるんですね．
    --そうですね．息子 (息子も研究者) が撮影したようです．
  • ランダウのO記法の「ランダウ」を物理学者のランダウだと勘違いしていた時期があり、自分は考案者の名前を冠した学術用語に苦い思い出があります。
    --O記法を考案したのはランダウではなくバッハマンのようです．ややこしいですね．
  • 休みの日は何をして過ごすことが多いですか
    --ドトールにいます．休みの日でなくてもドトールにいます．
  • 今日はやたら暑いですね。
    --そうですね．授業の後で汗だくになっていました．(-_-;
  • もう11月なのにどうしてこんなに暑いんでしょうか。温度差で体調崩しそうです。
    --季節の変わり目は体調を崩しやすいので，ご注意ください．
  • 今年の10月の頭は割と肌寒い日もあったと記憶しているのですが、ここ数日は11月にも関わらず最高気温が25度に達する日が続いていてびっくりしています。
    --すぐに寒くなるそうですので，ご注意ください．
  • 涼しくなったと思えば今週は夏日が続きますね。先生もどうぞご自愛ください。
    --こちらこそ．
  • 東n号館に在住しているものです。西8号館が遠すぎていつも泣きながら来ています。これからの時期は寒くて涙も出なそうです。
    --弧の数が最も少ない経路を見つけてお越しください．
  • 久々に通学時間に雨が降る予報が出ていましたが，狐の嫁入りに出くわすとは思わなかったです．
    --『狐の嫁入り』に類する言い回しは，いろいろな言語であるようです．フィンランド語では「狐の行水」なのだそうです．
  • 銀杏がとても多くて嫌なので、なにか研究利用できませんかね。
    --まず，そういう発想はとても重要ですね．ただ，イチョウはIUCNレッドリストのカテゴリーでEngangered (絶滅危惧) に分類されてますので，大事にしていってください．
  • 先生のヘッドセットが、カチューシャみたいで可愛いです;)
    --実は，カチューシャみたいではないのもあるのですが，無線 (Bluetooth) で，口からの距離もちょっとあり，うまく音が拾えなかったりしたので，カチューシャみたいな有線のものを使っています．
  • dopalのaは何の略ですか？
    --algorithmの頭文字です．
  • 一九一七年一一月七日（露暦一〇月二五日）、十月革命がロシアに起こった。三月（露暦二月）にツァーリズムが崩壊したあと、臨時政府とボリシェビキが対立していたが、この革命によってレーニンを指導者とするボリシェビキが臨時政府を倒し、世界最初の社会主義政権が成立した。
    --私はもちろんソ連 (ソビエト連邦) と呼ばれていたころや冷戦の状況を知っているものですが，ソ連がなくなって，いろいろな都市の名前が代わり，混乱したことを覚えています．いまでも昔の名前の方が分かりやすいと感じてしまうことがあり，しっかりアップデートしないといけないと思っています．
• 10/31 (4) 最大流問題：線形計画問題として
  • 次回は今回の残りから始めます．よろしくお願いします．
  • お菓子をくれなきゃいたずらします…！
    --今さら言われても困ります ;-)
  • trick or treat!!!!!
    --この「or」は「さもなければ」の意味のorであるものの例として有名です．ただ，あまり日常生活でその意味のorを使うことは (定型的な言い方を除いて) ないような気がします．学問においてはよく「publish or perish」という定型的な言い方があります．このorも「さもなければ」の意味なのですが，このフレーズの内容が真実であり，学問のあるべき姿なのかというのは別の問題ではあります．ただ，多くの研究者が認識していることであるとは思います．
  • 言われるまで今日がハロウィンだってことを忘れてました．
    --実はそうなのです．
  • 岡本先生の仮装、見れなくて残念です:'-(
    --それは残念でした ;-)
  • 今回もありがとうございました。
    --こちらこそありがとうございました．
  • 分かりやすかったです。
    --それはよかったです．ありがとうございます．
  • dopalのpは何の略ですか？
    --optimizationの2文字目です．
  • 先生の早口に置いていかれないようにがんばります。
    --早口であるのは自覚しているのですが，どうせ皆さんは動画になれば倍速で見たりするわけなので，早口ぐらいで皆さんにはちょうどよいのではないかと思っている自分がいます．ただ，そのおかげで授業の中で例をたくさん扱うことができるようになっているという点はご理解ください．
  • zoomの画面に表示されていたスライドを表示しているアプリケーションの名前はなんですか。
    --DrawboardPDFです．
  • Maximizer Maximizer!
    --Oliver!やMoulin Rouge!のように「!」のつく映画タイトルはいくつかありますね．Maximizer Maximizer!という映画があるか知りませんが．
  • 「書いたものがこちらになります」って言われるたびに3分クッキングを思い出して「フフッ」てなります．
    --まぁ，事前に準備がしてあるという意味では，同じようなものなのかもしれません．
  • いつもより理解しやすい授業内容のように思えたので良かったです。
    --それは良かったです．質問があったら，ぜひお願いします．
  • 今日の授業で、新しいトピックを学び面白かったです、ちょっと難しかったと思いますが、先生の説明のおかげてわかりやすくなりました。
    --毎回何か新しいことがありますので，毎回面白いと感じてもらえるように努力します．:-)
  • スライド番号が35/45となっているスライドに関して，右上端の図でカットから出る弧の容量の文字を青くしているのですが，左下の1だけ青くなっていないと思います．
    --ありがとうございます．ご指摘どおりです．修正しました．
  • 符号がおかしくなっていたところで混乱したので、修正スライドを見ながら復習しようと思いました。ついでに35ページの右上のカットが一部青文字になっていない気がします。
    --符号の混乱はすみません．ご指摘の箇所とともに修正しました．
  • s-tカットは、そこに含まれる頂点をまとめてカット自身を1つの頂点としたもの、というように考えていいのでしょうか。
    --はい，そのように考えてよいです．
  • スライド26から27の条件式の書き換えがいまいちピンときませんでした。この書き換えは同値ととらえていいのでしょうか。
    --はい，同値であるととらえてください．
  • 最後のs-tカットを求める距離が離散的にわかるということですが、軽い理解では距離の計算に容量を用いてそうに見えました。容量が無理数の場合でも離散的になるのでしょうか？
    --距離の計算に容量を用いています．そのため，容量が無理数である場合，距離は無理数になる可能性があります．ただ，その場合であっても，s-tカットの頂点数が増えるような距離の値は有限個に限られます．それは (対象としているグラフの頂点数が有限であるため) s-tカットの数が有限だからです．そのため，このプロセスで得られるs-tカットの数も有限になります．
  • 最小容量のs-tカットがネットワークのボトルネックになっていると考えると考えると最大流最小カット定理が直感的に理解できました。
    --直感的な理解はそのとおりです．ただ，その直感だと val(f) ≦ cap(S) しか示せていないかもしれません．等号が成り立つのが最大流最小カット定理のすごいところなので，それを味わってください．
  • ベクトルで書き表されている部分が書き下されていて、イメージしやすくわかりやすかったです。
    --例を重視しています．ぜひ自分でも例を作って書くのを試してみてください．
  • 最大流問題の双対問題は、元の問題と比較して、より簡潔に記述できていると感じました。ただ、式の見やすさは主問題の方が見やすいと思いました。
    --そうですね．双対問題の制約は実質的に $z_{uv} \geq y_u - y_v$ という形のものだけなので，主問題より簡単に見えますね．双対問題が何を表しているのか，ということは，また後の方の授業で考えることになります．
  • 最大流問題の双対問題を，目的関数に関係無い変数にうまく制約を与えることで，式が簡単に表現できるさまを見て「おぉー」と思いました．
    --私も「おぉー」と思いました．うれしさが皆さんと共有できると，これもまたうれしいです．
  • Randomizer rounding がおもしろいです。
    --これは今回残ってしまったので，次回の内容になります．お楽しみに．
  • スライド番号が33/45となっているスライドに表れる双対問題の最適解を用いて，講義で紹介されたプロセスを経て得られる$s-t$カットが，実は全て最小$s-t$カットになるという主張は驚きました．次回はこれの証明がなされる（正確には，プロセスを経ることで少なくとも$1$つは最小$s-t$カットが得られるという主張ですが）ということで楽しみです．
    --実をいうと，組合せ最適化を扱っていると，このような結果や論法がわりと出てきます．その例としてs-tカットの場合を紹介するのが目的の1つになっています．
  • 双対問題の最適解がs-tカットの容量を考えることで分かるという事実は面白いと感じた。新しい記号等も多く導入されたので、復習でしっかり確認したい。
    --はい，復習をお願いします．
  • 今回のスライド29/45で、y_vとz_aの値を下2行のように設定することが腑に落ちませんでした。個人的な理解としては、スライド30/45で導かれるΣ_{a∈A}u_az_a=cap(S)が成り立つために逆算して設定された値であると考えたのですが、その理解で合っていますか？
    --その理解で合っていますし，私自身はそのように導いています．本当のことを言えば，双対問題が許容解を持つことだけを言おうと思うならば，もっと簡単な方法があります．それは，s, t以外の各頂点 $v$ に対して $y_v$ を適当な (何でもよい) 実数として，各弧 $uv$ に対して $z_{uv}$ を $\max\{0, y_u-y_v\}$ とするのです．これは双対問題の許容解になります．それを踏まえて説明すると，29/45においてs-tカットを持ち出しているのは，その後の話の伏線にするためです．今回残ったところなので，次回の内容に続きます．
  • 双対問題というよくわからないものからs-tカットが現れましたが、増加道法のときより怖いかもしれないです。
    --たしかに怖いですね :-)
  • グラフとネットワーク、および線形計画法は履修済みであったが、これらが融合されるとネットワークを新たな視点から見れることが分かった。
    --まさに「大学院の授業」っていう感じがしませんか？
  • 線形計画問題への落とし込み方がよくわかりました。
    --考えている問題を他の形で書き直す，というのは有用なので，ぜひ身につけてください．
  • 最大流を線形計画問題として定式化したので，線形計画問題を解いて最大流などを求めると思っていたのですが，なぜ次回で増加道法のアルゴリズムの話に戻るのかというのが，話の展開として分からなくなってしまったので，教えて欲しいです．
    --話の展開が分かりづらくすみません．質問をしていただいて助かります．展開は以下の形になります．(1) 第2回で増加道法を紹介．増加道法では「停止すれば最大s-t流が求まる」ことが言えるが，停止するとは限らない．これでは困るし，そもそも最大s-t流が存在することすら言えていない．(2) 第4回では，最大流問題を線形計画問題として書いた．双対定理を使うことで最大s-t流が存在することが分かった．(3) 第5回 (次回) では，第4回で存在すると分かった最大s-t流を見つけるように増加道法を今一度考える．増加道法に工夫を入れることで，それが必ず停止することを言う．こんな感じです．実をいえば，増加道法で使う補助ネットワークは線形計画法の相補性定理と関係があります．これは第7回の授業で扱う予定です．
  • 増加道法のときはs-tカットはs-t流の道具に思えたが，双対関係にあることに驚いた．
    --今回の授業で扱ったように「双対問題を考える」というのは数理最適化における非常に強力な手法です．今回のように，一見関係なさそうなものを結びつけるのに役立つだけでなく，問題を解くアルゴリズムを考える際に使えたり，問題を書き換えることで見通しをよくすることができたり，などなど，いろいろなところで使えます．自分でうまく使おうとするのは難しいかもしれませんが，機会があったら，ぜひ使えるかどうか考えてみてください．
  • 講義はじめのつかみ（仮装の話）とてもよかったです．講義について，最大流問題をそれより上位の線形計画問題として考えるプロセスが面白く感じました．ただ数式変形の説明の理解が追い付いていない状況です．
    --数式の変形はわりと機械的にやっているので，落ち着いて考えれば自力で導けると思います．復習してみて，分からなかったら改めて聞いてください．
  • 今更ですが、流fを変化させて値val(f)を最大化させるという問題は、変分法っぽく感じました。
    --ちょっと私には変分法っぽさがわかりませんが，そのように，いろいろなものを関連させて考えることはよいので，どんどんと関連を見出していってください．
  • lを[0,1]で変化させていくとs-tカットの領域が増えていくのはパーコレーションみたいで面白いです。
    --浸透現象を見るという意味ではたしかにそうだと思いますね．
  • スライド番号が14/45となっているスライドに関して，$\boldsymbol{f} \in \mathbb{R}^A$としていたのですが，$\boldsymbol{f}$の成分の数を$n$として，$\boldsymbol{f} \in (\mathbb{R}^A)^n$あるいは$\boldsymbol{f} \in (\mathbb{R}^n)^A$ではないのでしょうか．
    --これはもとのままで正しいです．$(\mathbb{R}^A)^n$とすると，これは各成分が$\mathbb{R}^A$の要素であるような$n$次元ベクトル全体の集合になります．つまり，$\boldsymbol{f}\in (\mathbb{R}^A)^n$とすると，$\boldsymbol{f}$は$n$次元ベクトルで，その各成分が$A$から$\mathbb{R}$への関数を表すものになります．一方で，考えている$\boldsymbol{f}$は，$A$から$\mathbb{R}$への関数なので，$\mathbb{R}^A$の要素になります．$\boldsymbol{f}$の成分数は$|A|$ (弧の総数) であると考えてください．
  • 最大流問題を線型計画問題と考えたとき双対性は何になるかについて楽しみすぎて自分で具体例を考えていました。1時間半くらい考えてやっと最大s-t流に対応しているこような気がしました。（そしたら重みのつけたs-tカット？という謎につきあたりましたが・・・stの道に対応した1の分割と考えるとうまくいく？）第２回の授業で、「最大s-t流」と「fに増加道が存在しない」と「最大流」であることが必要十分であることが示されました。これは、特殊な場合（最大流問題）での強双対定理を示したことになるのでしょうか？また、これは一般の線型計画問題の強双対定理の証明に拡張すること、または、一般の場合で似たような手法で強双対定理の証明をすることが可能でしょうか？別のきき方をすると一般の線型計画問題でも増加道のアナロジーは有用でしょうか？
    --いくつかの質問があるので，分けて答えます．(1) 第2回の授業が最大流問題という特殊な場合の強双対定理を示しているのか，という質問に答えます．第2回の授業の内容だけでは強双対定理の証明になっていません．もう少しちゃんというと，第2回で証明した (と言える) のは「増加道法が停止すれば，最大s-t流の値とs-tカットの最小容量が等しい」ということになります．一方で，強双対定理は「最大s-t流の値とs-tカットの最小容量が等しい」ということになります．第2回で証明したことには「増加道法が停止すれば」という仮定がついているのが重要です．そのため，第2回の授業の内容だけでは強双対定理の証明になっていないことになります．一方で，次回は増加道法が必ず停止するような工夫を考えます．それによって，「増加道法が必ず停止するようにできる」ことが分かり，これによって，第2回の内容にあった仮定が必ず成り立つことになり，増加道法を使って強双対定理の証明が完了することになります．(2) 最大流問題の考え方を一般の線形計画問題の強双対定理の証明に拡張することができるか，という質問に答えます．ある意味でこれは可能です．どういう意味かというと，アルゴリズムを用いて強双対定理を証明するということです．教科書に書かれている証明でよくあるものは，単体法 (シンプレックス法) を使って強双対定理を証明するという方法です．ただ，単体法の停止性はわりとややこしく，私自身はあまり好きな証明法ではありません．他には，十文字法 (クリスクロス法) を使った証明があり，これは『計算による最適化入門』という本で紹介されています．他には，フーリエ・モツキンの消去法を使った証明があり，これは『凸多面体の数学』で紹介されています．
  • それぞれのバックグラウンドや話す時の環境によると思いますが、関数と函数と写像の言葉の使い分けは先生はどう考えてますか？
    --「関数」と「函数」の使い分けについて，私はもっぱら「関数」を使っています．それが標準的に用いられていると感じているからです．次に「関数」と「写像」の使い分けについて，数学において私は同じ意味で使っています．
  • プログラムを組む際に苦戦している場合、先生ならどうしますか？
    --何に苦戦しているか分からないので，一般的な問題解決法になってしまいます．問題を小分けにすることです．プログラミングにおいては問題を小分けにしやすいようなプログラミングを行う必要があります．そのために，関数やメソッド，クラスをうまく使うのがよいと思います．
  • 以前質問で先生は「私にとって質問することは，自分がもっと分かりたいとかもっと知りたいと思うことを聞くだけの行為であって」と回答されてましたが、「分かりたいとか知りたい」ことはどこまで当てはまりますか。発表者の研究内容はもちろん「分かりたい」し、「知りたい」というのはもちろんですが、今後どんな研究に発展するのかや、どんな研究の準備をしているか、なども「分かりたい」や「知りたい」ことに入りますか。さらには、発表者がちゃんとわかっているかなぁとか適当に話してないかなぁなど教育的な視点での発表者の理解度についても「分かりたい」や「知りたい」ことに入りますか。
    --はい，それらは全部私が理解したいことになります．
• 10/24 (3) 線形計画法の復習
  • スライドが大変見やすく解りやすかったです。
    --今回は字が小さい部分もあり，スライドが混んでいたと思います．復習するときには，拡大などをしながらご覧ください．
  • 教室が寒いです。
    --すみません，使っている教室は手元で冷暖房を調整できず，中央管理されているため，ご要望は教員で解決できないことになります．おそらく，11月になると暖房が入るのですが，それまでは着るもので調整してください．
  • Zoomでも配信いただいているおかげで、寝坊しても授業に間に合いました。ありがとうございます。
    --できるだけ寝坊しないようにしてください． ;-)
  • dopalのoは何の略ですか？
    --optimizationの頭文字です．
  • 授業内容の質問だけでなく授業範囲外の雑談にも答えが返ってきて，しかも何回コメントをしてもいいということで，とても勉強になっています．他の授業では得られない養分があるので，先生の授業がもっとあれば養分を提供させていただけるのになぁと思いました
    --量は増やせません (増やしません) が，提供する分はどんどん吸収していってください．:-)
  • 先生にとって面白いコメントとは何でしょうか。
    --どんなコメントでも面白いですが，私が気づかなかったことに気づけると，特にうれしいです．
  • そろそろ研究室配属の季節だと思います．私の研究室では，昼間からお酒を飲む人がいたり，麻雀をやっていたりします．先生の研究室はどのような雰囲気ですか？また，手のかかる人はいますか？
    --学生がなにをしているのか，つぶさに観察しているわけではないので，分かりません．他の人に迷惑をかけなければ何をやってもよいと思っていますし，そのように接しているつもりです．
  • 自転車通学しているのですが、最近寒く通学するのが大変になってきました。一方、空気が乾燥しているため、富士山が見える機会が増えてきました。
    --冬は空気が澄みますからね．音も遠くまで響くようになるそうです．
  • １９２９年１０月２４日、ニューヨーク株式取引所で空前の株価大暴落が発生し、「世界恐慌」の始まりとなったのが木曜日であった。
    --世界的な株価大暴落はたびたび起きますが，月曜日にひどく起きている印象を持っています (統計的に多いかどうかは調べてません)．ただ，日本は月曜日に祝日を多くつくるようになった (ハッピーマンデー制度) のおかげで，月曜日に起きがちな恐慌のときに市場が休みになり，恐慌の効果が和らいているのではないかと思っています (これもデータは見ていません)．ハッピーマンデー制度自体にはあまり肯定的ではないのですが，このような効果もあるのならば，良い面の一つとして認識されてもよいように思っています．
  • 本日もありがとうございました。
    --こちらこそありがとうございました．
  • 数式が複雑になってきたので復習して理解したい。
    --確かにそうですね．無駄にややこしく説明してしまった気もします．他の説明の仕方もあったのですが，今回はこの方法を採用して，よかったのか悪かったのか，自分でもよく分かりません．ただ，今回ややこしくしたおかげで，次回以降は (他の方法で説明した場合に比べて) シンプルになるはずです．
  • 行列や一般的な式が多く複雑に見えますが、ひとつひとつ丁寧に確認すれば理解できる内容でした。
    --式変形はわりとややこしいので，しっかりとひとつひとつ確認するようにしてください．よろしくお願いします．
  • 最後の方は転置が多くて理解に時間がかかりそうです。図が多いので雰囲気でわかりやすくていいですね
    --転置はややこしいですね．$\boldsymbol{x}^{\mathrm{T}}\boldsymbol{y}$ ではなく，内積を使って $\langle \boldsymbol{x}, \boldsymbol{y} \rangle$ のような形で書いていくという議論の方法もあったと思いますが，それを採用しませんでした．最適化の教科書では転置を使う方法を採用していることが多いように思いますので，この授業でもそれに従いました．
  • 特に双対定理の序盤で置いていかれてしまったので、授業後半は内容が頭に入ってこなかった。双対定理・相補性定理の導出を追い切れなかったので、復習でしっかり確認したい。
    --導出自体は今後の授業を理解するうえで重要ではないので，その点はご注意ください．ただ，やっていることの見た目はややこしいですが，本質は難しくないはずですので，ぜひ復習して理解してください．
  • 線形計画問題の記述において，maximizeやminimizeの行にカンマを入れないのは，英語として読むときにそれが自然だからということでしょうか．
    --自然だからというよりも，そういう規則だから，という方が正しそうです．日本語では句読点の使い方が明確に定められてはいないのですが，英語ではかなり細かく決まっています．句読点や約物 (やくもの) の使い方を句読法 (くとうほう，punctuation) といいます．日本人は，日本語の句読法がいい加減であることを基準にして，英語の句読法もいい加減になりがちですし，英語の句読法をしっかりと教えたり教わったりする機会はほぼないように思います．ただ，英語を母語する人が英語の句読法を正しく使えるのかといわれれば，それはまた別の話となり，私が観察する限りでは，英語を母語とする人でも英語の句読法を正しく使えている人はそんなにいないように感じます．
  • 最適化問題のいい復習になりました！ありがとうございました。
    --それはよかったです．分かりにくい部分もあったと思うので，ご自身でも復習をしてください．
  • 大学生の頃に受講したオペレーションズリサーチの講義で苦手な分野だったので、頑張りたいと思います。
    --次回の第4回は線形計画法を使っていきますので，よろしくお願いします．
  • 最大化問題のはずが，上界を最小化したいというように，いつのまにか最大と最小がすり替わっていて面白かった
    --これが双対問題の不思議なところですね．次回はこの「すり替わり」が最大流問題において何を意味するのか探究します．
  • 線形計画問題の一般化で、非負制約がついている変数とついていない変数を区別して、maximize c_1^Tx_1+c_2^Tx_2 や subject to A_{11}x_1+A_{12}x_2\le b_1 などと書いていましたが、区別せずに maximize c^Tx や subject to A_1x\le b_1 などと書いても線形計画問題を書き表せると思いました。また等式の制約と不等式の制約を分けて書いていましたが、等式は不等式を2つ使えば表せるので、等式の制約はいらないと思いました。非負制約がついている変数とついていない変数を区別したり、等式の制約と不等式の制約を分けて書いたりしているのは、相補性定理などのその後の話をしやすくするためでしょうか。
    --2つメリットがあると思っています．一つは最大流問題や最小費用流問題を考えるときに都合がよいことです．もう一つは主問題と双対問題が同じ形になることです．普通の教科書だと，自由変数がない (つまり，$n_2=0$) であることを仮定したり，等式制約がない (つまり，$m_2=0$) ことを仮定したりします．そして，自由変数があったり，等式制約がある場合でも，そのように仮定した場合に帰着できることを議論したりします．これはこれで良い面がありますが，そうすると，主問題と双対問題の見た目が変わってしまいます．一方で，等式制約と不等式制約の両方があり，自由変数と非負変数の両方がある形で線形計画問題を書くと (定義すると)，その双対問題でも等式制約と不等式制約の両方があり，自由変数と非負変数の両方があるようになります．その意味で，「きれい」ですし，対応が分かりやすくなると思います．もちろんデメリットはあって，それは式が煩雑になることです．
  • 双対問題が，主問題と同じ構造を持つように構成できることがありがたいのだろうなぁと思いました．
    --それがメリットの1つですね．(直前のコメントの返答の2つ目のメリットです．)
  • 学部の授業では，線形計画問題の制約は不等式制約で全て記述していた．よく使う制約である等式制約と非負制約を特別に扱うことで，アルゴリズムが効率良くなりそうと感じた．
    --線形計画問題を解くアルゴリズムの効率という観点では，いろいろな議論がありえます．教科書でよく紹介されている単体法では，すべての変数が非負変数であり，制約は等式しか使わない形の線形計画問題を扱います．その形の線形計画問題を標準形の線形計画問題と呼んだりするのですが，アルゴリズムを設計するときには，そのような都合のよい形に変形して考えることが多いような気がします．線形計画問題を考えるときの難しさは「不等式」にあります．これは不等式制約と非負制約のことを指します．これらが無ければ，ただの線形方程式なので，考えるのは割と簡単です．不等式をいかに扱うのか考えるのが線形計画法の要点だと思っています．
  • 「行」に対応する英単語である"Row"や，「列」に対応する英単語である"Column"は，行列の文脈以外で用いるときも，向きが指定されているものなんでしょうか．
    --英単語としてcolumnは縦長のものを指すときに使う語だと思います．例えば，新聞 (英字新聞) のコラムは，紙面を縦長に区切ったところに掲載されるから，そのように名がついたと聞いたことがあります．パルテノン宮殿のような建造物の柱もcolumnと呼ぶと思います．一方，rowは向きをあまり意識せずに，一列に並んでいる状態を表すような気がします．ただ，rowは動詞として「ボートを漕ぐ」という意味があったり，一列に並んでいる状態を表す言い回しの「in a row」は店やカウンターの前で行列を作っている様子を想起させるので，列の向きが横であることを思い浮かべやすいような気もします．
  • 横向きに並べたものにも「列」という言葉を使う（例えば，横書きで書いた日本語の文字列）のに，「列ベクトル」という用語は向きを指定するので，ややこしいと思いますね（縦向きに並べたもので「行」という言葉を使うものが，思い浮かばなかったのですが，何かありますかね）．「縦ベクトル」とか「横ベクトル」とかだったら間違えようがないのですが．
    --縦ベクトルや横ベクトルいう日本語の方が間違えようがないというのは同意します．会話ではそのような言い方をするときがあります．(そもそもベクトルについて会話するという状況が健全かどうかという疑問はありえますが，それは問わないこととします．) 五十音表では，縦を「行」，横を「段」という気がします．例えば，ア行，カ行，サ行，…で，ア段，イ段，ウ段，…になります．おそらく，横を行，縦を列と呼ぶことにしたのは恣意があったのだと思います．
  • ベクトルや行列の理論計算は任意の成分で計算する勢力の者ですが、今回のようにベクトルや行列自体の区別のための添え字が出てくる場合はそのままやった方が良さそうですね。ニューラルネットワークの異なる層の区別でも戸惑った記憶があります。
    --どのような記法を採用するか迷いました．$\boldsymbol{x}_1$ ではなくて $\boldsymbol{x}^1$ や $\boldsymbol{x}^{(1)}$ の使用も考えたのですが，転置記号と重なったときにみにくいのでやめました．
  • 学部時代に習いましたが正直忘れかけていたので線形計画法について復習させていただいて助かりました。
    --むかし勉強したことを覚えている必要はないと思っています．必要なときに調べて思い出せて，そして，自分で考えることができるということが重要だと思っています．その一助になれたならうれしいです．
  • 私は純粋に新しく理論を理解することが楽しいですが、新しく学んだ理論が目に見える問題に、言い換えると、小学生でも理解できる問題に、さらに言い換えると、その理論がなくても考えることができる問題に応用できると、とても嬉しくなります。前回の質問であった応用の紹介は非常に興味深いものでした。
    --ありがとうございます．応用について一言のべると，「いままでどのように応用されてきたか」を勉強することから始めて「これからどのように応用できそうか，できるか」ということまで考えられると素晴らしいと思います．いま皆さんが勉強していることを使うのは皆さん自身です．他の人がどう使おうと，どうでもよいのです．新しい使い方をぜひ開発していってください．そこから新しい研究や新しいビジネスが生まれてくるのだと思います．
  • 増加道法が浮かび上がってくることより，(3/2,0)が浮かび上がってくることの方が怖く感じました．
    --たしかに．実際(3/2, 0)は双対問題の最適解なので，それを持ってきているという後付けのからくりがあります．
  • 0以上だと思ったら0以下でした(=0)という論法は重要な一方、結果を知らず（考えず）に上から下へ読み進めるといつもトリッキーに感じます。昨日も久しぶりにε-δにやられました。
    --証明をする前に，どういう気持ちで証明をしていくのかお伝えするべきでした．すみません．
  • 材料費と売上の最適化は高校数学でよく出てくる問題ですが、まさか修士1年で（一般化された問題に）また取り組むとは、、いま思い返すと義務教育・高校教育は様々な研究分野のダイジェストという側面もあったと感じられます。
    --おそらく，いま勉強していることも，何かのダイジェストなのかもしれません．そう思ってみると，新たな発見があるかもしれませんね．
  • スライド番号が28/37となっているスライドの2枚目に関してですが，最後の行の一番左に表れる $\boldsymbol{y}_2$ から*が抜けてると思います．
    --ご指摘どおりです．ありがとうございます．スライドは修正しました．
  • 双対問題を求めるためにyをかける理由みたいのを知りたいです．
    --どれくらいの抽象度で説明するのがよいか，判断するのが難しいですが，関連しているのは「線形空間の双対性」です．線形空間には，双対空間と呼ばれるものが定義できます．線形空間とその双対空間の関係を調べるときには，内積 (pairing) が役立ちます．それに沿うと，yは双対空間の要素で，かけるのはもとの空間と双対空間の要素の内積をとっていることに対応します．
  • 「最適値の上界を求める(1)」のスライドのところで，なんで各制約式に$y_1 \geq 0$や$y_2 \geq 0$をかけるという発想に至ったのだろうなぁと思いました．その後の展開等を知っていれば納得はできるのですが…
    --直前の説明と別の説明をしますが，このyはラグランジュ乗数と関係しています．皆さんは，微分積分学で「ラグランジュの未定乗数法」というものを勉強したことがあると思います (内容は忘れていてもよいですが，勉強したことがあることは思い出してください)．そこでは，制約 (あるい拘束条件) に未定乗数と呼ばれる $\lambda$ を書けて，むにゃむにゃする，ということをやっていました．この $\lambda$ に対応するのが双対問題におけるyです．ただ，ラグランジュの未定乗数法のときは，拘束条件が等式で書かれているものを考えていました．そのため，$\lambda$ は実数であれば何でもよかったのですが，線形計画問題で不等式条件を考えるときは，未定乗数が非負でなくてはならないという条件がついてきます．これは実際にラグランジュの未定乗数法の原理をさかのぼると分かってきて，これが行き着く先には，最適化におけるKarush-Kuhn-Tucker条件という重要な性質があります．
  • 線形計画問題について、相補正定理は図に許容解の領域を書いたときに最適解が「角」のどれかになるということを示したことになりますか？
    --いろいろな側面があるので，分けて説明します．(1) 線形計画問題の許容領域に「角」があり，かつ，その線形計画問題に最適解が存在するとき，許容領域の「角」の中に最適解となるものが存在します．これは正しいです．少し仮定がついているのは細かいですが，割と重要です．(2) 相補性定理から上で述べた性質が導かれるかどうかということについては，ちゃんと考えたことがないのですが，おそらくできないと思います．というのは，「角」にない最適解が存在する可能性があり，そのような最適解であっても相補性定理にある条件 (相補性) を満たすからです．上で述べた性質を導くには，許容領域の構造を少し議論する必要があるような気がします．
  • 相補性定理ではxと(A11...-c1)の少なくともどちらかが0になるということを表していたと思いますが、問題によっては両方0になる場合もあるということでいいのでしょうか。
    --両方0になる場合もあります．2つコメントがあります．(1) 両方0になる典型例は，いわゆる「縮退」がある問題です．縮退の定義はしませんが，例えば，最適解が複数あるような問題を思い浮かべてもらうとよいです．(2) 実をいうと，最適解がある場合には，片方だけしか0にならない最適解が存在することが知られてます．これは強相補性 (strong complementarity) と呼ばれる性質で，線形計画問題に対するある種のアルゴリズムは強相補性を満たす最適解を見つけることを目指しています．
  • 相補性定理の証明を，$(A_{11} \boldsymbol{x}_1 + A_{12} \boldsymbol{x}_2)^{\mathrm{T}} \leq \boldsymbol{b}_1^{\mathrm{T}}$という式を用いて証明していたと思うのですが，行ベクトルに対する不等号関係が出てきてしまって，よく分からない状態です．結論は正しそうな（というか正しくないと色々困ってしまう）のですが…
    --ベクトルに対する不等式についてあまり説明しなかったのがよくありませんでした．少し補足します．列ベクトル $\boldsymbol{x}$ と $\boldsymbol{y}$ の次元が同じであるとします．ここで，$\boldsymbol{x} \geq \boldsymbol{0}$ と $\boldsymbol{y} \geq \boldsymbol{0}$ が成り立っていれば，$\boldsymbol{x}^{\mathrm{T}} \boldsymbol{y} \geq 0$ が成り立ちます (右辺の $0$ はスカラーであることに注意)．この性質を使って証明を行っています．
  • 線形計画法に関して以前勉強したときに，相補性定理がどう偉いのか，よく分かっていなかったのですが，今日の講義を通して，「解が最適であることの確認にも使えるし，最適解を見つけるヒントとしても使える」ところが偉いのだろうなぁと思いました．
    --はい，そのとおりですね．まとめていただきありがとうございます．この視点をあとの方の授業で使っていきます．
  • 相補性条件について飛んでいた論文に出てきたことがあり,調べても理解し難い内容だったが今回の講義で直感的なイメージがしやすかったので今後の理解に役立てたいと思います.
    --それはよかったです．より直感的なイメージをもつためには，主問題と双対問題を同じ図の中に描くイメージがあると助けになります．例えば，私が以前行った授業のスライドや松井知己先生の短い記事をご覧ください．
  • プログラミングの課題としてある条件の最大値を求める問題があったとき，問題文を読みかえて最小化の問題に置き換えるということを行う経験があった．線形計画問題においては，より論理的に最大化問題と最小化問題の書きかえをできることを知り，個人的に目から鱗の内容であった．
    --これは重要な視点で，双対性があるおかげで様々な問題を解きやすい形に変換できたり，効率のよいアルゴリズムが設計できるようになったりします．後者については，今後，最大流問題と最小費用流問題で体感することになります．
• 10/10 (2) 最大流問題：増加道法
  • 火曜日の12:15から研究室のゼミがあるため、このコメントを13時までに投稿できないときがあるかもしれないのですが、大丈夫でしょうか。今回のように授業時間内に書く時間をいただけると非常に助かります。
    --大丈夫かと言われると，あまり大丈夫ではないことになります．13時ちょうどに投稿を締め切るわけではないのですが，13時過ぎの不定時刻に締め切って，その後で，このコメント回答を作っています．できる限り授業の最後にコメントを投稿する時間は残しておきたいと思っていますが，うまくいかないかもしれないので，あらかじめご了承ください．また，皆さんのコメントは10:40頃からもう既に投稿できるようになっています．授業中や休憩時間中にコメントを入力していただいても全く問題ありませんので，その方法も試していただければ助かります．
  • 授業の録画は、授業日のおよそ何日後に公開されますか？
    --「できるだけ早く」が回答になりますが，状況は毎週変わるので，「何日後」と明確に定めることはできません．すみません．早い場合は当日になりますし，遅くても同じ週の木曜日までには公開するように努めます．ただ，保証はできません．
  • ドアの外から3匹くらい蚊が入ってきて、この時間だけで2箇所刺された気がします。痒いですね泣
    --西8号館の辺りは蚊が多いような気がします．西4号館はそういう感じがしないのですが．
  • 生きていくのに必要な養分(生徒からのコメント)，後期しか摂取することが出来ないと思うのですが，前期は大丈夫そうですか？
    --実を言えば大丈夫ではありません．;-) そのため，後学期でたくさん養分を得て，前学期はそれを放出していることになります．1年を通してバランスを取っているわけです．
  • dopalのdは何の略ですか？
    --discreteの頭文字です．
  • 講義内で，v''やv'''のことを"v two prime"や"v three prime"と呼んでいましたが，"v double prime"や"v triple prime"と呼ぶのはどうでしょうか．
    --よく知らなかった，というか，あまり認識していなかったのですが，double primeやtriple primeと読むのが普通のようです．これからはそう読みます．ご指摘ありがとうございました．
  • 分かりやすかったです。
    --ありがとうございます．分からないところがありましたら，ぜひ質問してください．
  • 10/24
    --これは次のコメントの書き損じだと思ったので，次のコメントに回答します．
  • 10/24に大学院連携科目の先行履修受講届出用紙に署名を貰いたいのですが大丈夫でしょうか
    --可能です．授業の前か後に申し出てください．
  • この場をお借りして質問させていただきます。大学院連携科目の履修に関して、受講届に岡本先生の署名が必要だということに今気が付いたのですが、先生の研究室に伺い、署名をいただくことはできますでしょうか。
    --前の方と同じ時間帯 (10月24日の授業前か授業後) はいかがでしょうか．他の時間帯でもよいですが，私はあまり自分の部屋にいないのでご注意ください．
  • 卒研中間発表で質問していただきありがとうございました。なぜその提案手法は今まで出てこなかったのか、というのを考えることの大切さを再認識できた気がします。先生はかなり多くの学生に質問しているように思えましたが、質問を見つけるコツとかってあるんですか？
    --コツは興味を広く持つことだと思います．そもそも興味がなければ，質問できませんし，質問しようと思えません．私が話す側にいるとすると，質問をいただけないことは興味を持ってもらえなかったということなので，話としては失敗だと見なしています．逆に，私が聞く側にいるとき，質問をしないとすると，そのときは大抵興味が湧かなかったときです．(質問する時間が十分になくて，質問できない，という場合もあります．) 私にとって質問することは，自分がもっと分かりたいとかもっと知りたいと思うことを聞くだけの行為であって，誰かを貶めようとか自分の意見を誇示しようとか，そんな思いは毛頭ありません．その点は誤解されることがあり，困るときもあります．
  • 1964年10月10日、第18回オリンピック競技大会（東京オリンピック）の開会式が行われた。1966年に10月10日が「体育の日」として祝日になったが、2000年にハッピーマンデー制度が導入され、「体育の日」は10月第2月曜日に変更された。「体育の日」は、2020年以降「スポーツの日」と名称が変更された。
    --私にとって「10月10日は体育の日」という印象が強いです．いまだに「スポーツの日」という名称に慣れませんし，ハッピーマンデーにも慣れません．
  • 復習に動画が使えるのでありがたいと思いました。
    --はい，ぜひ活かしてください．
  • 例をたくさん提示していただいたので、非常にわかりやすかったです。
    --例を重視しています．例で分かれば，ほぼ分かると思っています．一方で，例と呼んでいるものも段々と抽象的になっていくと思います．例を通して抽象的な考え方ができるようになったり，抽象的に考えたものを言葉で表現できるようになることは，皆さんが身につけるべき技能だと思っています．
  • 証明の際に図や具体例があることによって理解がしやすいです。
    --ありがとうございます．教科書や論文を読むと，この授業ほど図や具体例がないことに気づくと思います．皆さんは，自分の研究分野でも図や具体例を作りながら理解できるようにしてみてください．
  • 増加道の説明分かりやすかったです。
    --ぜひ，自分で例を作って，アルゴリズムの動作をその例で追ってみてください．
  • 前回は理解できたのですが今回は途中から追いつけなくなってしまったので復習に特に集中しようと思います
    --はい，ぜひ復習してください．分からないところは直接聞いていただいてもまったく問題ありません．
  • 情報量が多くて、復習動画を見ないといけないという感じでした。
    --今回の内容はいきなりクライマックスですからね．ぜひ動画を見て復習してください．
  • 11ページの流入和、流出和は13ではなく14だと思います。あと、最近世界がロシアとかパレスチナとか騒がしくて少し不安です。
    --ありがとうございます．ご指摘のとおりです．修正しました．
  • 講義内では，vに「入る」弧全体の集合を"δ-(v)"を書くことにしていますが，個人的には"-"という記号は，「出る」という言葉と結びつけたくなりますね． 伝統的に用いられている記法らしいので，今更変えるわけにもいかないですが，最初に「vを終点とする弧全体の集合」を扱おうと思った人が，$A^{\mathrm{in}}(v)$のような記号で定義してくれたら，個人的には分かりやすかったのになーと思います．
    --「in」や「out」という記法を使う人もいます．その意味ではこの講義は (伝統的ではあるものの) 分かりにくい記法を採用してしまったことになります．その点はすみません．
  • 証明がいくつか出てきましたが、途中で記号ややっていることについての説明があったため分かりやすかったです。
    --証明をお伝えするのは難しいのですが，できる限り，例と関連付けて，抽象的に見える式を具体的にイメージしやすいようにしているつもりではいます．難しいところはぜひ質問して聞いてください．
  • 「補助ネットワーク・増加道」など定義の説明の前に図によるイメージの解説がとても分かりやすかった．新たな定義が多かったものの，最大流問題の最適化条件の説明時に定義や性質を再利用したため，1講義の中で各定義・性質の利用方法の理解につながった．
    --補助ネットワークは今後も使うので，またそのときに復習しながら考えていきます．
  • 線形計画法とどう繋がるのかが楽しみです．
    --これは次回以降の話になりますね．お楽しみに．
  • 今回の内容で、グラフの縮約を考えればより単純なグラフで議論できるのではないかと感じました。
    --実をいうと，そのような考え方に従って数学的帰納法を用いて証明するという手法があります．ただ，そこからアルゴリズムが自然に湧き上がってくるかというと，そういうものでもない気がするので，この授業では採用していません．
  • 最適解条件の証明の最後の部分が少し速かった．おもしろかったです．
    --最適「性」条件ですね．確かに最後の部分は速かった気がします．まずは性質自体の威力を感じて，証明はゆっくりと理解してください．
  • 1回目の講義でおっしゃられていた問題からアルゴリズムを導き出すまでの道筋の理解を深めることができました．
    --こんな感じのことを最小費用流問題でもやることになります．それはこの講義の後半の話題になります．
  • 本当に自然に湧き上がってきて面白かった。たくさん「気持ち」を説明していただいたのが助かりました。止まらないアルゴリズムはアルゴリズムとは言えない気がしてるので、工夫して止まるようにできるのかな？と思いました
    --面白さを感じていただけてよかったです．「止まらないアルゴリズムはアルゴリズムとは言えない」というのはそのとおりだと思います．工夫については第5回の内容になる予定です．
  • 増加道法に関して、s-t流fの初期値の良い選び方が考案されていたりするのか気になりました。 (ここでいう「良い選び方」というのは、停止性の問題(スライドp.37)に陥りにくいという意味です)
    --これについて，私はよく知りません．もしかしたらよい選び方があるかもしれません．ただ，ある性質を持つs-t流を見つけるというのは，それだけで割と非自明な問題になる気がします．そのため，初期解の選び方を工夫するのではなく，増加道の選び方を工夫するという方向で世の中の研究は進んだのだと思います．
  • 増加道法が"自然と"湧き上がることが怖くは思えませんでしたが，嬉しいとは思いました．
    --「怖い」は言い過ぎだったと反省しています．(-_-;
  • 適切なペースで進み、トピックの深さもちょうど良かったと思います。
    --了解しました．ありがとうございます．今回の内容が前半の核となりますので，よく理解しておいてください．
  • s-tカットとs-t流の値のところがガウスの法則みたいで面白かったです。
    --実際，ガウスの法則 (や関連するベクトル解析の法則・定理) と関係があります．ある意味で，それらを (空間的に) 離散化したものがs-t流やs-tカットの考え方につながっています．
  • 「カット」という名前から辺（弧）を使って表現すると思っていたのですが、頂点を使って表現していて思ってたのと違う感じがしました。
    --「カット」という用語はいろいろな意味で使われて，また，場合によって異なる定義が採用されることもあります．今回の講義では (都合がよいので) 頂点集合として定義しました．ただ，実際は集合から出ていく弧であったり，集合に入ってくる弧に着目して議論をしているので，その点はややこしいと私も思います．
  • s-tカットのSの定義では、「S⊆Vでs∈Sとt∉Sを満たすもの」とあるのですが、スライド26/70の有向グラフでS={s, v2}のような選び方をしても(つまり頂点が飛び地になっていても)、SはGのs-tカットと言えるのでしょうか？
    --はい，いえます．今回の授業で紹介したs-tカットの性質において「飛び地になっていない」という条件はまったく使っていません．
  • 最大流は一つだけユニークに存在するという理解でいいのでしょうか？それとも最大流が二つ以上存在することはあるのでしょうか？
    --最大s-t流が2つ以上存在する例は存在します．むしろ，無限に存在する例も存在します．次のようなものを考えてもらうと分かると思います．
    
    ここで，$x$ は0以上1以下の任意の実数です．その範囲のどの $x$ に対しても，ここに書かれているものは最大s-t流です．つまり，最大s-t流は無限に存在する可能性があります．
  • 二部グラフの最大マッチング問題においても、増加道アルゴリズムがあったことを思い出しました。
    --二部グラフの最大マッチング問題は最大流問題と見なせることが知られています．例えばこれをご覧ください．
  • J8実験の前にこの説明があれば、よくわからず実装するなんてことはなかったんだろうな、と思いました。とてもわかりやすかったです。
    --実は，J8実験のテキスト (の始めのバージョン) は私が作ったのですが，一応，読めばすべてわかるようにはなっているはずです．もしかしたら，いま見返すと，当時分からなかったことも分かるようになっているかもしれません．
  • 応用例を紹介していただければと思います
    --何を持って応用と呼ぶのか，人によって感じ方は違うのですが，まず，この授業の中で応用例を紹介するということはありません．(ただ，このような質問や要望はあってしかるべきで，その点ではありがたく思います．) 最大流問題の応用については，例えば，ここやここを見てみてください．
  • スライドのグラフが綺麗で見やすいです。普段スライドのグラフは何で作成されてますか、またおすすめの作成ツールはありますか。
    --私はipeを使ってスライド自体を作成しています．スライドの中の図もこれで作っています．
• 10/3 (1) 最大流と最小費用流：定義
  • コメントをありがとうございました．以下のように掲載されます．
  • 半年間よろしくお願いします。
    --こちらこそよろしくお願いします．
  • わかりやすい授業でした。ありがとうございます。
    --こちらこそありがとうございます．わからないところがでてきたら，ぜひ質問をしてください．
  • これから約半年間よろしくお願いします。
    --よろしくお願いします．
  • 授業についていけるか不安ですが頑張ります
    --わからないところがありましたら，ぜひ質問をしてください．よろしくお願いします．
  • これからよろしくお願いします．
    --こちらこそよろしくお願いします．
  • 改めて復習しようと思います。
    --はい，動画もありますので，ぜひ活かしてください．
  • 1990年の10月3日、東西ドイツが45年ぶりに統一され、ドイツ連邦共和国が誕生した。
    --私にはそのときの記憶があります (当時中学生)．その頃，ソビエト連邦が崩壊して，冷戦が終わっていく瞬間をテレビ越しに見ていた気がします．皆さんにとってはただの歴史上の出来事に思えることでも，私には割と鮮明です．おそらくこの「コロナ禍」も十数年後にはただの歴史上の出来事になるでしょう．そのとき，皆さんは歴史の一部分になることに気づくと思います．
  • Zoomで録画を撮る形式は復習がしやすく個人的にはとてもありがたいです．
    --いろいろと試行錯誤しながらやっていますので，アドバイスなどがありましたらお聞かせください．
  • 初回だからか，しっかりと話を聞くことができた．内容も理解出来たと思う．
    --それはよかったです．今後どんどん難しくなっていきますので，しっかりと理解できるように勉強を進めてください．
  • 図があって理解がしやすくてよかったです。
    --図には力をいれています．むしろ，図にしか力をいれていないといっても過言ではないかもしれません．冗談はおいておいて，図を通して理解することは重要視しています．皆さんも，自分の研究分野の勉強をするときには，自分なりの図を描いて理解するようにしてみてください．
  • オンラインでも声聞き取りやすかったです
    --それはよかったです．トラブルがありましたら，リアルタイムでもチャットなどでお知らせください．対処できることにはすぐに対処します．ただ，その場で解決できないこともあると思うので，その点はご了承ください．授業中にもお話をしたとおり，オンラインは補助的に使っているとご理解ください．教室で授業を受けることを基本としています．よろしくお願いします．
  • 授業の途中から先生の声がスピーカーから返ってくるようになっいてましたが、仕様でしょうか。先生の声は十分大きいので必要ないと思います。
    --ご指摘ありがとうございます．仕様ではないはずで，途中から設定等を変えたわけではないので，よく分かりません．録画を見ても声が返ってくるような印象は受けなかったので，少し様子を見させていただいて，また問題が続くようでしたら原因を探ってみます．
  • 基礎や定義からしっかり教えてくださるので、とても分かりやすかったです。
    --定義を理解することが，すべてを理解するための基礎になるので，今回はその点に焦点をあてました．
  • 研究で整数計画法を使用しているので、活用の幅が知れそうで楽しみです。
    --はい，ぜひ活用できるかどうか考えてみてください．
  • 説明がすごく丁寧です！
    --丁寧かどうか自分ではあまり判断できないのですが，1コマの時間に収まる程度の濃さ・薄さで説明はしています．今後，場合によっては1コマで収まらない内容を「補足動画」のような形でご提供することもあると思います．
  • 扱う題材がネットワークフローで研究に役立ちそうで嬉しいです
    --ぜひ役立ててください．よろしくお願いします．
  • 武蔵境通りと西9号館の間にある大学敷地内の道が，工事でまた通行できなくなってて悲しいです．調布駅から西4号館に行くときに，ほんの少し遠回りするだけと言えば，それだけなのですが．
    --工事は致し方ないので許してください．
  • 最大流問題や最小費用流問題の問題設定は面白いと思った。これらをいかにして解くか気になり、次回の内容が楽しみになった。
    --最大流問題や最小費用流問題はネットワークフローの問題設定としては基本的なもので，既に1950年代から研究されていたものです．現在では，その変種もたくさん研究されているので，もし興味があれば調べてみてください．
  • 「〜〜がしたい」という気持ちが知れて楽しい授業です
    --直感的な理解と形式的な理解のバランスをとるのはなかなか難しく，どちらも大切だと思うので，どちらもお伝えしようと思っています．「○○がしたい」という気持ちは直感的な理解につながるのですが，その気持ちは大事にしていきたいと思っていますし，実際，「どうしてこのようなアルゴリズムを考えるのか・考えつくのか」という気持ちは私のできる範囲で皆さんと共有したいと思います．
  • 自然とアルゴリズムが湧き上がるという体験を楽しみにしております．
    --次回，既に体験することになります．お楽しみに．
  • アルゴリズムが自然と湧いてくるのが今から楽しみです。
    --はい，湧き上げます．(^^)
  • 講義室で見ていると講義資料にメモする文字が細くてよく見えない時があります。もっと太くするか大きく書いていただけると幸いです。
    --ありがとうございます．次回は太くしてみます．
  • 掛け算が入るとかなり面倒になりそうだと思いました
    --そのとおりですね．あまりその視点を持っていなかったので新しい気づきになりました．最大流問題では，流れているものを足したり引いたりしかしていないのに，最小費用流問題では費用を掛けたりしています．これによって最小費用流問題を考えるのが最大流問題より難しくなっているという側面はあると思います．
  • 久しぶりに扱ったので非常にわかりやすくしていただきありがとうございました．例に示すfの流れをグラフ上で→などで可視化していただけるとより理解できたと感じました．
    --ご提案ありがとうございます．ただ，絵が煩雑になってしまう気がする (現状でもかなり煩雑だと思っています) ので，「fの流れは弧の向きと同じ」だと理解して，弧にもとから付いている向きを参照するようにしてください．
  • 今までは弧の矢印(の三角)を終点側に描くことが多かったのですが、スライドのように弧の中央に描いた方が良いのでしょうか。またグラフ内にサイクルがあった場合、今回扱った内容で何か特殊な現象が起こったりするのかが気になりました。
    --2つのコメントに対して分けてお答えします．(1) 「矢印の三角をどこに描くのがよいのか」というのは私が長年頭を悩ませている問題で，いろんな研究者に話を聞いたりしました．その結果として，他の研究者が研究を行って論文を出版しています．ただ，決定的な解決策はまだなく，私の中では未解決です．一つ言えることは，「終点側に描く必要はない」ということです．
  • 最大流問題などのアルゴリズムにおいて入力として弧容量関数uの必要性が分からなかった．自身の認識としては，各経路(弧)に流せる情報量(f)を任意に設定できるときの最大の情報流量を求めるためには，各経路(弧)に流せる容量の限界が必要であるという認識である．
    --はい，その認識で正しいと思います．限界がないといくらでも流せてしまうので最大流は存在しないことになってしまいます．最大流が存在するためにはuが必要になります．数学的には「許容領域のコンパクト性」ということになりますが，これに関わる話は後の方で出てくる予定です．(コンパクト性という用語はでてきませんが．)
  • 流についてsから出る流量からsに入る流量を引いていましたが，sに入る流量が0ではない場合というのは現実的にはどのような状況が考えられますか
    --例えば，ネットワークが輪 (リング) になっていて，ぐるぐる回れる状況を考えます．「流れるプール」みたいなのを想像してもらえばいいかもしれません．そうすると，どの場所においても (ネットワークでいえばどの頂点においても) 出ていく流量と入る流量が同じになっています．それはsにおいても同じなので，sに入る流量は0ではないことになります．
  • ありがとうございました。val(f)の定義でどうしてδ-(s)を引くのかが理解しづらかったです。
    --sから実質的に出て行っている流量を測りたいからです．授業では水の流れのイメージをお伝えしましたが，そうではなくて，例えば，ネットワークの頂点が「人」や「店」を表していて，流が「金銭のやりとり」を表すと考えます．出ていく流れは支払い，入る流れは受け取りを表すと見なします．このとき，例えば，3000円出ていき，1000円入ってくるならば，実質的に出ている量は2000円になる，と考えるわけです．
  • 今年からUECに来ました。基盤理工学専攻ですが、雑談も含めて面白い内容だったので履修しようと思いました。
    --ありがとうございます．雑談にはあまり力をいれていないので，その点には期待しないでください ;-)．
  • 頂点や弧の多くある別名に使い分けはありますか
    --特に使い分けはなく，分野や場面によって使い分けられるという印象を持っています．例えば，「頂点」はグラフ理論で用いられる傾向が強く「節点」はコンピュータサイエンスで使われる傾向が強いように感じます．
  • 弧という用語に始点から終点をつなぐというように向きがある概念なのが不思議に思えました
    --たしかにそうですね．円の一部分のことを「弧」と呼びますが，これには向きがあるとは考えないと思います．グラフにおける弧が向きを持っているのは，「弧」という語の使い方として特殊なのかもしれません．
  • 質問：スライド35ページにおいて、b=5.1などとすれば、「ない」と出力されるわけですが（始点の容量を超えているため）具体的にどの値から「ない」と出力されるか解析するにはどうすればよいのでしょうか。（今後の授業で扱うのでしょうか） 要望：予習を行ってから授業を受けたいと考えているため、できるだけ早めにアップロードしていただけますと幸いです。
    --分けて回答します．質問について．bが最大流の値を超えると「ない」になり，超えない範囲では必ず最小費用流が存在します．要望について．あまり早めではないですが，前日の18:00までにはアップロードするように努力します．もっと早くできる場合にはそうします．ただ，早くアップロードすることよりも完成度を重視するため，18:00までにあげられないこともあるかもしれません．その点はあらかじめご了承ください．
  • 訓読みにセンスがないと思う理由が気になります
    --数学の用語は「音読み」が基本で伝統だと私が思っているからです (そうだと信じています)．例えば「数」は「すう」と読みます．「数」を「すう」と読めない人は圧倒的にいます．「負の数」は「ふのすう」です．そのため，読みが分からないときは音読みをすれば大抵あっています．また，訓読みの問題点は熟語にしにくいことです．伝統的な音読みの用語と新しく編み出した訓読みの用語で熟語を作ると，すぐにいわゆる「重箱読み」や「湯桶読み」が発生します．あまりよいとは思えません．
  • グラフ理論は個人的に好きな範囲なので、楽しく受講することができました。スライドも見やすかったです
    --ありがとうございます．一つ注意があります．この授業はグラフ理論の授業ではありませんし，グラフ理論を扱いません．グラフを扱えばグラフ理論を扱うことになるわけではありませんので，その点をご注意ください．グラフ理論はこの授業の扱うものと何か別のところにあります．世の中には何でも「理論」「論」「学」をつけて学問をやってる気になる人がいて，本当によくないと思っています．皆さんも，世の中にはびこる「理論」が本当に理論なのかどうか注意して対応するようにしてください．
  • 先生はよく「離散最適化を専門としているつもりはない」とおっしゃっていますが，何を専門としているつもりなのでしょうか．
    --ひとことでいえば「専門はない」です．そもそも，「専門は○○」というのは何か区別するためのラベルであって，そういうもので多様な考え方を一括りにするべきではないと思っています．多様性の時代です．私は私自身が興味あることを勉強し，研究し，皆さんにお伝えするということをしていますし，これからもそうしていたいと思っています．ただ，そんなことを言っていると他の人とコミュニケーションがとれないので，他の人から聞かれるときには何かしらのラベルを自分につけるようにしています．電通大の中では(あまり本意ではありませんが)「離散最適化」を専門とするというロールプレイをしています．国際的には「計算幾何学」の専門家だと認識されることが多いような気がするので，そのような場ではそういうロールプレイをしています．他にも場や状況によって「アルゴリズム」とか「計算理論」とか「離散数学」とか「オペレーションズ・リサーチ」とか，そういうものの専門家であるような顔をしています．もちろん「最適化」とか「離散最適化」を専門とするような顔をすることもあります．
  • コロナ禍の関係で，先生が担当される講義を対面で受講することは初めての経験でしたが，Webサイトの「実施形態」の説明にも書いてある「ライブ感」が感じられてとても良かったです．
    --それはよかったです．コロナ禍に入り，遠隔授業が普通になったとき，対面授業の意味を私なりに考えました．これはアイドルのコンサートと同じなのではないかと．その場のライブ感を味わえるような授業をすることが対面授業には求められると．ライブ感の強さは，対面授業が一番強く，その次がリアルタイム遠隔授業，そしてその次がアーカイブ (オンデマンド授業)．これはアイドルのコンサートで言えば，ライブハウス，ライブ配信，アーカイブ (あるいはDVDのようなもの) にそれぞれ対応するのではないかと．私自身はライブ感がある対面授業を行うことでしか，対面授業の価値を見出せませんし，皆さんもそのようなつもりでよいと思います．私の授業に対面で参加する価値がないという判断を皆さんがすれば，もちろん遠隔やオンデマンドで参加するという形でまったく構いません．そう判断してしまうのであれば，それは私が悪いだけなので．もう1つの観点を提示してみます．この授業はYouTubeにあがります．その意味で，皆さんが「授業料を払ったうえで」この授業を受講する「特典」は大きく分けて2つあり，1つは教室で授業に参加できること，もう1つは単位を得られる (可能性がある) ことです．教室で授業に参加する特典 (あるいは権利) を活かすかどうかは皆さんの判断になります．

• 2回のレポート課題により評価を行う予定でいます．
• レポート課題1
• レポート課題2
  • レポート作成のために，次の図を用いてもよい．
    PDF | PNG
    

• こちらをご覧ください

• 10/3 (1) 最大流と最小費用流：定義
• 10/10 (2) 最大流問題：増加道法
• 10/17 休み (体育祭)
• 10/24 (3) 線形計画法の復習
• 10/31 (4) 最大流問題：線形計画問題として
• 11/7 (5) 最大流問題：Edmonds-Karpのアルゴリズム
• 11/14 (6) 最大流問題：容量スケーリング法
• 11/21 (7) Push-Relabel法 (概要)
• 11/28 (8) Push-Relabel法 (計算量評価)
• 12/5 休み (出張のため)
• 12/12 (9) 最小費用流問題：線形計画問題として
• 12/19 (10) 最小費用流問題：負閉路消去法
• 12/26 (11) 最小費用流問題：正カット消去法 (オンデマンドの予定)
• 1/2 休み (冬期休業)
• 1/9 (12) 最小費用流問題：逐次最短路法
• 1/16 (13) 最小費用流問題：容量スケーリング法
• 1/23 (14) 最小費用流問題：費用スケーリング法
• 1/30 休み (金曜日の授業を行う日)

• David P. Williamson, Network Flow Algorithms, 2019, Cambridge University Press.
• Bernhard Korte and Jens Vygen, Combinatorial Optimization: Theory and Algorithms Sixth Edition, 2018, Springer.
• 繁野麻衣子，『ネットワーク最適化とアルゴリズム』，2010，朝倉書店．
• 室田一雄，塩浦昭義，『離散凸解析と最適化アルゴリズム』，2013，朝倉書店．
• 茨木俊秀，永持仁，石井利昌，『グラフ理論』，2010，朝倉書店．

• 離散最適化基礎論 (2022年度) テーマ：整数計画法
• 離散最適化基礎論 (2021年度) テーマ：グラフの準同型
• 離散最適化基礎論 (2020年度) テーマ：マッチング
• 離散最適化基礎論 (2019年度) テーマ：離散最適化における計算困難性
• 離散最適化基礎論 (2018年度) テーマ：理想グラフに対する組合せ最適化
• 離散最適化基礎論 (2017年度) テーマ：幾何的被覆問題
• 離散最適化基礎論 (2016年度) テーマ：グラフの木分解
• 離散最適化基礎論 (2015年度) テーマ：組合せ最適化におけるマトロイドの役割
• 離散最適化基礎論 (2014年度) テーマ：組合せ最適化における線形計画法の利用
• 離散最適化基礎論 (2013年度) テーマ：局所探索法の理論的側面
• 離散最適化基礎論 (2012年度) テーマ：ゲーム理論における離散構造とアルゴリズム