前回に引き続き最適化骨くんのアルゴリズム解説を行います。
今日は、親長方形に複数の子長方形を敷き詰める問題について考えることにします。
また今回、以下の条件を加えます。
- 子長方形の面積は親長方形の面積と同じかそれより小さい
- 敷き詰められる長方形の向きは固定
１つ目条件は話を単純にするために設定しています。
２つ目の条件は、プリプレグから切り出す部品の繊維方向は予め決まっているため設定しています。
複数の長方形を敷き詰める
さて、親長方形の中に、どのようにして複数の子長方形を敷き詰めていけばよいでしょうか？
なんとなく思いつくのが、長方形の端の角から敷き詰めていく方法です。
+-----------A-------------+ +--B--+ +----C----+
| | | | +---------+
| | +-----+
| |
| |
+-------------------------+
- A: 親長方形
- B, C: 子長方形
上図の例で考えることにしましょう。
例えば、なんとなく、端から敷き詰めると下のようになります。
1. Bを端に詰める。
+-----------A-------------+ +----C----+
| | +---------+
| |
| +--B--+
| | |
+-------------------------+
2. Cを端に詰める。
+-----------A-------------+
| |
| +----C----+
| +------B--+
| | |
+-------------------------+
上のようにして、長方形AにB,Cを敷き詰めることができました。
なぜ、私はこの様に敷き詰めたのでしょうか？
長方形を敷き詰めて行く過程の、長方形AにBを詰めた直後に注目してみます。
次に行うのは長方形Cを、長方形Aに敷き詰めることです。
しかし、現時点で長方形Aには長方形Bが敷き詰められているので、Cを敷き詰める先は もはや長方形Aではありません。
つまり下図のような、多角形A'に長方形Cを詰めることになります。
+-----------A'------------+ +----C----+
| | +---------+
| |
| +-----+
| |
+-------------------+
長方形Cをどこへ詰めればよいでしょう。
今回の例では、Bを詰めた直ぐ上へ詰めましたが、これで良かったのでしょうか？
直感的に敷き詰めていきましたが、私はなぜこのようにして敷き詰めたのでしょう？
課題
上の例から主に２つの課題が挙げられます。
この課題をうまく解決できれば、長方形の中に複数の長方形を敷き詰める問題が解けそうです。
課題.1 長方形ではない残りの多角形に長方形を敷き詰める
例題では、途中でA'のような多角形へ、人間が考え、長方形Cを詰めていましたが、機械的に計算させるのは難しそうです[1]。
できれば今まで通り、長方形に長方形を入れる問題として考えたいです。
課題.2 詰めていく部品の順番
今回B, Cの順で詰めていきました。結果、残りの素材は下のようになります。
+-----------A1------------+
| |
| +---------+
| +---+
| |
+-------------------+
一方C, Bの順で詰めると下のようになります。
+-----------A2------------+
| |
| +-----+
| |
| +---+
+---------------+
例えばここへ、下のような長方形Dを詰めるとどうなるでしょう。
+-----------A1------------+ +-D-+
| | | |
| +---------+ | |
| +---+ | |
| | +---+
+-------------------+
+-----------A2------------+ +-D-+
| | | |
| +-----+ | |
| | | |
| +---+ +---+
+---------------+
残りの素材の形や、後々入れる長方形のことなどを考えると、現実的にはA1よりA2へDを詰めたようが良さそうです。
敷き詰める順番によって、次に部品を詰める場所が変わってくるため、どの部品から詰めて行くか考えることが重要になります。
今回は、なんとなく素材の端から部品を敷き詰めて行きました。
実際にはこれをプログラムとして機械的に計算させたいので、なんとかシステマチックに解く方法を考えなければなりません。
そのために、まずは今回挙げた２つの課題を解決しなれけばなりません。
次回は、これら課題の解決策について考えていきたいと思います。
1: 数学的に考えれば解ける方法がありそうです。ご存知であれば教えてください…。
