奇妙なビンパッキングの問題を解決しようとしています。元の問題へのリンクはこちらです (長い質問で申し訳ありません。ご理解いただきありがとうございます)。
私は次のように問題を繰り返しています: 区画化された Panel の描画を生成するアプリケーションを作成しようとしています。
N 個のキュービクル (2D 長方形) があります (N <= 40)。各キュービクルには、最小の高さ (minHeight[i]) と最小の幅 (minWidth[i]) が関連付けられています。パネル自体にも MAXIMUM_HEIGHT 制約があります。
これらの N 個のキュービクルは、各キュービクルで上記の制約が満たされるように、列方向のグリッドで上下に積み重ねる必要があります。
また、各列の幅は、その列の各キュービクルの最大 minWidths によって決まります。
また、各列の高さは同じでなければなりません。これにより、パネルの高さが決まります
任意の列に残っている空きスペースに予備のキュービクルを追加したり、指定された最小値を超えて任意のキュービクルの高さ/幅を増やすことができます. ただし、キュービクルを回転させることはできません。
OBJECTIVE: TO MINIMIZE TOTAL PANEL WIDTH.
パネルの MAXIMUM_HEIGHT = 2100mm、最小幅範囲 (350mm から 800mm)、最小高さ範囲 (225mm から 2100mm)
選択した答えに従って、整数線形計画法を定式化しました。ただし、問題の組み合わせの性質を考えると、ソルバーは N > 20 で「ハング」しているように見えます。
現在、回避策を実装しようとしています。
キュービクルは、minWidths の降順で並べ替えられます。minWidths が等しい場合は、minHeights の降順で並べ替えられます。次に、 First Fit 減少ヒューリスティック
を使用して解決します。これにより、合計パネル幅の上限と、現在の列幅のリストが得られます。
今、私はパネルの幅を小さくして、フィーダーをその小さいサイズのパネルに合わせようとしています. （フィーダーが特定の列幅のリストに効率的に収まるかどうかを確認できます）
パネルの幅は、次の方法で小さくすることができます:
1. 任意の列を取り、次に低い minWidth フィーダーの列に置き換えます。列がすでに最小の minWidth である場合は、それを削除して確認してください。
2. 任意の列を取り、それをより高い minWidth フィーダーの列に置き換え、別の列を削除します。
3. 他の方法で、誰かが指摘してくれると嬉しいです。
最初の方法を正しく実装しました。以下はコードです。ただし、別の方法でコードを正しく記述することはできません。
for ( int i = 0; i < columnVector.size(); i++ ) {
QVector< Notepad::MyColumns > newVec( columnVector );
if ( newVec[i].quantity > 0
&& ( i > 0 || newVec[i].quantity > 1 ) ) {
newVec[i].quantity--;
if ( i < columnVector.size() - 1 )
newVec[i+1].quantity++;
float fitResult = tryToFit( newVec, feederVector );
myPanelWidth = fitResult ? fitResult : myPanelWidth;
if ( fitResult ) { // if feeders fit, then start the iteration again.
columnVector = newVec;
i = -1;
}
}
}
どんな助けでも大歓迎です。
ありがとう