• 講演者:降旗 大介 氏(大阪大学)
    • 題目:整数制約問題の差分法化 –離散問題と数値解析の融合にむけて–
    • 日時:平成18年7月10日(月)16:30〜17:30

様々な離散問題を扱う離散数学という分野は応用数学の精華の一つであり,その発展,成果には目覚ましいものがある. 一方,連続数学を主に取り扱う数値解析の分 野においてももちろん,数多くの研究が日々発展をとげている. これら二つの分野 をつなぐことができれば,より多くの発展が見込まれる.

そこで,整数制約問題,組み合わせ最適化の一部に対し,問題の定義域であるグラフを空間を離散化したもの,ととらえ, ペナルティ法と組み合わせることにより, 求解アルゴリズムを微分方程式の枠組みで解釈することを考えた. こうすることで, 微分方程式に対する膨大な数値解析の知見が利用できるようになり,離散問題を数 値解析の手法で解くことが可能になる. この際,系の性質の数値的保存という数値解析分野での成果などを取り込むことに より,通常のアルゴリズムより多少変わった性質のアルゴリズムが提案できる.

この考え方に基づいて,まずは一番シンプルなグラフの彩色問題について数値解析 で求解した例を当日は示す.

34 images

[<6>]

  • seminar/2006/008.txt
  • 最終更新: 2017/11/17 17:24
  • by 127.0.0.1