「位相的特徴量に基づく平面ポリオミノ箱詰め問題の解法」（Vol.43，No.12）

［論文概要］
　VLSIフロアプランや板金板取などを含む配置問題に関する研究の一環として，平面ポリオミノ箱詰め問題を取り上げた．この解法として，ピース配置に関わる位相的特徴量の潰し合いに着目した配置手順発見のための大域的な探索手法を開発した．この手法の中身は空間的な評価としての“`盤面の評価”とそれに基づく手順の評価としての“攻めての評価”を活用して，最も有望な順序でピースを選択し配置するアルゴリズムからなっているが，本論ではさらに，原問題を拡張して二つの最適化問題を派生させ，これらについても前記アルゴリズムをベースとした解法を構成した．

［推薦理由］
　本論文は，VLSIプロアプランのための手法を開発することを目的とし，平面ポリオミノをピースとする配置問題の解法を与えている．この種の問題は，探索木の大きさに比べ解の数が極端に少ないことが多く，場合によってはただ一つの最適解しか存在しない．そのため，従来の遺伝的アルゴ リズムやシミュレーティッドアニーリング法は有効に働かない場合が多く，実用的な面からも最適解を与える解法の研究は重要である．著者らは，ピース形状の位相的特徴量を用いた可能解の存在条件から，ピースの配置に関して大域的な整合性チェックを可能とする解法を与えた．さらに箱詰 め途中の盤面の評価，ならびに，次に配置するポリオミノの選択にエントロピー概念が有効に働くことを理論と実験において示した．本論文は，平面ポリオミノ箱詰め問題の解法を，単なる数学パスルという枠を超えて，一般的な定型ピースの配置問題に対して有効に働く新しい高速な解法を 提案しており，その研究成果は論文賞に値する．

村井　保之君 　1960年生．1999年神奈川工科大学大学院工学研究科情報工学専攻博士前期課程修了．2002年同大学大学院工学研究科情報工学専攻博士後期課程満期退学．2003年同大学情報学部助手．空間の認識に関する研究開発に従事．電子情報通信学会会員．

巽　久行君 　1956年生.1985年明治大学大学院工学研究科博士後期課程修了.工学博士.1986年神奈川工科大学情報工学科助手.2002年筑波技術短期大学助教授.多値論理,ニューラルネットに興味を持つ.電子情報通信学会,日本ファジイ学会,米国IEEE各会員.

徳増　眞司君 　1940年生．1963年横浜国立大学工学部卒業.(株)日立製作所日立研究所入社.1973～74年米国スタンフォード大学大学院OR学科修士課程修了.1984年工学博士（京都大学）．1995年神奈川工科大学情報工学科教授.生産情報システム,システム工学,OR,計算幾何学の研究に従事.米国 IEEE,OR学会,電子情報通信学会各会員