離散最適化基礎論

2013年度後学期
金曜4限 (14:40-16:10)
西5-214

岡本吉央

テーマ：局所探索法の理論的側面

講義資料

(1) 10/4：離散最適化問題と局所探索法
スライド (10/18修正) | 印刷用スライド (10/18修正) | 演習問題 (10/4修正)
(2) 10/18：解の表現
スライド (10/18修正) | 印刷用スライド (10/18修正) | 演習問題
(3) 10/25：近傍関数と近傍グラフ
スライド (10/27修正) | 印刷用スライド (10/27修正) | 演習問題 (10/27修正)
(4) 11/1：近傍グラフの性質：連結性と直径
スライド (11/3修正) | 印刷用スライド (11/3修正) | 演習問題
(5) 11/8：性能保証 (1)：厳密近傍
スライド (11/8修正) | 印刷用スライド (11/8修正) | 演習問題
(6) 11/15：性能保証 (2)：近似比の算定
スライド | 印刷用スライド | 演習問題
(7) 12/6：性能保証 (3)：巡回セールスマン問題と近似比
スライド | 印刷用スライド | 演習問題
(8) 12/13：計算量 (1)：近傍探索の高速化
スライド (12/17修正) | 印刷用スライド (12/17修正) | 演習問題 (12/13修正)
(9) 12/20：計算量 (2)：大規模近傍
スライド (12/29修正) | 印刷用スライド (12/29修正) | 演習問題
(10) 1/10：計算量 (3)：反復回数の上界と下界
スライド | 印刷用スライド | 演習問題 (1/10修正)
(11) 1/24：計算量 (4)：近似局所探索
スライド (1/24修正) | 印刷用スライド (1/24修正) | 演習問題 (1/24修正)
(12) 1/31：計算量 (5)：クラスPLSとPLS完全性
スライド (1/31修正) | 印刷用スライド (1/31修正) | 演習問題
(13) 2/7：計算量 (6)：ランダム移動を用いた局所探索法
スライド (2/10修正) | 印刷用スライド (2/10修正) | 演習問題はありません

期末試験

日時：2月14日 (金) 14:40～16:10 (いつもの講義時間)
場所：西5号館214号室 (いつもの講義室)
出題形式
- 演習問題と同じ形式の問題を6題出題する
- その中の4題は演習問題として提示されたものと同一
- 全問に解答する
配点：1題20点満点，計120点満点
成績：100点以上は100点で打ち切り．
持ち込み：A4用紙1枚分，裏表自筆書き込みしたもののみ可
試験問題
得点分布
得点分布では，未受験者を含めていません．受験者数は17で，Aは8人，Bは3人，Cは2人，Dは4人です．(大学院にSはないので，注意を．)
念のためお断りしますが，拝んだり頼みこまれたりしても成績が上がることはありません．解答用紙内でお願いされても同じです．
採点結果を個人的に知りたい人は私の居室 (西4号館2階206号室) まで学生証を持参の上お越しください (部屋の前でスリッパに履き替えて下さい)．電話，メール，twitterなどでの問い合わせには応じられません．
講評
- 問題1：演習1.8と同じ問題．局所最適解と近傍関数に関する基本的な性質の証明．この問題は割とよくできていました．
- 問題2：演習5.5と同じ問題．厳密近傍に関する基本的な性質の証明．これはできた人とできていない人の差が大きな問題でした．私の感じる限り，できていない人は証明というものが何なのかということをよく理解できていないように思います．問いは「存在することを証明せよ」といってるのですから，そういうものを1つ見つければよいわけです．それが存在することを証明する方法の基本です．ちなみに，ある日，M先生と食事しながらこの講義の話をしていて，この問題について触れたら「それって自明だよね」と言われました．私の回答は「でも，証明は必要です」ということでした．別の言い方をすると，この問題は自明であるとも思える非常に簡単なことを聞いているわけです．そういう意味で，できていない人が多かったことには割と衝撃を受けました．
- 問題3：演習9.3と同じ問題．これもできた人とできていない人の差が大きな問題でした．これは授業でもやったものなのですが，「再帰とは何か？」ということを聞いている問題で，特に小問2の方は講義内容を知らなくても解けるものなので，出来ていない人は再帰についての基本的な理解ができていないと思って下さい．
- 問題4：同じ問題は演習にありませんが，演習6.4におけるmが3の場合と同じ．これは「構成せよ」と問題文に書いてあるので，構成して下さい．近似比が3/2となることの証明がちゃんとできていないと減点されています．近似比というものが何であるのか，という基本的な部分の理解が足りない答案も少なからず見受けられました．
- 問題5：同じ問題は演習にありません．正しく遷移グラフが描けて，即時移動と最良移動による最悪反復回数というのが何であるか分かっていれば，難しくないはず．この問題はよくできていました．数え方を間違えている答案 (反復回数を1つ多く数えている場合) に対して減点はしないことにしました．
- 問題6：演習12.3と同じ問題．PLS帰着の基本的な性質の証明．私が採点した印象ですが，この部分を勉強してきた人はできていて，そうでない人はできていない，という単純な分別ができたと思います．40点台でDとなっている人は，ここができていればCになっていました．残念です．

