第３回研究会（２００６年９月３０日（土） １４時 〜）講演概要
会場： 上智大学 四谷キャンパス １１号館３階 １１−３０５
講演者：
降旗 大介 氏 （大阪大学）
タイトル：
整数制約問題の差分法化 --離散問題と数値解析の融合のこころみ--
概要：整数制約問題に対し，定義域のグラフを離散化した空間としてペナ ルティ法と組み合わせ，求解アルゴリズムを微分方程式の枠組みで 解釈することを考える．離散問題を数値解析の文脈で解釈できるた め，系の性質保存性などをもつ，変わった性質のアルゴリズムが提 案できる. 当日は，グラフの彩色問題についての求解例を示す．
講演者：
梅谷 俊治 氏 （電気通信大学）
タイトル：
多角形詰込み問題に対するメタ戦略
概要： 多角形詰込み問題は，与えられた多角形を2次元平面上の領域内に重なりなく 配置する問題であり，自動車の板金型抜きや服飾のパターン切出しなど，製造 業の多くの分野に応用を持つ． 本問題は，設計工学や計算幾何の分野で比較的古くから研究されてきたが，多 角形の重なり判定一つを取っても，非常に複雑で多くの計算量を要するため， これまで現実の問題に適用できる実用的な解法はほとんどなかった． しかし，近年では，計算幾何や数理計画の手法を用いた様々な解法が研究され ており，計算機の性能向上も相まって，実用的な規模の問題例に対して歩留り の良い解を現実的な計算時間で求める解法もいくつか提案されている． 本講演では，メタ戦略を中心に多角形詰込み問題に対する最新の近似解法につ いて報告する．
ホーム
Copyright, S@CO All rights reserved, 2006.
