attribution d'un siège contigu dans la carte des sièges

Question

Je dois écrire un algorithme pour l'attribution de sièges contigus dans une carte de sièges, par exemple pour l'attribution de sièges dans un stade. La carte des sièges peut être vue comme un tableau 2D de N lignes et M colonnes. Le système doit attribuer des sièges contigus pour les réservations effectuées ensemble. Étant donné qu'aucun plan des sièges n'est présenté à l'utilisateur, le système doit automatiquement attribuer les sièges disponibles correspondant à chaque achat. En outre, il doit le faire de manière à minimiser les trous/écarts dans les sièges.

Answer 1

Trouver une solution parfaite est NP-difficile . Examinez le problème du langage équivalent :
L={((x1,x2,...,xk),n,m)} où xi est le nombre de billets réservés en commun et n,m la taille des stades.

Nous montrerons Partition <=(P) L, et donc ce problème est NP-Hard, et il n'y a pas de solution polynomiale connue pour ce problème.

Preuve
laisser S=(x1,x2,..,xk) est l'entrée d'un problème de partition, et laissez sum=x1+...+xk
Regardez la réduction suivante :

Input: S=(x1,...,xk)
Output:((x1,...,xk),sum/2,2)

La correction : Si S a une partition, qu'elle soit S1=(x_i1,x_i2,...,x_it) alors par définition de la partition, x_i1+...+x_it=sum/2 et nous pouvons donc insérer x_i1,..,x_it dans la première ligne, et le reste dans la deuxième ligne, et ainsi de suite ((x1,...,xk),sum/2,2) est dans L
Si ((x1,...,xk),sum/2,2) est dans L, alors par définition il y a t réservations telles que x_i1,x_i2,...,x_it forment une première ligne parfaite, et donc x_i1+x_i2+...+x_it=sum/2 et donc c'est une partition valide et S est dans le problème de la partition

Conclusion :
Étant donné que L est NP-Hard et que le problème que vous recherchez est le problème d'optimisation de ce langage, il n'existe pas de solution polynomiale connue. Pour une solution exacte, vous pouvez utiliser retour en arrière [vérifier toutes les possibilités et choisir la meilleure], mais cela prendra beaucoup de temps, ou vous pouvez opter pour une solution heuristique, telle que avide mais il ne sera pas optimisé.

EDIT : Solution de backtracking [pseudocode] :

solve(X,n,m):
   global bestVal <- infinity
   global bestSol <- null
   solve(X,new Solution(n,m))
solve(X,solution):
   if (X is empty):
       gaps <- solution.numGaps()
       if (gaps < bestVal):
            bestVal <- gaps
            bestSol <- solution
       return
   temp <- X.first
   X.removeFirst()
   for i from 0 to m:
       solution.addToLine(i,temp)
       solve(X,solution)
       solution.removeFromLine(i,temp)
   X.addFirst(temp)

Assumer Solution est une classe implémentée, et pour une solution illégale [c'est-à-dire trop de personnes dans une rangée] numGaps() == infinity

Answer 2

Note

Ce n'est généralement pas un vrai problème, car si vous parvenez à vendre tous vos billets, les derniers acheteurs feront un compromis et diviseront leurs réservations en plusieurs réservations distinctes, ou se retireront et permettront à d'autres acheteurs ayant des exigences différentes en matière de taille de réservation d'acheter les sièges restants.

De plus, les gens aiment choisir leur siège. Si vous voulez interdire cette option, ils peuvent choisir de ne pas acheter de billets du tout.

Notez que si les acheteurs n'ont aucun contrôle sur leurs sièges, vous pouvez tout aussi bien leur donner un code, et traduire ce code en un siège spécifique une fois que tous les billets sont vendus.

Réponse au problème posé :

Chaque ligne comporte m sièges. Nous supposerons que la taille de réservation la plus élevée est de m (sinon, nous devrons le diviser en plusieurs réservations).

Tout d'abord, nous devons modéliser la fonction de distribution de probabilité discrète pour la taille des réservations. Cette fonction peut être construite sur la base des données des événements précédents. (Un modèle plus avancé peut prendre en compte le type d'événement, l'heure de l'événement, etc.) Appelons cette fonction f(b)

Il est évident que la meilleure stratégie consiste à remplir les lignes de gauche à droite (ou de droite à gauche) et à ne pas laisser d'espaces vides, ce qui ne ferait qu'imposer davantage de contraintes.

