長さ x 幅 で定義された複数のサイズのビンがあるとしましょう。それらは「原材料」のサイズと呼ぶことができます。
原材料の量を最小限に抑えるために、その原材料から一定量のテーブル (長方形、ギロチン形式) を切り取る必要があります。
ビンのサイズが同じではないため、それらの値を反映するために、何らかの方法で因数分解するか、優先順位を付ける必要があります。したがって、ビンが大きいほど、明らかに「より高価」になります。
私はこれが NP 完全問題であることを知っており、多項式時間での決定論的アルゴリズムを期待していません。
問題を解決するアルゴリズムが必要です。
どんな提案も役に立ちます！
ありがとう
さて、基本は次のとおりです。まず、良さ関数を適切に定義する必要があります。その後になって初めて、あなたの問題は明確に述べられていると見なすことができます。マテリアルプレート上の長方形のレイアウトを「配置」と呼びましょう。goodnes関数は、アレンジメントのドメインから実数のドメインにマップする必要があります。たとえば、大きいほど良いと言えます。関数は、指定されたアレンジメントで「浪費された」マテリアルの量に応じて減少し、アレンジメントによって満たされる長方形の量と値に応じて増加する必要があります。繰り返しますが、あなたはその善の関数、つまり、材料の相対的な価値と個々の長方形の価値を定義しなければならない人です。あなたが言うように、それは「大きいほど良い」ということわざを満たします。あなたはそれを定量化する必要があります。
これを行うと、多数のアルゴリズムが開きます。最初のアルゴリズムはランダムアルゴリズムです。重なり合わない配置または長方形をマテリアルのシートにランダムに分散し、その良さを評価してメモリに保存します。これを十分に何度も行った後、最適なものを選択します。このアルゴリズムの改善点は、すでに適切な配置を選択し、長方形を少し「微調整」して、もう1つの小さな長方形用のスペースを確保することです。それが、ディランがシミュレーテッドアニーリングを使用することによって意味する可能性があることです。そしてところで。シミュレーテッドアニーリングに関するウィキペディアのページを読まないでください。頭が混乱するだけです。
コメントへの回答：
ニック、明らかに、最初からすべての種類のビンを使用する必要があります。マテリアルの開始シートが（ビットマップまたはベクトルのいずれかとして）定義されているとします。次の手順を実行します。1。ポイントをランダムに選択します2.長方形のタイプをランダムに選択します3.回転をランダムに選択します4.長方形が収まらない場合は、ポイント1に戻ります。5。長方形が収まる場合は、配置しますマテリアルシートに配置し、同じ方法で2番目の長方形を配置してみます。6.次に、3番目、4番目など、多くの障害が発生し、行き止まりに達したと結論付けるまで続きます。7.結果の配置の良さを計算します。8。次の配置に進みます。
さて、あなたの切断機は一方向（工具回転なしの2軸）しか許さないので、長方形の回転を考慮する必要はないのではないかと思います。その場合、ポイントをどこかだけでなく、マテリアルシートの側面、またはシート上にすでにある別の長方形の側面にランダムに選択し、次の長方形をこのポイントに配置して、隣接する側面が次のようになるようにします。シートの側面または別の長方形。この場合（回転なし）、方向をランダムに選択し、垂直な壁に当たるまで、選択した方向に新しい長方形をシフトできます。そうすることで、コンピューティング作業を節約し、最初からより良い配置を作成できます。最後のステップは、まだ良さ関数を計算し、最良のものを選ぶことです。