60

放物線があるとしましょう。今では、すべて同じ幅の棒もたくさん持っています (はい、私の描画スキルは素晴らしいです!)。放物線が使用するスペースをできるだけ最小限に抑えるために、これらの棒を放物線内に積み重ねるにはどうすればよいですか? これはナップザックの問題のカテゴリに分類されると思いますが、このウィキペディアのページでは、現実世界の解決策に近づくことはできません。これは NP 困難な問題ですか?

この問題では、垂直領域を含む、消費される領域 (例: Integral) の量を最小限に抑えようとしています。

ここに画像の説明を入力

4

7 に答える 7

23

processing.jsと HTML5 キャンバス を使用して、JavaScript でソリューションを作成しました。

このプロジェクトは、独自のソリューションを作成する場合の出発点として適しています。2 つのアルゴリズムを追加しました。入力ブロックを最大から最小に並べ替えるものと、リストをランダムにシャッフルするものです。次に、各アイテムは、一番下 (最小のバケット) から始めて、収まる十分なスペースができるまで上に移動してバケットに配置されます。

入力のタイプによっては、ソート アルゴリズムが O(n^2) で良い結果をもたらす場合があります。ソートされた出力の例を次に示します。

ソートされた挿入

これが順序アルゴリズムの挿入です。

function solve(buckets, input) {
  var buckets_length = buckets.length,
      results = [];

  for (var b = 0; b < buckets_length; b++) {
    results[b] = [];
  }

  input.sort(function(a, b) {return b - a});

  input.forEach(function(blockSize) {
    var b = buckets_length - 1;
    while (b > 0) {
      if (blockSize <= buckets[b]) {
        results[b].push(blockSize);
        buckets[b] -= blockSize;
        break;
      }
      b--;
    }
  });

  return results;
}

github のプロジェクト - https://github.com/gradbot/Parabolic-Knapsack

これはパブリック リポジトリなので、自由に分岐して他のアルゴリズムを追加してください。興味深い問題なので、今後追加するかもしれません。

于 2011-03-22T03:55:14.843 に答える
15

簡略化

まず、問題を単純化して、次のようにします。

  • 軸を切り替えて互いに追加すると、x2 の成長が得られます
  • 閉区間の放物線であると仮定し[a, b], where a = 0、この例ではb = 3

b(間隔の 2 番目の部分) とw(セグメントの幅)が与えられたとしましょうn=Floor[b/w]。この場合、リーマン和を最大化する自明なケースが存在し、i 番目のセグメントの高さを取得する関数は次のとおりf(b-(b*i)/(n+1)))です。実はこれは仮定であり、100%確実ではありません。

関数実数値 の17閉区間のセグメントの最大化された例:[0, 3]Sqrt[x]

ここに画像の説明を入力

この場合のセグメントの高さ関数はRe[Sqrt[3-3*Range[1,17]/18]]で、値は次のとおりです。

  • 正確な形式:

{Sqrt[17/6]、2 Sqrt[2/3]、Sqrt[5/2]、Sqrt[7/3]、Sqrt[13/6]、Sqrt[2]、Sqrt[11/6]、Sqrt [5/3]、平方根[3/2]、2/平方根[3]、平方根[7/6]、1、平方根[5/6]、平方根[2/3]、1/平方根[2]、 1/平方[3]、1/平方[6]}

  • おおよその形:

{1.6832508230603465, 1.632993161855452, 1.5811388300841898, 1.5275252316519468, 1.4719601443879744, 1.4142135623730951, 1.35400640077266, 1.2909944487358056, 1.224744871391589, 1.1547005383792517, 1.0801234497346435, 1, 0.9128709291752769, 0.816496580927726, 0.7071067811865475, 0.5773502691896258, 0.4082482904638631}

あなたがアーカイブしたのは、ビンが部分的に満たされたビンパッキングの問題です。

bを見つける

が不明な場合、または私たちのタスクは、最初のバンチ フィットを形成するすべてのスティックの下でb可能な限り小さいものを見つけることです。b次に、少なくともb値を次のように制限できます。

  1. 下限 : セグメントの高さの合計 = スティックの高さの合計の場合
  2. 上限 :セグメントの数 = スティックの数 最長のスティック < 最長のセグメントの高さ

見つけるための最も簡単な方法の 1 つは、解決策が存在する場合に検索bでピボットを取ることです。(higher limit-lower limit)/2次に、それが新しい上限または下限になり、必要な精度が満たされるまでプロセスを繰り返します。

