ホーム / 学科の紹介 / 研究室・教員 / 離散数理分野

離散数理分野

計算科学の基礎理論の研究として、離散最適化問題の数学的性質・計算の複雑さの解明や高速な離散最適化アルゴリズムの設計を行うとともに、これらの成果を現実問題へ応用する研究を行っている。 具体的な応用例には、2〜3次元物体の最適配置、VLSIチップ内の配置・配線問題、大規模データに対する論理的解析および知識獲得、グラフ描画を用いた情報可視化、最適ルートの決定、配送計画スケジューリングなどが挙げられる。 これらのうち関連するアルゴリズムを統合した問題解決システムを構築することも目指している。

教員

  • 教授:永持 仁
  • 助教:SHURBEVSKI, Aleksandar

研究内容

離散最適化問題の複雑さの解明とアルゴリズムの開発

  • グラフ・ネットワーク問題に対する高性能アルゴリズムの発見
    離散構造を表現する基本モデルであるグラフの数学的性質の解明
  • メタヒューリスティクスによる問題解決システムの構築
    電気・機械、造船、鉄鋼メーカーにおける生産計画、スケジューリング、配送計画など現実問題への適用
  • データマイニング・知識発見  蓄えられた大量のデータから、意味のある情報を効果的に抽出

巡回セールスマン問題

or_amp_p_01.gif

セールスマンが各都市を一度ずつ訪問し、元の場所に戻ってくるときの総移動距離を最小化する問題。
図は、アメリカ合衆国 532 都市の最短巡回路。

長方形詰込問題

or_amp_p_02.gif

与えられたすべての長方形をできるだけ隙間なく2次元平面上に配置する問題。 図は、ランダムな配置を、メタヒューリスティクスと呼ばれる手法により改善した様子。

研究室ウェブサイト

http://www-or.amp.i.kyoto-u.ac.jp/