2016年06月02日胡 艶楠 助教（計算機数理科学専攻）2016/03/1着任

2016年3月に計算機数理科学専攻の助教に着任しました胡艶楠と申します．

　私はこれまで主に配置問題に対する解法の研究を行ってきました．
配置問題とは，配置すべきもの（製品と呼ぶ）の集合と配置される空間が与えられたとき，製品を空間内に，様々な制約の下で効率よく配置する問題です．この問題は，古典的な組合せ最適化問題の１つであり，これまで多くの研究がなされてきました．最近では，工学的に重要な意味を持つ，長方形配置問題，多角形詰込み問題，直方体詰込み問題に対する研究が盛んです．計算の複雑度という観点から見ると，ほぼ全ての配置問題はNP困難に分類され，多項式時間で厳密な解を求める手法はおそらく存在しません．このような状況にあるため，性能の良い近似解法の開発が非常に重要であると考えられています．

　2次元配置問題について，私の研究では一般の図形配置問題の中でも特に大規模な問題に焦点を絞り，性能の高い近似解法の構築を目的としました．曲線を含む一般の図形の配置問題は非常に多くの応用を持ちますが，十分な研究が行われていません．従来研究の多くは，単純な図形を対象とし，人工的に作られたベンチマークによって評価されるなど，本問題の実用上の重要性を考慮すると不十分な点がありました．この問題を扱いづらくしている原因は，形状の取り扱いの難しさです．一般の図形配置問題では，図形の配置に対して重なりがあるか否かを判定する際，計算コストの高い計算幾何的な処理が必要となり，さらに，それに起因する数値誤差が問題となります．そのような状況から，実用的に高速なアルゴリズムを作ることが非常に困難であると考えられています．

　私の研究では，垂直もしくは水平線分で描かれるレクトリニア多角形を長方形の領域に詰め込む問題に対して，空の状態からひとつずつ多角形を配置する構築型解法の高度なデータ構造を駆使した効率的な実装を提案し，1万個程度の多角形を2秒以内で配置することができました．また，ビットマップ図形を効率的に扱うためのデータ構造を提案しました．これらの成果を利用して，一般の図形配置問題をビットマップ図形に近似して解く方法を提案しました．その結果，既存研究では100程度の図形の配置に1200秒以上かかってしまうのに対し，本研究の手法は，図形数が約１万個ある問題例に対しても100秒以内で良質の解を構築できました．

• 

　今後の研究としては，主な研究テーマとして行ってきた配置問題に関する研究を引き続き実施し，さらに掘り下げた研究を行いたいと思っています．
また，配置問題に限らず実用上重要な研究課題にも取り組んでいきたいと思います．