京都大学ELCAS(エルキャス)

平成27年度以前のレポート

数理工学

数理工学の2016年2月6日の内容はこちら



実習指導

永持 仁 (離散数理研究室 教授)
Aleksandar Shurbevski (離散数理研究室 助教授)

チューター

田村 有為 (離散数理研究室 専攻)
黒木 智弘 (離散数理研究室 専攻)
須藤 浩明  (離散数理研究室 専攻)

ボランティア

なし

実施場所

吉田キャンパス  総合研究8号館講義室3 

実習内容

前回解説し、完成させたグラフの到達可能点を収集するアルゴリズムを復習した。そのアルゴリズムからグラフ上の任意の2点間の路を出力するアルゴリズムが作成できることを解説し、実際にPythonコードの穴埋め方式で実装してもらった。グラフ上の任意の2点間の路を出力するアルゴリズムを用いて、最大フロー問題のアルゴリズムを解くアルゴリズムが作成できることを解説し、実際にPythonコードの穴埋め方式で実装してもらった。実装したアルゴリズムを用いて、畳パズル問題から変換した最大フロー問題を実際に解いてもらった。「最大フローは最小カットの容量に等しい」ことを簡単に解説し、畳パズル問題から変換した最大フロー問題を解くだけで全探索しなくても解が保証されることを解説した

畳パズル問題を再帰的アルゴリズムで解いた場合に対して最大フロー問題を解くアルゴリズムを利用して解いた場合は、計算時間が大きく削減できることの解説。
畳パズル問題を再帰的アルゴリズムで解いた場合に対して最大フロー問題を解くアルゴリズムを利用して解いた場合は、計算時間が大きく削減できることの解説。

畳パズル問題だけでなく、座布団パズル問題、防水シート問題、暖房マット問題や長方形への分割問題がグラフへ変換することで最大フロー問題を解くアルゴリズムを利用して解けることの解説。
畳パズル問題だけでなく、座布団パズル問題、防水シート問題、暖房マット問題や長方形への分割問題がグラフへ変換することで最大フロー問題を解くアルゴリズムを利用して解けることの解説。


受講生の感想

  • 床をグラフに置き換えることで、4つのパズルが解けるのはすごいと思った。また、4つのパズルも見方を変えることで他のグラフとの関係が見えてくる。監視カメラの問題は入り口、3つと目的地2つでパズルと少し異なるが、グラフをうまく、つけ加えることで、パズルと同様に解ける。
  • 今回は、3時間ぐらいスライドを作りました。役割分担ができたので思っていたより順調です。明日は発表ですが、堂々と楽しく発表できるように頑張りたいです。今回がラストで悲しいですがとても楽しかったです。
  • いろいろな問題がグラフの問題にできるということが分かった。最小カット・最大フローを使えば色々な問題が同値であることが分かる。
  • 今日はほとんどスライド作りだったので、自分で考えることが多く大変でした。エルキャスは、自分が今まで知らなかったことをたくさん教えてもらえてとても楽しかったです!明日の発表頑張りたいと思います。
  • 入り口が3つあるのを始点を1つにするためにどうすればよいかについて別に点をつくって入り口に矢印を伸ばせばいいことは思いついたがそれが3本だと限定要因になってしまうことの解決策は思いつかなかった。
  • 今回は畳パズル・座布団パズル問題に関連した様々な問題を取り扱い、また、Powerpoint資料の作成を行った。明日の発表会に向け、全8回の講義で学習したことを他の受講生に伝えられるように頑張りたい。
  • 畳パズルの問題の考え方が他の問題(座布団、防水ネット、…)にもそのまま応用できることが分かりました。資料作りでは慌ただしくなりましたが学んだことをきちんと伝えられるようにがんばります。
  • 最終回で、スライド作りがメインとなりました。今までやってきたことをまとめる際にも、数理最適化について再発見がありました。明日は良い発表ができればと思います。

平成27年度以前の
実施レポート

平成28年度以降の
実施レポート