離散最適化基礎論

岡本 吉央

テーマ：高速指数時間アルゴリズム

注意：テーマは毎年変わります

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

実施形態

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

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

講義資料

• 10/7 (1) 高速指数時間アルゴリズムの考え方
  • スライド (10/8更新)
  • 講義動画

• 10/7 (1) 高速指数時間アルゴリズムの考え方
  • コメントをありがとうございました．以下のように掲載されます．
  • よろしくお願い致します．
    --こちらこそよろしくお願い致します．
  • 今後ともよろしくお願いします
    --こちらこそよろしくお願いします．
  • 半年の間よろしくお願いします。
    --こちらこそよろしくお願いします．
  • お疲れ様です 🙇
    --こちらこそお疲れ様です．
  • 良い
    --ありがとうございます！
  • すごく愉快な先生だなと思いました。スライドもわかりやすく次の授業が楽しみです。
    --私が愉快かどうか，私自身では分からないのですが，言い回しにクセがあることは自覚しています．次回もお楽しみに．
  • 非常に面白かったです
    --面白く感じていただけて，よかったです．:-)
  • 面白そうなので受講しようと思います。よろしくお願いします。
    --はい，よろしくお願いします．
  • 内容が分かりやすくて、興味深かったです。
    --内容はわかりやすくなるように努めていますが，分からなくなったら，ぜひ質問してください．
  • 数理最適化に関する研究を行なっているので、その知見をこの講義で得たいと考えています。4ヶ月間よろしくお願いします。
    --はい，よろしくお願いします．
  • この講義を落とすと留年が決まります。頑張ります。
    --評価の方法は授業内で述べたとおりです．しっかりと復習するようにしてください．
  • 研究内容に必要なそうな内容でもあるし、授業の内容も魅力的で、面白そうだが、難しそうです。でもわかりやすいです。
    --あとでレポート課題に取り組むとき，それまでの内容があまり分かっていなかったかな，という気持ちになるかもしれません．でも，それで構わないと思います．一度聞いたことをその場ですべて理解できるとは限りませんし，むしろ，理解できる方がまれです．あとから思い出せるように復習していくことが大事かな，と思います．
  • 先生少し長く休憩を取っても大丈夫です。
    --お気遣いいただきありがとうございます．
  • 金輪際って表現が自然に口から出る人を先生以外に会った記憶がないなと（私の交友が狭いだけ…？）．
    --私はいろんな表現が自然に口から出ます ;-)
  • 十把一絡げ → ざっくりまとめると とかどうですか．
    --提案ありがとうございます．「ざっくり」は「おおまかに」のような意味だと思うので，少し思っている意図とは違うかもしれません．「すべてをひとまとめにして」とかの方が私の意図としては近かったかもしれません．
  • 昨日横浜のコクトーバーフェストに行ってきました．二日酔いですが頑張って来ました．
    --二日酔いにはご注意ください ;-)
  • 情報・ネットワーク工学専攻なので、情報系の授業でついていけるか不安であったが、スライドのアルゴリズムの説明や数学的定義など詳しく解説されていて非常に分かりやすくて面白かった。
    --定義すべきものは定義していく予定ですが，わからなかったり，知らないものがあれば，なんでも質問してください．知らないことは恥ずかしいことではありませんので，そのつもりで臨んでください．
  • シラバスでも「データ構造やアルゴリズムの授業は，多項式時間でできることに対して多くの時間を割きすぎています」って書いてありましたが，確かに，指数時間アルゴリズムに真面目に向き合ったことって多項式時間アルゴリズムほどないなぁと思ったので，とても楽しみです．
    --シラバスに書いたそれですが，「教え方が古い」ことが一番の原因だと思っています．多項式時間でできることについてしっかりと勉強することは重要ですが，それだけに偏ると，アルゴリズムやプログラミングで解決できる問題の幅はとても狭くなります．しかも，基礎的なデータ構造やアルゴリズムは最近の高級プログラミング言語では既に実装されています．そのため，それらを学ぶ意義は「しくみを理解する」という側面が強く，「新しいものをつくる」という側面が弱くなっているように感じます．指数時間でできることについても目を向けていくべきだと思います．
  • 今までやってきたようなアルゴリズムやオーダー法をちゃんと理解した。しらみつぶしのところの並べ方は何かの基準があるのか気になった。
    --並べ方ですが，10ビットの列を0000000000から1111111111まで順にインクリメントして作り，各列において10個のビットを10個の頂点の1つ1つに対応させています．それを左上から右に進めて，右端まで来たら下の段の左端に移る，ということを繰り返して，グラフを作っています．1であるビットが赤，0であるビットが黒で表されています．
  • 今日の授業では高速指数時間アルゴリズムの考え方について学べたが、個人的にとても興味深い内容だった。ただし、忘れている内容が多いので復習したいと感じた。
    --はい，ぜひ復習をしておいてください．
  • O(c^n)のcを小さくするということは今まであまり触れてこなかったので楽しみです
    --そうですね．この授業を通して皆さんには「しらみつぶしでしか解けない」というような主張がどれほど正しくないのかということを味わっていただきたいと思います．
  • 指数のオーダーを改善することのインパクトを甘く見ていたので、その凄さを体感できてよかった
    --それはよかったです．評価を低くされがちなのですが，とても威力があります．
  • 段階的に図で表されたスライドや手書きでの説明が、とてもわかりやすく、内容がスルスル入ってきたため、集合の基礎知識を振り返ることができました。
    --それはよかったです．ただ，スルスル入ってきているときは，本当に理解できているか要注意ですので，改めて考えてみて，理解を確認してください．
  • 最大独立集合を求める問題のアルゴリズムで、頂点を選ぶ順番が関係ないことが直感的にはわからなかったが、直前のしらみつぶしからの流れで見ると理解できた。目標を明示してくれるのがありがたい。
    --目標を先に述べることを私は心がけています．皆さんもぜひ．
  • 最大独立集合問題が簡単に解けて驚いた
    --ぜひプログラムを書いて，実際に解いてみてください．どんな風に解けているのか，より深く分かるようになると思います．
  • グラフ理論における開近傍や閉近傍って，普通の位相空間論とかで使う開集合や閉集合と何か関係があったりしますか．
    --関係があってほしいのですが，関係がないというか，むしろ関係がないために混乱します．位相空間論においては開集合がメインの対象であるので，たとえば，単に「近傍」といえばそれは開集合になります．しかし，これはグラフに対する開近傍とは違うものです．もう少し具体的に言います．位相空間論において「xの近傍」のような言い方をするとき，それはxを含むような，ある集合を指します．一方で，グラフ理論において「xの開近傍」と言ったら，それはxを含みません．このあたりのグラフ理論の用語はややこしく，非常に分かりにくいように私自身も感じます．一方で，グラフ理論にはグラフ理論の伝統があるので，その伝統に従った用語をこの授業でも使うことにしていて，そのため分かりにくくなることはあるかもしれません．
  • 異なる専攻の学生ですが、受講させていただきます。自分の研究テーマと関連があり、最適化問題にも興味があるからです。まず、最大独立集合問題を考える際に葉の数が大幅に減ったのに驚きました。独立集合が確定した時点で場合分けをやめることで、計算量を減らすことがポイントだと解釈しました。
    --異なる専攻の皆さんも歓迎しています．ありがとうございます．最後に書かれたポイントは工夫2の方ですね．工夫1の方も実は重要です．
  • 講義で扱ったアルゴリズムから，講義で扱ったグラフに対して最大独立集合を見つけられることはわかったが，本当にこのアルゴリズムで，どのような入力に対しても最大独立集合を出力させられるのか不安が残ります．「しらみつぶし」による安心感から抜け出せない自分がいると感じています．このような，腑に落ちない感覚を払拭するためにも，自らプログラミングをすることが大切なのだと思いました．
    --そうですね．実感をするためには，プログラムを書いて動かしてみるのがよいかもしれません．
  • 1024通りしらみつぶしの図がすべてグラフだと知った時にぎょっとしました．そのあとの木を使った考え方が際立って見えてとてもよかったです
    --図を作るのに，かなり力をいれています ;-)
  • 巡回セールスマン問題などは名前だけは聞いたことがあったため、改めてどのようなものか学ぶことができてよかった。今後も授業を通して、引き続き学びを深めていきたい。
    --巡回セールスマン問題はあとのほうでまた出てきますので，そのときにまた思い出してください．
  • 多項式時間でないアルゴリズムについて考える機会があまりなかったのでこの講義を機に学習したいと思った. 巡回セールスマン問題について, 頂点の中で三平方の定理が成り立つのであれば頂点を結んだ線が交差しないように選べば早くなりそうだと思った.
    --ユークリッド平面上では，そのような考え方を進めていくことで，$2^{O(\sqrt{n})}$ 時間アルゴリズムが提案されています．これは $2^n$ よりも圧倒的に速いです．
  • 色々な人が考えた結果であるとは思うのですが、最初に計算量を小さく出来ることに気付いた人はどういう考えを基に考えていたのか気になりました。
    --最初のことはよく知らないのですが (調べてもよく分からないのですが)，1960年代や70年代には何人かの研究者が既に気にしていたようです．例えば，最大独立集合問題に対するTarjanとTrojanowskiの論文の出版は1977年です．
  • 確かにんが非常に大きい時、N^3などの多項式は2^Nといった指数関数と比較して誤差みたいなものなので、O*記法を使用することは理解できる。でも、O(n^3)とO*(1)が同一かというと、元のオーダー記法の方に指数関数がないので、指数関数の存在を意識したこの記法は一見不適切であるように思える。
    --ご指摘のとおりだと思います．普通は，O(f(n)p(n))と書くとき，f(n)が指数関数 (あるいはオーダーが多項式より大きな関数) であるときにO*(f(n))と書きます．ただ，授業で紹介した定義では，f(n)がそうでなくてもO*(f(n))と書けることになるので，O(n^3) = O*(1)となってしまいますが，実際にはそのような書き方はあまりしないと思ってください．
  • グラフ理論に関する講義は非常に興味があったので楽しみながら講義を聞くことができました。1.3803という数字がどのように出てきたのか気になるので第2回も楽しみです。今後ともよろしくお願いいたします。
    --残念ながら，これはグラフ理論に関する講義ではないのです．残念ながら，グラフを扱えばグラフ理論になる，というわけではないのです．また，グラフに関する講義であるわけでもなく，グラフは例としてでてきているだけです．今後はグラフでない例も出てくる予定です．
  • 先ほど申し上げました通り，私は約束を守ります．全世代総力結集で，全員参加で頑張らなきゃ立て直せませんよ．だって，人数少ないですし，もう全員に働いていただきます．馬車馬のように働いていただきます．私自身もワークライフバランスという言葉を捨てます．働いて働いて働いて働いて働いて参ります．　（高市早苗　新総裁選出後のあいさつより引用）
    --馬車馬のように働くような馬車馬を皆さんが見たことあるのか，気になっています．
  • 27ページ目のアルゴリズム内の3. A(G-N[v]))の閉じかっこが二重になっているのは誤植でしょうか。
    --はい，ご指摘のとおり誤植です．修正しました．ありがとうございました．
  • アルゴリズムの改善で具体的にどれくらい嬉しいかの話を聞けるのはありがたいです
    --この嬉しさはあまり伝わらないのかもしれないと思っています．本来は，いろいろな例で実際に動作させた場合の状況をお伝えするのがよいのだと思いますが，この授業ではそこまでせずに，「最悪の場合の計算量がよくなった」ということと，「それによって何ができるようになるのか」ということだけをお伝えしていることになります．
  • オーダースター記法について初めて知ったので感心しました。それ以外の箇所に関してはいつも通り（離散数理工学の時のような）で安心しました。
    --O*記法はあまり標準的に使われるわけではないですが，細かいことを気にしなくてもよいので，この授業では使っていきます．皆さんが使うときには，ひとこと断ってから使う方がよいと思います．
  • 先生の授業内にけっこ速口でした。最後の新しいオーダー記法もはじめって聞きました。勉強になりました。
    --オーダー記法自体はよく使うので，しっかりと復習をしておいてください．

• 2回のレポート課題により評価を行う予定でいます．

• こちらをご覧ください

• 10/7 (1) 高速指数時間アルゴリズムの考え方
• 10/14 休み (体育祭)
• 10/21 (2) 分枝アルゴリズム：基礎
• 10/28 (3) 分枝アルゴリズム：高速化
• 11/4 (4) 分枝アルゴリズム：測度統治法
• 11/11 (5) 動的計画法：基礎
• 11/18 (6) 動的計画法：例
• 11/25 (7) 包除原理：原理
• 12/2 休み (秋ターム試験)
• 12/9 (8) 包除原理：例
• 12/16 (9) 部分集合たたみ込み：原理
• 12/23 休み (出張)
• 12/30 休み (冬季休業)
• 1/6 (10) 部分集合たたみ込み：例
• 1/13 (11) 指数時間仮説：原理
• 1/20 (12) 指数時間仮説：証明
• 1/27 (13) 最近の話題
• 2/3 休み (修士論文発表会)

• Fedor V. Fomin, Dieter Kratsch, Exact Exponential Algorithms. Springer, 2010.
  https://doi.org/10.1007/978-3-642-16533-7

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