(13) 2/7：計算量 (6)：ランダム移動を用いた局所探索法
- コメントありがとうございました．
- 当日時間内に解けることを願うばかりです．ありがとうございました． ---願うだけでなく，しっかりと準備をしてきて下さい．
- 半年間ありがとうございました． ---こちらこそありがとうございました．
- 半年間ありがとうございました．テスト勉強のコツみたいなのがあれば教えて下さい． ---講義内容を見返して，重要だと思う点は持ち込み用紙に残して下さい．
- 今回の授業は前回に比べてわかりやすいし，おもしろかったです． ---前回は抽象的な話でしたからね．
- どういうわけか，僕は死ぬまでにP≠NPを証明しなければいけないみたいです．助けて下さい． ---死ななければよいのです．;-)
- 今日の内容は簡単だった． ---演習問題があれば，それで理解度を確認できたかもしれないのですが，用意してなくてすみません．
- 今日の内容も含め，全体的に非常に興味深い内容だったと思います．半年間ありがとうございました． ---こちらこそありがとうございました．来年度はまた違う内容をやります．
- 単位取れるようにしたい ---はい，お願いします．
- おつかれさまでした！結構面白かったです． ---ありがとうございました．
(12) 1/31：計算量 (5)：クラスPLSとPLS完全性
- コメントありがとうございました．
- 卒論，出してきましたー!! ---おめでとうございます
- テストができるか不安です ---しっかりと準備をしてきて下さい．
- 出題範囲が多すぎてつらいです ---どの講義でも1学期分の試験をやってると思うので，それと変わらないと思って下さい．
- P, NPの話は聞いてるだけでワクワクできて楽しいです ---そういう研究をやろうと思えばできる環境にいる，ということですので，ぜひチャレンジしてください．
- RくんがP≠NPを死ぬまでに証明してくれるらしいので楽しみです． ---証明するか，永遠の命を手に入れるか，どっちかですね．(永遠はいいすぎですが．)
- PLSに属するとは一意なのでしょうか？クラスPLSはアルゴリズムA, B, Cに拘らず1種類なのでしょうか？ ---A, B, Cが存在すればよいので，PLSは一意に定まります．ただし，A, B, Cが一意に定まるとは限りません．
- PLS-completeがNP-hardであるときにNP=co-NPとなる証明は本題からそれますが相当難しいのでしょうか？ ---論文における分量で言うと1/3ページです．「相当難しい」というものでもないです．
- PLS帰着が存在するかもよくわからないのにPLS完全はすごいところに飛んでるなあと思った ---存在を仮定して議論していますからね．計算量理論ではそういう議論の仕方をよくします．
- PLS帰着でアルゴリズムF, Gが多項式時間であると仮定しているのですが，Fはそのようなアルゴリズムが存在しそうですが，Gは難しいように感じます． ---実際にPLS完全性を証明するときにはFとGを作っています．そのとき，Gをうまく作れるようにFを作るというのがポイントになってきます．
- PLS完全問題の立ち位置があいまいになることに関して数学者がどのようにとらえているか気になります．白でも黒でもないグレーになることを好まなそうですが… ---実はそんなにあいまいではありません．PとNP困難の間にもたくさんの問題があるかもしれない，ということは研究者によって指摘されています．例えば，Ladnerの定理と呼ばれているものは，P≠NPならば，NPに属する問題で，Pにも属さないし，NP完全でもないものが存在する，ということを主張しています (定理なので証明されています)．P≠NPであると信じている人は多いので，P≠NPであれば，そのような中間的な問題は必ず存在します．
- 岡本先生はPLS完全問題が難しいと思いますか？ (すなわち，おどろき#1派) ---難しいとは思いますが，NP困難であるほど難しいかどうかは分かりません．難しさにも度合いがあるので，NP困難であるほど難しくはないけども，まだ難しいといえる，という段階はありえます．
(11) 1/24：計算量 (4)：近似局所探索
- コメントありがとうございました．
- 今日の話は少し面白かった ---面白く感じていただけてよかったです．
- 証明に感動しました．どのような訓練をすると素晴らしい証明ができるようになるのかが気になります． ---スポーツや芸術，料理と同じで，基本的な訓練が大事だと思います．
- f(τ)とf_i(τ)，τと˜τとτ'が入り乱れ，解説を追ってゆくのが大変だった ---確かにそうですね．どのような記号の使い方にすると分かりやすいのか，ということについて，工夫が必要ですね．
- 近似局所探索のεの値の設定をどうすればよいのか悩みましたが，計算量が1/εに比例するので，かなり大きめの値から，少しずつ値を小さくすればよいと思いました． ---そうですね．実際は，ある大きめの値をεとして，反復の中でqが更新されていくことがε自身を小さくしていくことに対応しています．最終的に得られる巡回路が気に入らない場合は，再びqを更新して反復を続ける，とすればよいです．
- q_iと言えば，イギリスのクイズ番組QIが良いですね． ---『QI』はquite interestingの略なんですね．
- 2/7より前に演習レポートは提出可能ですか？ ---はい，私に直接渡すか，西4号館4階の事務室の前にあるレポートBOXの「岡本」のところに入れて下さい．
- もし急な企業説明会とテストの日が重なってしまった場合，どうしたらいいですか？ ---すぐに連絡を下さい．事後では対応できないので，注意して下さい．
- 合格点は何点ですか ---60点です．
- 復習問題は何題出題されますか ---知りません．
- テストの準備，修論出したら本気出します ---はい，よろしくお願いします．
- 途中から入ると後を追うのが大変でした ---できるかぎり，はじめから来てください．
(10) 1/10：計算量 (3)：反復回数の上界と下界
- コメントありがとうございました．
- あけましておめでとうございます．今年もよろしくお願いします． ---今年もよろしくお願いします．
- 明けましておめでとうございました．病気で寝正月でした． ---お大事に．
- 明けましておめでとうございます．今年もよろしくお願いします．再履にならないようにはがんばります．年賀状は書きましたか？ ---年賀状は書かないことにしています．
- 日に日に寒さが厳しくなっていますが体調を崩さないように気をつけて下さい ---ありがとうございます．なんとなく，もうすぐ雪が降るのではないかと思ってます．
- 問題をどんどん解いて理解を深めたいです． ---はい，是非そうしていって下さい．
- 今日の証明は感動的だった ---基本的なことの積み重ねできれいに証明ができているところがいいですね．
- 帰納法はすばらしいと思います ---帰納法は証明法としてとても標準的で，よく使うものなので，是非マスターして下さい．
- '96年，'03年に証明された定理の証明を一学生である我々が理解できる，ということはすごいことだと思います． ---離散数学に関わる証明は，聞けば理解できるけども，それを思いつくことが難しい，とよく言われます．そのため，それを思いつくために繰り返し練習が必要になるわけです．
- 最悪例の数字が2^n/16+4-22とかどんな発想したら出てくるんだって突っ込みしか出来ず，新規性という言葉に頭がやられそうです． ---細かい数字は気にしないでください．それよりは，nに関して指数関数的になる，ということが重要なのです．
- 局所探索法が悪い方法な気がしてきた ---理論的にはあまりよいことが分かっていない，というのが現状ですね．理論と実践の差が大きいことも局所探索法にまつわる状況なのですが，ここら辺については最終回の講義で少し述べたいと思います．
- 最良移動戦略の最悪反復回数が分かると助かるのですが，一般的にそれを示せた問題はないのでしょうか ---あります．最後の補足で，線形計画法における単体法について少し述べましたが，そこでは，最良移動戦略の最悪反復回数が入力に現れる変数の数に関して指数関数的になってしまう例が知られています．線形計画法における単体法の最悪反復回数はよく調べられている話題で，最近 (2010年代) でも活発に研究がされています．
- 「複数回動くJobは最後以外に"小さい移動"である」という補題を先にほしかったですね．Aから明らかなのですけど． ---そうですね，その事実を補題として分けておくと，もっと分かりやすくなったと思います．
- 今日の機械台数2の最終完了時刻最小化スケジューリング問題とグラフ等分割問題の近傍と問題が似ている気がしました．両方とも集合の2分割というところで．グラフの等分割のグラフが完全グラフのとき辺数がn(n-1)/2，即時移動による最悪反復回数がO(n²)となり，スケジュールと何か関係がありそうだと思いました． ---見た目上はとてもよく似てますね．しかし，証明法は全く違うので，真にどこまで似ているのか，と言われると，少し悩みます．そこら辺を統一的に証明する方法論があると，そのような相似性についても理解が深まるのだと思いますが，現状はそこまで私たちの理解が進んでいない，ということになるのだと思います．
(9) 12/20：計算量 (2)：大規模近傍
- コメントありがとうございました．
- 今日は暖かかった ---そうですね，暖房が直ったのだと思います．
- 眠いのです． ---質問をすると，眠くなくなると思いますので，そうしてみて下さい．
- スライドや印刷資料はPCで閲覧できるのですが，スマホやタブレットではできません．何か設定とかしてありますか？ ---PDFファイルを読むためのアプリケーションが必要です．ダウンロードして設定をして下さい．
- 実際に問題を解くのが非常に難しい ---まずは復習問題からやってみて，講義内容が理解できているか確認してみて下さい．
- 超がつかないただの大規模近傍はありますか ---「大規模近傍」も「超大規模近傍」も同じ意味で使うことが多いですが，「超大規模近傍」と呼ぶ方が普通のようです．
- 超大規模近傍は初期解の選び方によって局所最適解の良さが大きくばらつきそうなのですがどうなのでしょうか？直径が小さいので相殺されるのでしょうか？ ---直径が小さいから相殺される，ということはありそうですが，理論的にその点を調査している研究を私は知らないです．なので，よい研究課題になると思います．
- 高速なアルゴリズムを考える際に「これを使えばこの程度の計算量になる」という見積りから始めるのか，「この問題を高速に解きたい」という心意気から始めるのか，どちらのきっかけが多いのかが気になります． ---普通は後者が先にあって，その次に，どのような方法論を用いるか考えることで前者の思考が出てきます．
- 割当近傍の探索でループを行ってないのは，最初の割当操作が固定された除去しかしないからですか？ ---そうですね．本来，局所探索法としては反復を行わなくてはならないのですが，割当近傍の場合は反復が1回で必ず終わるのです．
- 割当近傍では，偶数番目の頂点しか取り除かないので (巡回セールスマン問題の許容解全てを頂点とする) 近傍グラフは非連結になりそうですが，ピラミッド型の場合は近傍グラフは連結なグラフになりますか？ ---割当近傍については，その通りです．ピラミッド型巡回路近傍については一つ気をつけないといけないのは，それが対称な近傍関数ではないことです．なので，近傍グラフを考えるときは有向グラフであるとして考える必要があります．このとき，近傍グラフは確かに強連結となります．
- ピラミッド型巡回路近傍は得られた近傍を再度1からnまで並べるとピラミッド型巡回路であることが保証されないということですが，これは初期解がピラミッド型巡回路でなくてもτ₁=1, ..., τ_n=nとなるように添字を取り替えることでピラミッド巡回路を考えることができるということでしょうか． ---その通りですね．
- 効率の良いデータ構造は言われれば納得できるかな？何か再帰見てるとDijkstra法の仲間っぽいですねえ． ---Dijkstra法も動的計画法の一種なので，確かに仲間ということになります．
- 9.5 最初はJ₁からJ_nまでのジョブの中で最も小さいJ_k1を任意のM_k1に割り当てる．次は，J_k1を除いたJ₁からJ_nの中で最も小さいJ_k2を任意のM_k2に割り当てる．... ---それだと，M_k1，M_k2，...が全部同じでもよいので，最適解を得られる保証がないですね．
- よいお年をー！！ (*^^*) ---よいお年をー
(8) 12/13：計算量 (1)：近傍探索の高速化
- コメントありがとうございました．今回はあまり演習問題の時間がとれず，済みませんでした．
- わかりやすかったです． ---ありがとうございます．
- 今日は寒かった．暖房を入れても寒かった．壊れてるのかな ---エラーがでてました．壊れてたみたいです．
- 非常に寒かった． ---防寒対策をしてきて下さい．
- 寒かった ---私も寒かったです．
- スライド17のmax{l₂, l_j+p_i}＜l₁でこのl₁, l₂というのはジョブJ_iを移動操作した後のl₁, l₂でよろしいでしょうか？ ---移動の前のl₁, l₂です．そうだと思ってもう一度資料を見直してみると理解が深まると思います．
- 今さらな質問ですが，最終完了時刻最小化スケジューリング問題に対する移動操作において，J∈A_iをi∈{1,...,m}からj∈{1,...,m}-{i}に動かすというのは，初期解それ自身を含むという近傍関数の定義に反しないのでしょうか． ---今さらな質問も大歓迎です．移動操作はそのように定義するのですが，そこから近傍関数を定義するときには，移動操作にして得られるスケジュールと移動前のスケジュールを合わせて近傍である，として定義します．資料を見ると「○○から導かれる」とか「○○が誘導する」というような書き方をしていると思いますが，それはそのような意味であると解釈して下さい．
- ヒープの話が単純に懐かしいと感じてしまいました． ---案外いろんなところで出てくるので，もっと身近に感じて下さい ;-)
- 今回の講義でヒープのありがたみを再確認するとともに，「このデータ構造を使って，このようにすれば，高速に計算できる」というアイデアをきちんと示されたので，非常に気持ち良かったです． ---データ構造にはいろいろとありがたいことがあり，特に局所探索法のように，同じような処理を何度も行う，という場合には，とても有効ですね．
- 私事なのですが，出来なかった (分からなかった) ことがなぜ出来なかった (分からなかった) のかが，今回の講義から分かりました．行間をうめる作業は大変だと思いました．ありがとうございます． ---「私事なので…」で始まると，結婚しましたとか転職しました，とかそういうのが続くのかと思ってドキドキしました ;-)．いずれにせよ，何か分かっていただけたようでありがたいです．こちらこそありがとうございました．
- 8.5，ダランベールの収束判定法で収束することしかわかりません． ---ダランベールの収束判定法でたしかに収束することはわかりますね．有限和を計算してから，それを無限大に持っていく，ということをすればできると思います．必要ではないかもしれませんが，二項定理を使ってもよいかもしれません．
- 図やグラフはどのようなソフトで描いていますか？ ---ipeを使っています．
(7) 12/6：性能保証 (3)：巡回セールスマン問題と近似比
- コメントありがとうございました．
- スライドのデザインがシンプルで気に入ってます ---ありがとうございます．使っているのはLaTeXのbeamerクラスです．
- 3週間ぶりの講義で何をやっていたか結構忘れてしまったので，復習しときます． ---講義が始まる前に，前までの内容を見返すと少しは思い出せると思うので，是非励行して下さい．
- 証明は理解できましたが，なぜそのように証明するのかまではわかりませんでした．数学の証明が得意になる方法を知りたいです． ---たしかに，「なぜ」という部分には私も不満があります．別の言い方をすると，「なぜ」という質問に答えられるだけ，満足な理解を私たちは巡回セールスマン問題に対してしていないのだ，というのが現状なのです．それだから研究をしてるのです．
- 証明を聞きつつ追いかけるのは何とかなるけど，自分で再現するのは手が止まりますね．「どんな発想してんだ」と言いたくなる組立ばかりです． ---演習問題としてこの証明を掲載している部分では，誘導がありますので，それに沿って考えてみて下さい．
- 今日の証明は長かったので，途中でτとかE_iとかの変数の意味や補題 (観察) で何を証明しようとしていたのか忘れそうになってしまった．後でゆっくりスライドを見直します． ---はい，是非お願いします．
- 非常に長い証明であったがわかりやすかった． ---たしかに長かったのですが，できるかぎりわかりやすくなるように努めました．ありがとうございます．
- 証明は難しかったが，三角不等式を満たすという条件が証明中で有効に働いているのが分かった． ---有効に働いていましたね．別の言い方をすると，証明の中で有効に働いていない条件があるとすると，それを外しても証明したいことが成立する可能性が出てきます．その可能性を見ていくと，問題の本質に迫っていくことができるかもしれません．
- 今回の証明は非常に長い旅のようでした．近似比の上界がわかることで安心 (?) してアルゴリズムを使用できる気がしました． ---そうですね．上界が理論的に得られたということが重要で，それによってアルゴリズムの動作に保証が与えられているのですね．
- 証明の手順が序盤の授業よりややこしくなったので，この後がこわい ---この後で何が起こるのか，私もあまり分かっていないので，私もこわいです．
- 補題7.5の証明の部分集合の構成(1)で，Xの任意の都市uを選んでいるのですが，これは選ぶ順番によらず集合Yは一意に定まるのでしょうか？集合は異なるけど，集合の要素数は等しくなると思います．なので，|Y|＞√iには関係ないと思うのですが．書いているうちに反例が思いついたのですが，時間が． ---Yは一意に定まらないです．Yの要素数が等しくなるということもないのですが，どのようにuを選んでいっても|Y|＞√iという不等式は成り立ちます．
- 急に難しくなりましたね ---たしかに急だったかもしれませんが，1ステップずつしっかりと追っていけば，追える内容だとは思います．
- 急に難しくなりましたね ---たしかに急だったかもしれませんが，1ステップずつしっかりと追っていけば，追える内容だとは思います．
- 7.2は数学的帰納法で解けますかね (直接でも解けそうですが)．ステップ1：頂点が3つの場合，ステップ2：頂点がnの場合に題意成立と仮定したとき頂点数n+1のとき． ---数学的帰納法を使おうと思って証明すると，実は数学的帰納法を使わない証明になると思います．
- そういえば，今日は私の誕生日です．また1つ大人になりました． ---おめでとうございます．
- 難しかった．なんとなくわかった．おもしろかった． ---「なんとなく」よりも上の「確実にわかった」まで進められるようにして下さい．
- 指数タワーは面白いですよね．巨大数論はここ10年でかなり研究されていて熱いです． ---巨大数論というものがあることを知らなかったので後で調べます．ありがとうございます．巨大数についてはwikipediaにも項目がありますね．楽しいです．
- 不覚orz第6回を印刷してしまいました． ---気をつけて下さい．
- 先日twitterのTLで話題でした「過去問くん」知ってますか？ ---すいませんが，知りません．
(6) 11/8：性能保証 (2)：近似比の算定
- コメントありがとうございました．
- スライド29ページで，なぜt^*≧p_kなのかわからなかったです． ---授業のときとはちょっと違う説明のしかたにします．任意のスケジュールとそこで処理されている任意のジョブJ_iを考えます．このとき，そのスケジュールの最終完了時刻は必ずJ_iの処理時間p_i以上になります．なぜでしょうか．その理由 (つまり証明) は以下の通りです．(1) ジョブJ_iを処理する機械の完了時刻はp_i以上です．なぜなら，その機械はJ_iを処理するから．(2) 最終完了時刻はジョブJ_iを処理する機械の完了時刻以上です．それは最終完了時刻の定義から分かります．(3) いままで見た(1)と(2)から「最終完了時刻はp_i以上」ということが証明できました．ここで，iとしてkを選べばt^*≧p_kという式が得られます．
- 間違っているのかもしれませんが，ある離散最適化問題の近傍関数の数は有限だと思うのですが，たくさん存在していると思います．その中で，2opt操作のような近傍関数の性能保証をしらべると悪いと分かったのですが，それをすべての近傍関数に対して行うと果てしなく感じます．何か，近傍関数を作るコツとかあるのでしょうか？それとも経験とか人間的なものによるものでしょうか． ---「ある離散最適化問題の近傍関数の数は有限だ」というのはある意味で正しく，ある意味では正しくないです．まず，正しいという説明をします．離散最適化問題の許容集合Sは有限集合です．近傍関数はSから2^Sへの関数です．一般に，有限集合AとBがあるとき，AからBへの関数の総数は|B|^|A|になります．なので，近傍関数の数は有限になります．次に正しくないという説明をします．これは，例えば「巡回セールスマン問題」が「ある離散最適化問題」であると解釈すると正しくない，ということになります．このとき，巡回セールスマン問題の入力というのが無限に存在するので，近傍関数の数も無限になります．それでも「たくさん存在している」というのはいずれにせよ正しく，「すべての近傍関数に対して行うと果てしなく感じる」という感覚も正しいと思います．よい近傍関数を作ることは経験に基づく部分が大きいですが，この講義でやっている評価観点を念頭において設計することが重要です．
- 初めて証明した人はすごいと思った． ---そうですね．証明ができる前には，まだ何が正しいのか分からなかったわけですから，ある程度の信念を持って証明をしないといけないわけです．
- 今日の証明は結果や期待から逆算して解くような手順があって難しかった ---証明すべきことが分かると，そこから方針が見えてくることがあります．よく証明を見てみるととても自然な証明をしていることが分かるかもしれません．
- 今日の近似比の証明はすごく面白かった ---証明が面白く感じられるようになるのはいいですね．演習問題にも取り組んで下さい．
- 6.4について，m=3のとき．
  
  1 1 1 1 1
  
  2 2 1
  
  4 4
  
  の様な入力でいいのでしょうか？許容解は
  
  2 1 1 1 1
  
  4 2
  
  4 1 1
  
  となり近似比は4/3 ---m=3のとき，この入力で近似比が4/3以上になるということは正しいです．しかし，構成してもらいたい入力は近似比が3/2以上になるものなので，これではまだ不十分ということになります．
