1．は　じ　め　に

　VLSI CADは，集積回路が大規模化するにつれて，重要性が高まっていった．ここで，集積回路の製造上の制約を考慮すると，離散問題として考慮することが自然であった．そのため，ほとんどの問題が組合せ最適化問題として定式化されたきた．しかし，これらの定式化された問題は，大多数がNP-困難である⁽¹⁾．その対応として，数多くの解法が提案されたきた．

　近年，計算機性能の飛躍的な向上とその上で動作する高性能なアルゴリズムの開発により，VLSI CADをはじめとする組合せ最適化問題に，新たな解法の利用がなされるようになってきた．本稿では，モンテカルロ木探索（MCT）と制約充足問題を取り上げ，これらの組合せ最適化問題への適用についての一例を示す．

2．VLSI設計における組合せ最適化問題

　1．で述べたように，CAD等の問題は組合せ最適化問題として定式化される．VLSI設計で発生する問題も含めて，組合せ最適化問題において，NP-困難である問題に対しては，現実的な時間で解を得ることはできないと予想されている⁽²⁾．そこで，これまで，多数の解法が提案されてきた．これらの解法は，出力される解質に応じて，①厳密解法，②近似解法，③発見的手法，等にクラス分けされる．厳密解法は，出力される解が最適解であることが保証される反面，解が得られるまでの時間は問題の入力サイズの多項式を超える計算時間を認める解法である．以前は，理論的な側面が強調されていたが，最近，SATソルバ⁽³⁾やILPソルバ^(4),(5)の性能向上が著しく，実用的にも注目されている解法である．近似解法は，厳密解法よりも高速に，かつ，出力解の最適解からの劣化度合いが理論的に保証される解法である．理論的には非常に興味深い手法であるが，実際には，この性能を保証できる問題が余り存在せず，実用的とは言えない状況である．そして，発見的手法は，実行時間が実用的である反面，解質に対する保証がない手法である．この発見的手法の性能評価は，ベンチマークと呼ばれる入力に対する解で行われることが一般的である．また，メタヒューリスティックと呼ばれる確率を用いた手法，例えば，Simulated Annealing（SA）法⁽⁶⁾やGenetic Algorithm（GA）法⁽⁷⁾等は，得られる解質の良さと適用の容易さから広く利用されてきた．これらは無限の計算時間を掛ければ，確率的に最適解に到達可能であることが証明されている．一方で，ある程度の時間を掛けないと，良質な解を得ることができない．