モンテカルロ法がどのようなものであるかは、ここに分かりやすい説明があります。
この中に、モンテカルロ法を使った円周率πの求め方が紹介されていますが、ここで大切なのは、ランダムに発生させた事象を評価して、採択するか棄却するかを決めている事です。
LSIの論理セルも、これと似たような方法で配置を求めていきます。まず最初に、全くランダムにすべてのセルをLSI上にばら撒きます。次に1つの論理セルに注目して、他の論理セルと交換した場合の評価を行います。改善されれば採択、されなければ棄却します。評価は、仮想配線長が短くなるかどうかで判断します。これを満足できる結果が出るまで、延々と繰り返すのです。
この方法には、二つの欠点があります。一つ目は膨大な量の計算をしなければならない事です。特に大規模なLSIになればなるほど、指数関数的に計算量が増えますから、常識的な時間内で結果が得られるように考慮しなければなりません。
二つ目は、前にも述べましたが、最適解ではなく極小解に陥りやすい事です。いったん極小解に陥ると、そこから抜け出すには大きなエネルギーが必要になります。そしてどの極小解に陥るかは、初期条件に大きく影響されます。最適解が求まらないまでも、より良い極小解を導く為には、優れた初期条件を与えてやる事が重要です。
この事を、文学的に表現すると、次のようになります。
一つの最適解と無数の極小解が、広がりを持った空間に漂っています。一つの極小解を見つけた人は、さもそれが最適解だと信じて喜ぶのですが、すぐに別のもっと良い解がある事に気づくと、今度はその新しい解を最適解と信じるのです。そして、それを幾度となく繰り返すうちに最適解の存在さえ疑うようになり、もはや本当の答えを追求する事を諦めてしまうのです。