6

少なくとも 1 つの出口 (コンテナーからの) があり、車がブロックされないように、駐車場にできるだけ多くの車 (すべての車が同じサイズであると仮定) を配置するために使用するアルゴリズム (総当たりかどうか) を使用します。または、この問題をプログラムで解決した例を誰かに見せてもらえますか。

駐車場の形状が変化するのはいいことですが、不変の形状であると想定したい場合は問題ありません。

別の編集: 駐車場での走行距離は要因ではないと仮定します (ただし、駐車場内の車の数に重み付けされた要因であれば、それはまったく素晴らしいことです)。

別の編集: 2 次元を仮定します (クレーンや車の運転はありません)。

別の編集: いったん駐車すると、車を移動することはできません (係員付き駐車場ではありません)。

4

4 に答える 4

5

さて、少し単純化/具体化しましょう。私たちの車が単位正方形であり、駐車場がN x Nであり、左下隅から出入りする必要があると仮定します。単純なパターンでは、車でほぼ2/3がいっぱいになります（N = 12で表示）。

+------------+
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
             |
  -----------+

私はあなたがおそらくできる最善のことはロットを2/3いっぱいにすることであることを証明することができます。完全に満員のガレージから始めて、（現在到達可能な）車を一度に1台ずつ運転して、空きスペースを増やすことを想像してみてください。車を削除するたびに、最大3台の新しく到達可能な車を作成し、1台の到達可能になった車（現在は空きスペース）を1台削除します。したがって、作成するスペースごとに、最大2台の到達可能な車を作成します。2/3 N ^ 2の到達可能な車を作るには、少なくとも1/3 N ^ 2のスペースを作る必要があり、それがあなたが持っているすべての正方形です。したがって、ガレージを最大2/3まで満たすことができます。

上記の単純なパターンは、密度がN->無限大として2/3に近づくため、漸近的に最適です。（ちょっと退屈ですが、木のように見えるパターンがうまくいくことを望んでいました。）

于 2010-05-15T05:46:10.623 に答える
1

これは基本的にbin-packingと同等ですが、出口が特定の場所にあり、すべての車が出ることができるという要件が追加されています。これ自体が難しい問題です。

したがって、あなたの問題は少なくとも NP 困難です。

于 2010-05-13T18:17:53.820 に答える
0

技術的にはNP完全なのかもしれないと思います。しかし、それぞれが最後の経験から構築された一連のインテリジェントなソリューションを開発し、計算されたセットからアルゴリズム的に最適なソリューションを選択できると思います。それが最善の解決策であることを証明できない場合があります。しかし、実用的な観点からは、最適化された駐車場があるので、無限の時間が与えられた場合、そこにさらに 3 台の車を詰め込むことは本当に重要でしょうか?

于 2010-05-13T17:57:15.670 に答える
0

効率の定義は、特定のサイズと形状の駐車スペースの最大数ですか (他の車を動かさずに各車を追い払うことができると仮定します)? もしそうなら、それはパッキングの問題であり、ナップザックの問題ではなく、NP のように聞こえますが、実際のロットの解の範囲は非常に小さいため、実用的な徹底的な検索で解決できます。

于 2010-05-13T17:46:18.670 に答える