Supposons que le stade contienne une seule ligne. Nous pouvons calculer la probabilité de remplir toute la rangée en énumérant toutes les tailles de réservation possibles. Nous pouvons utiliser la méthode proposée aquí pour l'énumération, en multipliant chaque taille de réservation par sa probabilité et en faisant la somme.

Supposons maintenant qu'il y ait 2 rangées dans le stade et que la première taille de réservation soit de 3. Il y a maintenant une rangée avec m sièges vides, et une autre rangée avec m-3 sièges vides. La deuxième taille de réservation est de 4. Nous pouvons maintenant comparer la probabilité de remplir un siège. (m-4) et la probabilité de remplir une rangée de sièges, et la probabilité de remplir une rangée de sièges. (m-3-4) rangée de sièges. Nous attribuerons les sièges pour la réservation en cours en conséquence.

Bien entendu, la probabilité de remplir une ligne vide est de 1, et une fois remplie, elle doit être supprimée de la liste des lignes non remplies.

En général, pour chaque réservation, nous pouvons l'affecter à la ligne où la probabilité de la remplir (après l'affectation) serait maximisée.

Il convient de noter qu'étant donné f(b) toutes ces probabilités peuvent être calculées à l'avance pour toute constante comprise entre 1 y m .

Answer 3

Vous devriez vous pencher sur les algorithmes d'allocation de mémoire pour les systèmes d'exploitation. C'est ce qui modélise le mieux votre problème. Vous devez vous concentrer sur les algorithmes qui minimisent la fragmentation.

Answer 4

J'aime bien la dernière. Elle est tout à fait correcte dans le sens le plus simple du terme. Pour la rapidité, un test de carte de probabilité est un excellent moyen de remplir les rangées. Mais il manque quelques éléments. Cela vous intéresse-t-il que les partis soient divisés par un certain nombre de sièges ? Qu'en est-il des annulations et des remboursements ? Examinez le problème d'une manière un peu différente. Il y a 3 états possibles, et non 2. M sièges vides, dans R rangées, chacun avec 3 états possibles : Vacant, Rempli, Annulé, où Annulé a une probabilité ajustée. Comment gérer cela ? Vous pouvez augmenter la probabilité de remplir les annulations ou les remboursements en les plaçant dans une nouvelle rangée, avec N sièges, avec une probabilité de 1 pour remplir des ensembles de 1 à N sièges, et vous pouvez encore augmenter la probabilité de remplir tous les sièges en limitant la taille probable du groupe lorsque N > 2 à une taille de groupe >2 mais inférieure à N.

Une autre façon de procéder consiste à utiliser une carte. Pour illustrer cela, créez une feuille de calcul composée de petits carrés d'une taille d'environ un siège. Placez une lettre dans chaque carré pour indiquer la disponibilité des sièges. Créez ensuite une base de données qui renvoie à ce fichier. Vous pouvez ajouter une section dans laquelle vous définissez les numéros des sièges dans la rangée, puis identifier un numéro de billet pour la salle en fonction de cela, et vous pouvez effectuer des tests simples pour remplir les sièges. Cela permettra de "minimiser" les lacunes, mais ne les éliminera probablement pas complètement. Si, comme moi, vous travaillez avec des intermittents du spectacle \entertainers\musicians et les sites, la cartographie est essentielle. Le principal groupe avec lequel je travaille est petit et a un public fidèle mais en constante évolution. Il s'agit à la fois d'un programme pour enfants, d'une action de proximité et d'une troupe de théâtre. Le problème que je rencontrais était que de nombreuses personnes voulaient s'asseoir avec des amis, etc. J'ai donc imaginé la formule des billets multiples. \ROW\TABLE plan d'attaque. Comment procéder ? Pour chaque division que vous faites, vous devez faire une provision dans votre programmation. Les lignes et les colonnes sont une bonne base de travail. Nous commencerons par là. Avec les tableaux, placez-les en lignes et en colonnes, et vous pourrez les découper joliment. Ce n'est peut-être pas parfait, mais cela fonctionne, avec un petit ajustement pour chaque division en sections que vous faites.

