L'optimisation d'un parc de Stationnement Problème. Quels algorithmes dois-je utiliser pour s'adapter au plus grand nombre de voitures dans le lot?
Quels algorithmes (brute force ou pas) aurais-je utiliser pour mettre beaucoup de voitures (à supposer que toutes les voitures sont de la même taille) dans un parking alors qu'il y a au moins une ouverture de sortie (à partir du conteneur) et une voiture ne peut pas être bloqué. Ou quelqu'un peut-il me montrer un exemple de ce problème est résolu par programmation.
Le stationnement varie en forme serait bien, mais si vous voulez assumer c'est un invariant de la forme, c'est très bien.
Un Autre Edit:
Supposons que la distance de conduite dans le stationnement n'est pas un facteur (bien que ce serait vraiment génial si c'était pondérée du facteur du nombre de voitures dans le lot).
Un Autre Edit:
Supposons 2 Dimensions (pas de grues ou de conduite sur les voitures).
Un Autre Edit:
Vous ne pouvez pas déplacer des voitures une fois qu'elles sont garées (ce n'est pas un valet parking).
- Que voulez-vous dire "organiser un parc de stationnement"? Optimiser le choix de l'espace de chaque parkings? Optimiser l'aménagement de l'aire de stationnement? Quelles sont vos contraintes--sont toutes des voitures de la même taille? Ce géométrie sommes-nous travailler? Je pense que vous obtenez en avant de vous, vous ne donnez pas beaucoup de détails sur le problème que vous essayez de résoudre!
- J'ai voté pour le fermer. Raison: trop vague. Veuillez modifier pour ajouter plus de détails.
- et @Crétin, je me sens comme un Utilisateur Final de demander à un développeur pour un long métrage. Supposons que toutes les voitures sont de la même taille. Supposons qu'ils aient à sortir de l'aire de stationnement.
- Cette question est parfaitement bien comme il est. Je souhaite que je pourrais anti-vote.
- Allez les gars. ne pas fermer
- Lire la FAQ: "Éviter de poser des questions qui nécessitent une discussion prolongée". @ShaggyFrog. On peut toujours l'ouvrir de nouveau. En fait, si la question a un sens et il se ferme, je vais voter pour la réouverture.
- cela ne nécessite pas de longues discussions. Je savais exactement ce que l'OP a été de demander dès que j'ai lu la question. Il me semble que vous deux n'ont pas compris la question, et ont donc voté pour le fermer. Mais pas parce qu'il a été rédigé correctement, mais parce que vous ne comprenez pas le domaine. C'est une erreur.
- Je vous suggère d'aller lire la version 1 de la question (elle a été modifiée depuis). En tout cas, la version actuelle 3 exige également la discussion. Dans Adam propres mots: "je me sens comme un Utilisateur Final de demander à un développeur pour une fonctionnalité". Si vous savez exactement ce que l'OP est de poser des questions et je pense qu'aucune discussion, tout ce qui est nécessaire, bon pour vous. Je ne suis pas pyschic et je suis heureux avec ce que la compréhension de la lecture capacités, j'ai.
- Je n'ai pas le droit de voter pour fermer, mais pour être honnête, je ne suis pas sûr de comprendre ce que l'OP veut. Quel est exactement un parc de stationnement et ce qui est exactement une voiture, dans un contexte de programmation? Qu'est ce qu'une sortie? Pouvez-vous poster un exemple? Aussi, beaucoup plus claire des questions ont été fermés avant. Juste pour dire.
- si la question est maintenant de donner un sens, peut-être il est temps de déposer votre bulletin à proximité?
- voir ma réponse
- Je ne peux pas l'onu vote pour fermer. D'ailleurs, je ne veux pas. C'est pas encore assez précis.
- Grenouille: Considérons un parking qui ressemble à cela, seuls les plus:
_ | | _, où les voitures ne peuvent être placés sur un_face à un|. Il est assez évident que la solution est dans ce cas, donc, je suis franchement pas sûr de ce que l'OP est après tant comme il le dit "la forme peut changer, mais seulement si vous le voulez". Eh bien, je veux toujours que la forme donc, le problème est trivial. Je ne vois vraiment pas ce que sa question est. Quand vous dites "parking", je pense que de la vraie vie, les terrains de stationnement, pour lequel un algorithme glouton va trouver la solution optimale facilement. Utiliser des termes de programmation pour rendre cela moins vague. - si vous ne comprenez pas la question, alors vous pouvez toujours déplacer sur. Par exemple, c'est pourquoi je ne voudrais pas creuser dans la ASP.NET des questions sur un Débordement de Pile. Je ne sais pas comment répondre à ces questions.
- Grenouille: c'est exactement ce que je fais. Je viens de donner l'OP un avertissement que des questions de ce genre ont tendance à être fermés. Personnellement, je ne vais pas fermer cette.
- Parler de NP-Complétude pour une question ouverte, comme c'est un non-sens complet. Par exemple, je vais avoir un parking avec une grue attachée. Il suffit de ramasser les voitures et de les mettre. Complètement plein. Ou utiliser un tunnel comme une file d'attente, et si nous avons besoin de la 10e voiture, la première 9, et de les replacer dans par la conduite sur le toit du tunnel. De nouveau complet. 'Polynôme' algorithmes temps à mettre et enlever les voitures. Je pense que je vais prendre ShaggyFrog de la suggestion et de progresser.
- la façon dont la question est actuellement libellé est parfaitement raisonnable et compréhensible. Je suis d'accord que si c'était complètement vague avant, l'avertissement est justifiée. Mais il semble que l'OP a abordé la question.
- Je suis juste poser quelques techniques de comment je pourrais résoudre ce problème avec des références à des algorithmes. Je souhaite que je pourrais changer le titre et je re-poser la question, mais là encore, les questions sont censés être Wiki comme je ne veux pas perdre certaines des réponses. @Débile et @IVlad je suis désolé que je ne suis pas assez intelligent pour savoir comment facile ce problème est à résoudre, d'où la question.
- Le problème ici est que "ce problème" n'est pas défini correctement et qu'est ce que la discussion (au moins par moi) a été d'environ. Comme indiqué à la question est non-responsable et donc le vote pour le fermer.
- le problème est bien défini, comme indiqué actuellement. Il n'est certainement pas "de l'onu-responsable." S'il vous plaît, si vous ne comprenez pas le problème, alors vous devriez vous en aller loin de cette question.
Vous devez vous connecter pour publier un commentaire.
Eh bien, nous allons simplifier/concreteify un peu. Supposons que nos voitures sont de l'unité de places, le stationnement est N x N, et nous avons besoin d'entrer/quitter le coin inférieur gauche. Un modèle simple obtient le lot près de 2/3 plein avec des voitures (montré pour N=12):
Je peux prouver que le mieux que vous pouvez éventuellement faire est d'obtenir le lot 2/3 plein. Imaginez que vous construisez les espaces vides en commençant avec une pleine garage et la conduite d'une (joignable) voiture d'un à la fois. Chaque fois que vous supprimez une voiture, vous produire jusqu'à 3 nouvellement accessibles voitures, et enlever une fois accessible en voiture (maintenant un espace vide). Ainsi, pour chaque espace que vous faites, vous vous créez tout au plus 2 plus accessible aux voitures. Pour faire 2/3 N^2 accessible voitures, vous devez faire au moins 1/3 N^2 espaces, et c'est tous les carrés que vous avez. Donc, vous pouvez remplir le garage est situé à plus de 2/3 plein.
Le schéma ci-dessus est asymptotiquement optimale, sa densité approches 2/3 N -> infini. (Un peu ennuyeux, j'espérais quelques arbres à la recherche de modèle permettrait de faire mieux.)
C'est en gros équivalent à bin-packing, avec l'ajout de l'exigence que la sortie soit dans un lieu particulier et toutes les voitures peut quitter, qui est lui-même un problème difficile!
Si votre problème est d'au moins NP-dur.
Est votre définition de l'efficacité le plus grand nombre de places de stationnement dans un lot d'une taille et d'une forme (en supposant que chaque voiture peut être chassés sans le déplacer sur une autre voiture)? Si oui, c'est un emballage problème, pas un problème de sac-à-dos, et il semble NP pour moi, mais la gamme de solutions pour un monde réel beaucoup d'être si petit qu'il pourrait être résolu avec une pratique de recherche exhaustive.
Je pense qu'il peut être techniquement NP complet. Mais je pense que vous pourriez développer un système intelligent de l'ensemble des solutions, chacun profitant de l'expérience de la dernière, et algorithmiquement choisir une meilleure solution de la valeur calculée ensemble. Vous ne pouvez pas être en mesure de prouver qu'elle est la meilleure solution possible. Mais à partir d'un point de vue pratique, vous avez une optimisation du parc de stationnement, le fait-il vraiment de l'importance que, compte tenu d'un nombre infini de fois que vous avez pressé 3 plus de voitures là-dedans?