1

3次元ナップザック問題を解きたいです。

幅、高さ、長さ、値が異なる箱がいくつかあります。指定されたスペースがあり、最適な利益が得られるように、そのスペースにボックスを配置したいと考えています。ブルートフォースを使ってやりたいと思います。

私はJavaでプログラミングしています。私は再帰でそれをやろうとしたので：

public void solveBruteforce(double freeX, double freeY, double freeZ) {
   for(int i = 0; i < numOfBoxes; i++) {
      for(int j = 0; j < BoxObject.numOfVariations; j++) {
         if(possible to place box) {
            place(box);
            add(value);
            solveBruteforce(newX, newY, newZ);
         }
      }
   }
   remove(box);
   remove(value);
}

しかし、各行に異なる空き x、y、z があるという問題が発生します。

誰かがそれを行う別の方法を見つけるのを手伝ってくれませんか?

4

1 に答える 1

0

まず、octree を使用して、空間内のどこにあるかを追跡します。占有ツリーは 3D の 4-out-degree ツリーであり、すべてのノードに占有フラグがあり、空間を効率的に検索できる場所に分割します。これは、ある種のヒューリスティック検索を使用してボックスを配置したい場合や、あらゆる可能性を試している場合でも役立ちます。禁止された（密集した）配置をショートカットできます。

ブルートフォースは時間がかかります。ただし、それが必要な場合は、配置の順列を試すための順序を定義する必要があります。

多くの反復が必要になるため、スタックオーバーフローが発生するため、再帰はそれほど大きくありません。

最初のドラフトの代替案には、貪欲なアルゴリズムが含まれます。利益を最大化するボックス (たとえば、最大のもの) を取り、それを配置し、次に最大のボックスを取り、それに最適なものを見つけます。

しかし、考えられるすべての組み合わせを試したいとします。

def maximize_profit(boxes,space):
    max_profit = 0
    best_fits = list()
    while(Arranger.hasNext()):
        a_fit,a_profit = Arranger.next(boxes,space)
        if (a_profit == max_profit):
            best_fits.append(a_fit)
        elif (a_profit > max_profit):
            max_profit = a_profit
            best_fits = [ a_profit ]
    return best_fits, max_profit

アレンジャーを定義する方法についてのアイデアについては、対称に関して同一である配置を尊重して、#{space} の可能性から #{box} スロットを選択することを考えてください。あるいは、「フラッド フィル」メソッドでアイデアが得られるかもしれません。

于 2012-01-16T10:22:02.823 に答える