Considérez ceci... numérotez vos sièges de gauche à droite, tout simplement. Suivez ce modèle lorsque vous attribuez des places à un billet : Pour la colonne a, la rangée a, allez de gauche à droite (ce qui signifie pour la rangée b, allez de droite à gauche (suivez maintenant le calcul ci-dessous) Procédez de la même manière pour chaque colonne (imaginez une salle de spectacle comme le Carnegie Hall, où chaque colonne comporte des allées de chaque côté et s'étend sur plusieurs rangées). Le calcul pour chaque rangée d'une colonne est assez simple. Prenez le nombre total de sièges dans les rangées paires pour les réservations de groupe : Si partysize > remainingSeatsInRow mult seat#_in_row by -1 then add to the seat#_Normal=S (where S is the seat#_within_row), if S* -1>0, S*-1=S endif, so the venue fills up by group and by single, keeping parties together. Supposons que vous ajustiez la tarification toutes les 15 rangées environ, les zones où les prix sont les plus élevés peuvent se remplir plus lentement, vous pouvez donc ajouter des incitations, mais uniquement pour ces zones, ou ajuster les incitations pour chaque zone et en fonction du nombre de billets disponibles dans cette zone, etc. Ajoutez maintenant la possibilité de vérifier les places restantes dans d'autres zones tarifaires pour accueillir un groupe (rappelez-vous qu'il suffit qu'ils soient dans la même zone et qu'ils seront toujours assis ensemble par proximité ; je me concentrerais uniquement sur les opérations en colonne pour gagner du temps, mais chacun est libre) et vous pouvez même envoyer une demande pour remplir les places vides dans les zones tarifaires plus élevées à un prix inférieur, juste pour remplir la salle à l'approche de l'heure du spectacle et garder les gens heureux avec leurs copains. Pour ce qui est de la sélection... ...vous pouvez demander aux gens de choisir leur place s'il y a des places disponibles. Dans le cas que je suis en train de construire, les lieux changent en même temps que les dates, et je dois donc utiliser cet algorithme au maximum de ses capacités. Fondamentalement, les spectacles sont des œuvres de bienfaisance et les participants sont des parents, des amis, des membres de la communauté, etc. qui connaissent les groupes qui se produisent et se connaissent entre eux. S'ils savent où quelqu'un est assis, ils voudront être à proximité. Obtenez le nombre de billets qu'ils veulent et montrez les zones où il y a autant de sièges disponibles par le biais de l'ensemble que vous voulez ; vous pouvez même aller par rangée et par colonne (pour utiliser votre exemple de remplissage des sièges ; carnegie a plusieurs ensembles d'allées qui divisent une colonne entre les rangées, de sorte que vous pouvez soit changer de colonne, soit simplement continuer à avancer ; carnegie a également des sièges de niveau et des balcons - comme le dirait le jeune monsieur Simpson, "Aye Carumba ! "Si le vôtre change, vous devez en tenir compte dans vos bases de données et travailler à partir de là ; ce modèle est flexible car il peut être ajusté à plusieurs diagrammes) de toute façon, pour bien faire les choses : utilisez le test original pour aller en ligne droite (vous pourriez leur demander de sélectionner la colonne et la ligne de leurs copains, puis de tester la colonne, puis les colonnes adjacentes pour les mêmes lignes avec les numéros de siège testés pour la proximité, utilisez les mathématiques du gardien de proximité original ci-dessus, si les copains sont à gauche, testez la colonne de gauche sur les numéros de siège de droite, si les copains sont à droite, vérifiez la colonne de droite sur les numéros de siège de gauche et comparez même les annulations. discuté plus tard Si vous mettez en évidence les zones où des sièges sont disponibles, que vous en tirez un nombre et que vous ne mettez en évidence que les zones où il reste autant de sièges contigus disponibles (faites le test sur 2 rangées ou plus si nécessaire, le même test que ci-dessus est mis en œuvre dans les rangées d'une colonne), ils seront très probablement assis ensemble si vous avez fait le test ci-dessus correctement, mais au pire, ils seront assis le plus près possible les uns des autres (et combien de fois ce test a-t-il lieu, hein ?). Vous pouvez proposer cette option à un prix spécial tant que vous avez de l'espace à remplir, mais logiquement, vous devriez plafonner la taille de la fête que ce placement secondaire peut accueillir, et il est probable qu'il échouera de plus en plus souvent à mesure que vous vous rapprocherez de l'heure de votre spectacle.
Vient maintenant la partie la plus amusante, le nettoyage de l'écart. Certaines personnes se rendent à un enterrement de vie de garçon ou arriveront probablement en retard à cause de leur travail ou des embouteillages, et veulent assister à un spectacle ou voir leur enfant jouer une interprétation ridicule de Peter Pan. Si le nombre de places libres dans une rangée ou une colonne donnée est de 1 et qu'il n'y a plus de places autour (ce qui devrait arriver si des personnes annulent), ou si un groupe entier annule, vous devez remettre ces places dans le chapeau de tri. Il y a plusieurs façons de procéder. Vous pouvez créer un grand tableau de sièges pour chaque section et travailler à partir de celui-ci, mais il peut être préférable d'ouvrir une nouvelle liste pour contenir de petits tableaux de sièges adjacents qui peuvent remplir les sièges de votre section principale ; vous pouvez également créer un fichier texte de plan de salle, en marquant chaque siège comme vacant, plein, annulé, et stocker les pointeurs des groupes annulés, puis tester la cartographie pour les annulations après chaque annulation, et créer des cartographies séparées pour les différentes tailles de groupe qui contiennent les listes de sièges pour chaque taille. Vous pouvez nommer les cartes avec le titre Venue_Cancel_GroupSize, puis coder le test pour vérifier toutes les cartes où GroupSize est >= à votre nouveau groupe. Cela rend plus difficile la recherche de vos amis car vous avez un nouveau test, mais vous pouvez utiliser les mêmes pré-tests pour les aligner afin de scanner les places disponibles et de les dessiner : Testez s'il y a des annulations, testez le nombre de sièges contigus pour chaque annulation (combien y en a-t-il dans le nouveau groupe ? pourront-ils tenir dans un créneau d'annulation ? Offrez-leur une réduction sur les sièges restants dans le créneau d'annulation, puis traitez toutes ces données)... ... Il ne s'agit pas exactement d'un algorithme, loin de là, juste d'une conception mentale du problème avec une tonne de tests arithmétiques de base de type IF qui devraient s'exécuter comme un éclair, mais vous pouvez diviser ces tests en séparant les machines qui les exécutent, et attendre que tous les processus reviennent, puis additionner les résultats, etc, (interrogation multiserveur de la vieille école d'un fichier distant, logiciel d'interrogation de base de données hébergé par des machines distantes ; avec les serveurs plus récents, vous pouvez exécuter les tests plus rapidement en les liant ensemble dans XSERVE, et en mettant en place des fermes multihomées qui gèrent la base de données, avec des unités plus petites qui gèrent votre site web).

P Déterminez comment diviser votre (vos) lieu(x) de réunion, puis comment le (les) numéroter. \count les différentes sections \seats et comment fixer le prix des billets, puis déterminer si l'on veut que les gens choisissent leur prix avec une vue interactive ou une vue simpliste. Avec plus d'interaction, vous risquez de vous retrouver avec quelques lacunes. S'il y en a quelques-unes, vous pouvez proposer des baisses de prix ou des invitations spéciales aux personnes intéressées, etc. Cela vous permet de maximiser l'utilisation de la salle et d'offrir des choix qui maximisent la satisfaction. Je ne suis pas sûr du nom de cet algorithme, mais l'utilisation d'un tri à bulles, d'une base de données ou de tout autre outil similaire peut vous permettre de définir vos valeurs pour la billetterie, ainsi que toutes les informations nécessaires à la réservation. Cela vous permet de traiter une annulation comme un élément distinct mais LIÉ, de définir des drapeaux et d'ajouter de manière répétitive un traitement des données à vos opérations afin d'éviter les sur- ou sous-réservations. La méthode de base est la suivante : en cas de surréservation, vous obtenez les balises temporelles de chacune des dernières transactions, N+1 (où N est le nombre de transactions surréservées), et toutes les personnes après la dernière réservation (qui ont rempli la salle ou l'ont à peine remplie) seront placées dans une nouvelle table avec les mêmes informations sur les transactions, puis on vérifiera si elles conviennent encore, et si ce n'est pas le cas, elles seront remboursées, et on leur enverra un e-mail ou on les appellera. De cette manière, vous pouvez vérifier le nombre de places disponibles et voir si quelqu'un souhaite raccourcir sa fête. Vous pouvez également leur faire de nouvelles offres en exportant leurs informations dans un nouveau tableau pour le CMS, et les satisfaire. C'est beaucoup de travail, mais cette méthode peut exécuter plusieurs tests simultanés si elle est configurée et traitée correctement. C'est probablement une réponse longue et ennuyeuse, mais le mérite en revient à Lior qui a énoncé un test couramment utilisé. C'est juste mon long programme pour maximiser si vous avez la puissance de traitement et le temps de construire le code.