- (^≡*w*^≡) ネタが尽きてしまいました．アルゴリズムの設計には，書き方は決まっているのでしょうか？ ---きまりはないですね．人によってどのように書かれていると分かりやすいのか，が違うようです．私は疑似コードで書かれていると分かりやすく，自分でも疑似コードで書いてます．その方が基本的な考え方が分かりやすいからです．
- 「一番有能でない人ができれば，ほかの人もできる」は言えますが，「一番有能である人ができれば，ほかの人もできる」は言えないと思いました．これがおこりえるのがどうしてなのかを考えると，「一番有能である本人が一番有能でない」と考えてるからだとわかりました． ---様相論理ですね．「○○である」ということと「○○であると考えている (信じている)」ということの違いを認識することが大事ですね．
- グラフ描画はどうやってますか？オススメのソフト等あれば教えて下さい． ---私は大体手動で描いています．私が使っているドローイングツールはIpeです．計算幾何を研究している人はほとんどこれを使っています．その他，自動的にグラフを描くプログラムとしてGraphvizを使うこともあります．あと，前回のコメント欄にも書きましたが，yEdやGraphityは手軽なツールだと思います (私は使ったことがありませんが)．
- 先週は就活でおやすみしてました．ゆっくりしたペースでトピックをすすめていただけると一週開いても対応できそうなので助かります． ---はい，わかりました．
(5) 11/8：性能保証 (1)：厳密近傍
- コメントありがとうございました．今日は欠席者が多かったと思いますので，自分で復習をするようにお願いします．
- 本日の授業は，厳密近傍という概念について紹介されました．第5回ですが，いままでの内容を少し忘れていて，復習しなくてはいけません． ---はい，復習をお願いします．
- グラフの証明難しい ---そうですね．離散数学の証明には独特の味わいがあるので，それに是非慣れて下さい．
- 証明の難しさが増した ---これからも証明が核となるので，心の準備をお願いします．
- 板書が多くてわかりやすかった ---ありがとうございます．板書が効果的にできたかどうかよく分かっていませんが，スライドと板書を両方使ってうまく説明できるように心掛けているつもりではいます．
- 最適解であること，そうでないことの言い換えを証明の際に表現するのが難しい ---この辺りは論理の書き換えなので，機械的にできるはずです．自分でも試して下さい．
- グラフは手を動かさないと分かりにくいのに，手で書くとすごく残念な図になりがちでつらい．PCでグラフィカルに動かせればいいなとか毎度思います． ---手で動かせるようなエディタがいくつか知られています．例えば，yEdやGraphityは手軽なツールだと思います．
- ∀x∈S (∀x'∈N(x) (f(x)≦f(x')) → ∀x'∈S (f(x)≦f(x'))) は ∀x∈S (∀x'∈N(x) (f(x)≦f(x')) → ∀x''∈S (f(x)≦f(x''))) でなくて良いのでしょうか？ x'∈N(x)→x'∈Sですがx'∈S→x'∈N(x)とは限らないので．細かくてすみません． ---細かくてもよいので，どしどし質問を下さい．2つに分けてお答えします．(1) この2つは論理的には同値です．具体的にいうと「→」の前後で変数のスコープが切れています．つまり，「→」の前の部分のx'と後の部分のx'は違う変数なので．なので，論理的には同値なのです．(2) しかし，指摘してもらった書き方の方が好ましいとは思います．というのは，そのようなスコープのことを考えなくてもよいからです．特に，論理学ではある種の標準形に論理式を書き換えることがよくありますが，その際に，すべての変数の名前が異なるようにするというのはよく行う操作です．
- 70年代に最後のような事が分かっていたのに驚きです．今はどんなに進んでいるのかを考えるとはてしない気がします． ---実を言うと，厳密近傍に関する研究は最近あまり行われなくなっています．難しい離散最適化問題に対して厳密近傍が役に立たないという理論的な結果が多く知られるようになり，その望みが消えたからです．その一方で，厳密近傍ではない近傍関数に関して近似比として何が得られるのかという研究は盛んにされています．これは次回からの話題になりますので，お楽しみに．
- 髪切ってさっぱりしましたね ---ありがとうございます．冬場に髪を切ると，風邪をひきやすいので，要注意です．
(4) 11/1：近傍グラフの性質：連結性と直径
- コメントありがとうございました．防災訓練へのご参加，おつかれさまでした．
- 予想：引率なしだと思います ---自分でしてしまいました．
- 1時間だと短いですね ---そうですね．短いですね．
- 証明つらいです ---がんばりましょう．
- 証明がつらいです． ---がんばりましょう．
- 証明を書くのは大変だと思った ---大変な場合は，証明を考えるためのアイディアと，それをちゃんと書き下すところを明確に分けるとよいです．
- 証明が非常に大変そうだった ---大変な場合は，証明を考えるためのアイディアと，それをちゃんと書き下すところを明確に分けるとよいです．
- 2回目のスライド番号34の「J_iとJ_i+1の完了時刻和のみ」という文は完了時刻ではないのでしょうか？ ---そのままで正しいですが，分かりにくいかもしれません．2つのスケジュールの完了時刻和の違いはJ_iの完了時刻とJ_i+1の完了時刻のみで，「J_iの完了時刻とJ_i+1の完了時刻」を「J_iとJ_i+1の完了時刻和」と表現しています．
- 前回の巡回セールスマン問題のn(n-3)+1が証明できなかったのですが，今回の最後の証明のアイディアを使えば出来そうな気がします．どうなるかは分かりませんが． ---はい，試してみて下さい．
- 本日は特にないです ---是非演習問題をやって下さい．
- アルゴリズムを考える人は天才だと思っていましたが，それを証明するのもとんでもないことだと思いました． ---証明のないアルゴリズムはアルゴリズムと呼べないと私は思っています．証明のないアルゴリズムはただの思いつきです．アルゴリズムが正しく動くのは，そこに証明があるからです．
- 近傍グラフの直径について理解できました ---是非演習問題もやって下さい．
- 先生は今日の巡回セールスマン問題の直径の証明があまり気に入らないようでしたが，そういうアルゴリズム的な証明は私は結構好きです．もっとあってもいいと思います． ---別に気に入らないわけではないのですが，過度に表記が複雑になってしまっていて，その点がよくないと思っています．うまく表現すれば，それほど複雑にならないと思うのですが，そのような表現を練られなかったことが気に入らない点です．
- グラフの直径は小さいほど良いという話でしたが，グラフの直径が小さいことはその分∀x∈Sに対してxの近傍が多いということになりませんか？そうなると近傍探索でたくさんのx'についてf(x')の値を確認しなければならなくなって計算量が増える気がします． ---その通りですね．なので，直径は基準の1つにしかすぎず，絶対的な基準であるというわけではないです．また，後の講義で議論しますが，近傍を探索する反復継続条件の確認をどのように行うのかということにも工夫のしどころがあって，いろいろなことが絡み合ってきます．
- 局所操作回数の下界が直径だと分かりましたが，上界はどうなるんだろうと思いました． ---自明な上界は許容解の数になりますね．局所探索法を行うと，すべての許容解をたどっていって最終的に局所最適解に到達するということがありえます．そして，ある種の自然な問題 (の人工的な例) においても，そのようなことが実際起きてしまうことが知られています．
(3) 10/25：近傍関数と近傍グラフ
- コメントありがとうございました．n(n-3)は間違いで，正しくはn(n-3)+1でした．そして，n≧4ではなくて，n≧5のときに，これは成り立ちます．
- 雨って嫌ですね ---嫌ですね．
- P.24のグラフにバグを発見しました．一番右・真中の頂点に有向辺の始点がありません． ---ありがとうございます．左上に向かって出ていく有向辺があるので，大丈夫だと思います．
- 3.8とけません．N₂(x) = {y∈S | |x-y| ≦ 2} の意味がわからない ---集合の書き方で「{○○ | △△}」となっていたら，「△△を満たす○○をすべて集めた集合」のことを表します．この場合は|x-y|≦2を満たすyをすべて集めた集合 (ただし，y∈S) になります．
- 3.8の近傍関数はタコの足みたいに各頂点0から9までがつながりあってるグラフになる訳ですね．N₁を自分で書き直して理解できました． ---そうですね．授業の中で出てきた例も自分でやり直してみると理解が深まると思います．
- 演習は後にまとめて提出してもOKですか？ ---はい，OKです．
- このときは遷移グラフはひかれないであっているでしょうか？
  ---はい，あってます．遷移グラフではこの2つの頂点の間にどちらの向きの弧も存在しません．