探している場合b、正確な結果は必要ありませんが、最適ではなく、効率的なアルゴリズムを使用して実際に比較的近いピボットポイントを見つけると、はるかに高速になりますb。

例えば：

  • スティックを長さで並べ替える: 大きいものから小さいものへ
  • 最初のビンに「最大のアイテムを入れる」ことを開始します。
于 2011-02-23T22:48:59.497 に答える
12

これは、複数のナップザックを持つことと同等であり (これらのブロックが同じ「高さ」であると仮定すると、これは各「行」に 1 つのナップザックがあることを意味します)、したがってビン パッキング問題のインスタンスです。

http://en.wikipedia.org/wiki/Bin_packingを参照してください。

于 2011-02-22T22:37:38.353 に答える
2

ビンパッキングと同等であると確信しています：

非公式の削減

最も広い行の幅の x にして、ビンを 2 倍の大きさにし、行ごとに 2x-rowWidth の大きさのプレースホルダー要素を作成します。したがって、2 つのプレースホルダー要素を 1 つのビンにパックすることはできません。

パラボリック ナップザックのビン パッキングを減らすには、サイズ width-binsize の必要なビンサイズよりも大きいすべての行のプレースホルダー要素を作成するだけです。さらに、行全体を埋める binsize より小さいすべての行のプレースホルダーを追加します。

これは明らかに、問題が NP 困難であることを意味します。

他のアイデアについては、こちらをご覧ください: http://en.wikipedia.org/wiki/Cutting_stock_problem

于 2011-03-22T14:23:18.933 に答える
2

これらのスティックを放物線内に積み重ねて、使用する (垂直) スペースをできるだけ最小限に抑えるにはどうすればよいですか?

他のビンパッキングの問題と同じように対処してください。これらのアルゴリズムは問題に固有のものではないため、メタヒューリスティック(タブー検索、シミュレートされたアニーリングなど) を適用します。

たとえば、 Drools Plannerでクラウド バランスの問題(= ビン パッキングの一種)から始めるとします。すべての棒の高さが同じで、2 本の棒を重ねる間に垂直方向のスペースがない場合、変更する必要はほとんどありません。

  • に名前を変更ComputerしParabolicRowます。そのプロパティ (CPU、メモリ、帯域幅) を削除します。一意にしますlevel(0 が一番下の行です)。の数を作成しますParabolicRows。
  • Processに名前を変更Stick
  • ProcessAssignementに名前を変更StickAssignment
  • Sticksに割り当てられたすべての合計に十分なスペースがあるかどうかを確認するように、ハード制約を書き直しますParabolicRow。
  • ソフト制約を書き直して、最高levelの を最小化しますParabolicRows。
于 2011-02-23T08:42:20.283 に答える
1

レベルがさまざまな高さにある可能性があるという事実に言及した人への小道具 (例: スティックが 1 の「太い」レベルであると仮定すると、レベル 1 は 0.1 単位から 1.1 単位になるか、代わりに 0.2 から 1.2 単位になる可能性があります)

もちろん、「複数のビンのパッキング」方法論を拡張して、任意の小さな増分をテストすることもできます。(例: 0.0、0.1、0.2、... 0.9 で始まるレベルで複数のビンパッキング方法論を実行し、最良の結果を選択しますが、何らかの方法論がない限り、無限の時間の計算に行き詰まるようです。 「正しく」取得したことを確認します (または、より正確には、すべての「行」が内容に関して正しいことを確認します。その時点で、放物線の端に達するまでそれらを下にシフトできます)。

また、OP では、スティックを水平に配置する必要があることを指定していませんでしたが、おそらく OP はそれらの甘い絵でそれを暗示していました.

このような問題を最適に解決する方法はわかりませんが、スティックをランダムに配置して放物線の「内側」にあるかどうかをテストできる場合があり、水平方向のみに依存する方法論を打ち負かすでしょう.行。(1 本の長い棒で埋めようとしている狭い放物線の場合を考えてみましょう。)

私はそこにそれらをすべて投げ入れて振るだけだと言います;）

于 2013-03-08T16:50:06.857 に答える
1

ほとんどの場合、これは 1-0 ナップサックまたはビン パッキングの問題です。これは NP 困難な問題であり、おそらくこの問題は理解できず、説明することもできませんが、貪欲なアルゴリズムで最適化できます。phpclasses.org で私の php クラスの bin-packing を作成するために使用するhttp://www.developerfusion.com/article/5540/bin-packingに関する有用な記事を次に示します。

于 2011-03-22T14:28:13.803 に答える