Optimisation d'un problème de stationnement. Quels algorithmes dois-je utiliser pour adapter le plus grand nombre de voitures dans le lot?

Question

Quels algorithmes (force brute ou non) utiliserais-je pour mettre autant de voitures (supposons que toutes les voitures sont de la même taille) dans un stationnement de sorte qu'il y ait au moins une sortie (du conteneur) et une voiture bloqué. Ou quelqu'un peut-il me montrer un exemple de ce problème résolu par programmation. Le parking varie en forme serait bien, mais si vous voulez supposer que c'est une forme invariante qui est bien. Supposons que la distance parcourue dans le stationnement ne soit pas un facteur (bien que ce soit tout à fait génial s'il s'agissait d'un facteur pondéré au nombre de voitures dans le lot).

Autre édition: Supposons que 2 dimensions (pas de grues ou de conduire sur les voitures).

Autre édition: Vous ne pouvez pas déplacer les voitures une fois qu'elles sont garées (ce n'est pas un parking avec voiturier).

Answer 1

Eh bien, simplifions/concrétisons un peu. Supposons que nos voitures sont des carrés unitaires, le parking est N x N, et nous devons entrer/sortir du coin inférieur gauche. Un modèle simple obtient le lot presque 2/3 des voitures (indiquée pour 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| 
      | 
    -----------+ 

Je peux prouver que le mieux que vous pouvez éventuellement faire est d'obtenir le lot 2/3. Imaginez que vous construisez les espaces vides en commençant par un garage complètement plein et en conduisant une voiture (actuellement joignable) une à la fois. Chaque fois que vous retirez une voiture, vous produisez jusqu'à 3 voitures nouvellement joignables, et enlevez une voiture joignable une seule fois (maintenant un espace vide). Donc, pour chaque espace que vous faites, vous créez au plus 2 voitures plus accessibles. Pour faire 2/3 N^2 voitures accessibles, vous devez faire au moins 1/3 N^2 espaces, et c'est tous les carrés que vous avez. Ainsi, vous pouvez remplir le garage au 2/3 maximum. Le motif simple ci-dessus est asymptotiquement optimal, sa densité se rapprochant des 2/3 de N -> infini. (Un peu ennuyeux, j'espérais qu'un motif ressemblant à un arbre ferait mieux.)

Answer 2

Votre définition de l'efficacité est-elle le plus grand nombre de places de stationnement dans un lot d'une taille et d'une forme données (en supposant que chaque voiture peut être emmenée sans déplacer d'autre voiture)? Si c'est le cas, c'est un problème d'empaquetage, pas un problème de sac à dos, et cela me semble NP, mais la gamme de solutions pour un lot réel est si petite qu'elle pourrait être résolue avec une recherche exhaustive pratique.

Answer 3

Je pense qu'il peut être techniquement NP complet. Mais je pense que vous pourriez développer un ensemble de solutions intelligentes, en construisant chacune de l'expérience avec la dernière, et en choisissant algorithmiquement la meilleure solution parmi l'ensemble calculé. Vous ne pouvez peut-être pas prouver que c'est la meilleure solution possible. Mais d'un point de vue pratique, vous avez un parking optimisé, alors est-ce vraiment important que, compte tenu d'un laps de temps infini, vous auriez serré 3 voitures de plus?

Answer 4

Ceci est fondamentalement équivalent à bin-packing, avec l'exigence supplémentaire qu'une sortie soit dans un endroit particulier et que toutes les voitures puissent sortir - ce qui est en soi un problème difficile! Donc, votre problème est au moins NP-difficile.