- 遷移グラフにおいて，どのノードが最終的にどのノードに到達するのかを色分けすると，より分かりやすいと思いました． ---なるほど，そうですね．今度試してみるかもしれません．
- 演習問題の中で解くことに特に推奨される問題が (特に授業中に) ありましたら，講義資料のラストの頁にその旨を書いていただければ自習するのにも役立ちますので，できればお願いします． ---すみません，これは難しいです．授業中に推奨といっているものは，相談して考えることに適しているとか，時間内にできそうであるとか，残り時間も見ながら決めているので，前もってどれが推奨となるのかは決めにくいです．
- 今日はいつもより噛みかみでしたね．スライドにも間違いがいくつかあったし．やっぱり6時間かけて作ったグラフのせいでお疲れでしたか？ ---ちょっと落ち着きが足りなかった気がします．
- グラフの図，感動しました． ---ありがとうございます．是非自分でも描いてみて下さい．
- テストでグラフを書く問があったら大変です． ---時間内に終わり，解答用紙に収まるような問しかでてこないと思って下さい．
- 近傍の大きさの数え方には気をつけないといけないと思いました． ---気をつけてなかったので私は間違えてしまったのだと思います．
- 有向閉路が存在しないことの証明なのに，アルゴリズムが停止することを示しているので，シンプルで良いと思います． ---そうですね．グラフを道具として使っているということに注目して下さい．
- 近傍関数の選び方によってアルゴリズムの性能に違いがでることがよく分かりました． ---その性能の違いについて，講義の中でより深く扱っていきます．
- 本日の講義の中では，近傍グラフと遷移グラフがでていて，グラフを見ると難しそうな感じでした．また，理解が深くなるように，スライドを見直そうと思います． ---はい，復習は大事ですので，是非そうして下さい．
- 授業はある程度理解できたが証明がきびしい． ---証明までできて完全な理解なので，頑張って下さい．
- 頂点挿入のグラフは，n次元のハイパーキューブの有向版の様に見えた．どちらも解集合2^Sの完全グラフだから当然ではあるのだが． ---いい着眼点ですね．しかし，残念ながら，巡回セールスマン問題に対する頂点挿入近傍の近傍グラフはハイパーキューブになっていないです．一方，最終完了時刻最小化スケジューリング問題に対する移動近傍の近傍グラフはハイパーキューブになっています．
- 板書は電気を点けた方がやはり見やすい ---では，そのように今後もします．
- スライドの説明の時は電気を消して，黒板の説明の時は電気を点けていただけるとありがたいです． ---点けたり消したりするのに時間がかかるので，すみませんが，ずっと点けっぱなしにさせて下さい．
(2) 10/18：解の表現
- コメントありがとうございました．1回目を休んだ人は1回目の分の復習もしておいて下さい．資料は上にあります．
- 誤字報告 10/4スライド P66 ねらばらし → ねたばらし，10/4 演習問題追加1.5 最大完了時刻最小化 → 最終完了時刻最小化 ---ありがとうございます．演習問題の方は前回既に指摘していただいたので修正済みです．もう一方の方は今修正しました．
- 背理法での証明はあまり良くないのでしょうか ---できれば避けた方がよいと言われています．その理由ですが，背理法は直感的でも直観的でもないからです．今日の授業で出てきた定理も背理法を使わないで証明できます．しかし，背理法の証明は短くて済む場合が多く，そのような利点もあります．
- わかりやすかったです． ---ありがとうございます．演習問題にも取り組んで下さい．
- 今日はすごくわかりやすかったです． ---ありがとうございます．演習問題にも取り組んで下さい．
- わかりやすかった ---ありがとうございます．演習問題にも取り組んで下さい．
- 局所探索法そのものよりも，その周囲に存在する問題が難しいと感じた ---局所探索法で何かを行うときにはいろんなことに気をつける必要がありますね．
- 説明が長すぎて，少し退屈していました…丁寧に説明しているとも言えますが． ---今日まではまだ易しい方なので，だんだん難しくなっていくと思って下さい．
- 近傍関数Nだけでなく，局所探索法は最初に選択するxと近傍関数Nの2つに依存すると思いました． ---そうですね．本来は最初に選択するxをどのように選ぶのかということが割と重要なのですが，その辺りの話は今後あまり出てこないことになります．
- 演習時間をもっと長くして下さい ---すみません，現行の15分が精いっぱいですので，自分で演習問題を解く時間を見つけて下さい．
- 黒板に書く時は電気をつけてください ---では，次回はそうしてみます．スイッチの近くに座る人はご協力をよろしくお願いします．
- 前の電気をつけなくても黒板は見えると思うので電気は消したままで良いと思います ---次回はつけてみようと思います．
- 調布祭ではグリークラブの「焼きそば」よろしくお願いします！！ 3年間焼きそばおいしかったので，今年もおいしいはず ---調布祭では岡本研の研究室公開もよろしくお願いします．
- 質問ナシ ---演習問題に取り組んで下さい．
- 今の授業をやっとききとれました．よかったです． ---こちらもよかったです．ありがとうございます．
- 講義資料のページでNewが上，Oldが下の順でソートされてますが，逆順にソートしていただいた方が直感的に見やすいです．特に授業中に見るときに ---そのように変更しました．
- 今回の定理の証明は理解しやすいと思いました．ただ，数理解析のようなグラフ理論を用いた証明が出てくると危険な予感がします ---残念ながら次回からグラフがだんだんと出てきます．
- 局所探索法の条件変更により起きる不都合の証明．f(x')≦f(x)としたときf(x')=f(x)が存在したとすると，局所探索法が終わらなくなる？ ---そんな雰囲気です．「f(x')=f(x)が存在」というのは日本語として意味が成立しないので，その点を書き改めれば問題がなくなります．
(1) 10/4：離散最適化問題と局所探索法
- コメントありがとうございました．初回にしては割とリラックスした雰囲気の講義だったと思います．
- 内容は面白かったが，すこし進行が遅いような気がしました ---今日は初回なので，同じぐらいの進行でもだんだんと早く感じるようになるかもしれません．そうなので，今の進行を保ちたいと思います．
- 局所探索をつきつめるのは時間がかかりそうで大変に感じた ---今後の講義ではその辺りを理論的に突きつめていきます．
- 巡回セールスマン問題の目的関数のシグマがどこまでかかってるか分かりにくかった．(書き方上仕方ない？) ---確かに分かりにくいですね．慎重になって読んでみれば理解できるかと思います．
- 電気は消した方がいいです． ---次回またアンケートを取ります．
- 追加問題1.5に関して，最大→最終？ ---確かにその通りです．訂正しておきます．
- テストに出る演習問題の4問は，復習問題，補足，追加の全てから出るってことで良いでしょうか？ ---はい，その通りです．
- 声がはっきりしていて聞きやすい ---ありがとうございます．
- 演習の解答レポートの形式指定はありますか？ ---形式の指定はありません．ただ，返却するために，氏名はどこかに記載して下さい．
- 窓の開け閉めについては勝手にやるので先生が暑いと感じていらっしゃるなら言って下さい． ---ありがとうございます．ただ，暑いのは私だけかもしれないので，その場合は我慢します．
- 授業中にtexをいじりながら演習問題を解いていることもしばしばあると思いますがレポートの提出はメールでいいでしょうか？ ---はい，メールでもよいです．ただし，返却は印刷された紙で行います．
- 「放送禁止用語」は放送しなきゃいいんです！！ ---どこで放送されるかわからないので，日ごろから気をつけているのです．
- すごくわかりやすかったです．次回も楽しい講義を期待してます． ---ありがとうございました．
- 分かりやすい説明だと思った． ---ありがとうございました．
- 具体例や手順が示してあってわかりやすかった． ---具体例は重要だと思っているので，できるだけいれるように心掛けています．
- 黒板の字が暗くて見づらい ---これについては次回アンケートを行います
- だんだんと内容が難しくなりそうで不安です… ---それは難しくなっていきますが，分からなくなりそうになったらどんどん質問して解決をしていって下さい．
- 具体的な例を多く使っていただいて分かりやすかったです． ---ありがとうございます．
- 関係ないですが，beamerのアニメーションをどう書いているのか気になりました． ---アニメーションではなく，実際はパラパラ漫画になっています．ただ単に10枚ぐらい図のファイルを作って，それを順に見せているだけです．
- 最後に問題解いてて楽しかったので，とろうと思います． ---演習問題を解くことが楽しめるのはとてもいいです．今後も楽しんで下さい．
- レポートは出したらいつ頃返ってきますか？ ---提出された翌週の講義のときに返却する予定です．
- 下界を求める手法などを軽くのせてもらえるとうれしいです． ---これは本当に難しく，離散最適化の真髄になっていくので，軽く，というのも難しいです．それでもキーワードだけ挙げると，「緩和問題を解く」というのと「緩和を強化する」というのが重要な技法です．
- 板書はスライド印刷した用紙にメモするのでいいですかね．ノート買う必要なかったかもしれない． ---はい，それについては自由にどうぞ．ノートは演習問題を解くために使いましょう．
- 暑いし問題難しい ---外気は冷たくなってきてるんですけどね．
- とてもイメージしやすい内容でした． ---ありがとうございました．
- 講義の流れは，抽象→具体にしてほしかった． ---ここは好みが分かれるところだと思うんですよね．私は具体→抽象が好きで，こちらの方が理解しやすいと思っているのですが，いつか逆向きも試してみます．