Lancer les plus grosses personnes sur un avion surchargé.

Disons que vous avez un avion et que le carburant manque. À moins que l’avion ne tombe à 3000 livres de passagers, il ne pourra pas atteindre l’aéroport suivant. Pour sauver le plus grand nombre de vies possible, nous aimerions d’abord faire partir les personnes les plus lourdes de l’avion.

Et oh oui, il y a des millions de personnes dans l’avion, et nous aimerions un algorithme optimal pour trouver les passagers les plus lourds, sans nécessairement sortinger la liste complète.

Ceci est un problème de proxy pour quelque chose que j’essaye de coder en C ++. Je voudrais faire un “partial_sort” sur le passager manifeste en poids, mais je ne sais pas combien d’éléments je vais avoir besoin. Je pourrais implémenter mon propre algorithme “partial_sort” (“partial_sort_accumulate_until”), mais je me demande s’il existe un moyen plus simple de le faire en utilisant la STL standard.

Un moyen serait d’utiliser un tas std::priority_queue ( std::priority_queue en C ++). Voici comment vous le feriez, en supposant que vous ayez une classe MinHeap . (Oui, mon exemple est en C #. Je pense que vous avez l’idée.)

 int targetTotal = 3000; int totalWeight = 0; // this creates an empty heap! var myHeap = new MinHeap(/* need comparer here to order by weight */); foreach (var pass in passengers) { if (totalWeight < targetTotal) { // unconditionally add this passenger myHeap.Add(pass); totalWeight += pass.Weight; } else if (pass.Weight > myHeap.Peek().Weight) { // If this passenger is heavier than the lightest // passenger already on the heap, // then remove the lightest passenger and add this one var oldPass = myHeap.RemoveFirst(); totalWeight -= oldPass.Weight; myHeap.Add(pass); totalWeight += pass.Weight; } } // At this point, the heaviest people are on the heap, // but there might be too many of them. // Remove the lighter people until we have the minimum necessary while ((totalWeight - myHeap.Peek().Weight) > targetTotal) { var oldPass = myHeap.RemoveFirst(); totalWeight -= oldPass.Weight; } // The heap now contains the passengers who will be thrown overboard. 

Selon les références standard, le temps d’exécution doit être proportionnel à n log k , où n est le nombre de passagers et k le nombre maximal d’éléments sur le tas. Si nous supposons que le poids des passagers sera généralement de 100 livres ou plus, il est peu probable que le tas contienne plus de 30 articles à tout moment.

Le pire des cas serait que les passagers soient présentés dans l’ordre, du poids le plus faible au plus élevé. Cela exigerait que chaque passager soit ajouté au tas et que chaque passager soit retiré du tas. Malgré tout, avec un million de passagers et en supposant que le plus léger pèse 100 livres, le nombre de passagers représente un nombre raisonnablement réduit.

Si vous obtenez le poids des passagers au hasard, la performance est bien meilleure. J’utilise quelque chose comme ça pour un moteur de recommandation (je sélectionne les 200 meilleurs articles dans une liste de plusieurs millions). Je finis généralement avec seulement 50 000 ou 70 000 articles ajoutés au tas.

Je soupçonne que vous verrez quelque chose de très similaire: la majorité de vos candidats seront rejetés car ils sont plus légers que les plus légers. Et Peek est une opération O(1) .

Pour plus d’informations sur les performances de la sélection de tas et de la sélection rapide, voir Quand la théorie rencontre la pratique . Version courte: si vous sélectionnez moins de 1% du nombre total d’éléments, alors la sélection de tas est clairement gagnante par rapport à la sélection rapide. Plus de 1%, puis utilisez la sélection rapide ou une variante comme Introselect .

Cela ne vous aidera pas pour votre problème de proxy, cependant:

Pour 1 000 000 de passagers qui perdent 3 000 livres de poids, chaque passager doit perdre (3000/1000000) = 0,003 lb par personne. Cela pourrait être réalisé en larguant toutes les chemises ou chaussures, ou probablement même les coupures d’ongles, sauvant tout le monde. Cela suppose une collecte et un largage efficaces avant que la perte de poids nécessaire augmente à mesure que l’avion utilise plus de carburant.

En fait, ils n’autorisent plus les coupe-ongles à la main, alors c’est tout.

Vous trouverez ci-dessous une implémentation assez simple de la solution simple. Je ne pense pas qu’il existe un moyen plus rapide qui soit 100% correct.

 size_t total = 0; std::set dead; for ( auto p : passengers ) { if (dead.empty()) { dead.insert(p); total += p.weight; continue; } if (total < threshold || p.weight > dead.begin()->weight) { dead.insert(p); total += p.weight; while (total > threshold) { if (total - dead.begin()->weight < threshold) break; total -= dead.begin()->weight; dead.erase(dead.begin()); } } } 

Cela fonctionne en remplissant l’ensemble des “personnes mortes” jusqu’à ce qu’il atteigne le seuil. Une fois le seuil atteint, nous continuons à parcourir la liste des passagers essayant de trouver ceux qui sont plus lourds que le mort le plus léger. Lorsque nous en avons trouvé un, nous les ajoutons à la liste, puis nous commençons à “enregistrer” les personnes les plus légères de la liste jusqu’à ce que nous ne puissions plus en économiser.

Dans le pire des cas, cela se fera à peu près comme une sorte de liste entière. Mais dans le meilleur des cas (la “liste morte” est remplie correctement avec les X premières personnes), elle exécutera O(n) .

En supposant que tous les passagers coopéreront: Utilisez un réseau de sorting parallèle . (voir aussi ceci )

Voici une démonstration en direct

Mise à jour: vidéo alternative (sauter à 1:00)

Demander à des personnes de comparer les échanges – vous ne pouvez pas obtenir plus vite que cela.

@Blastfurnace était sur la bonne voie. Vous utilisez quickselect où les pivots sont des seuils de poids. Chaque partition divise un ensemble de personnes en ensembles et renvoie le poids total pour chaque groupe de personnes. Vous continuez à casser le seau approprié jusqu’à ce que vos seaux correspondant au poids le plus élevé atteignent plus de 3000 livres et que votre seau le plus bas dans cet ensemble comporte 1 personne (c’est-à-dire qu’il ne peut plus être divisé).

Cet algorithme est le temps linéaire amorti, mais le pire cas quadratique. Je pense que c’est le seul algorithme de temps linéaire .


Voici une solution Python qui illustre cet algorithme:

 #!/usr/bin/env python import math import numpy as np import random OVERWEIGHT = 3000.0 in_trouble = [math.floor(x * 10) / 10 for x in np.random.standard_gamma(16.0, 100) * 8.0] dead = [] spared = [] dead_weight = 0.0 while in_trouble: m = np.median(list(set(random.sample(in_trouble, min(len(in_trouble), 5))))) print("Partitioning with pivot:", m) lighter_partition = [] heavier_partition = [] heavier_partition_weight = 0.0 in_trouble_is_indivisible = True for p in in_trouble: if p < m: lighter_partition.append(p) else: heavier_partition.append(p) heavier_partition_weight += p if p != m: in_trouble_is_indivisible = False if heavier_partition_weight + dead_weight >= OVERWEIGHT and not in_trouble_is_indivisible: spared += lighter_partition in_trouble = heavier_partition else: dead += heavier_partition dead_weight += heavier_partition_weight in_trouble = lighter_partition print("weight of dead people: {}; spared people: {}".format( dead_weight, sum(spared))) print("Dead: ", dead) print("Spared: ", spared) 

Sortie:

 Partitioning with pivot: 121.2 Partitioning with pivot: 158.9 Partitioning with pivot: 168.8 Partitioning with pivot: 161.5 Partitioning with pivot: 159.7 Partitioning with pivot: 158.9 weight of dead people: 3051.7; spared people: 9551.7 Dead: [179.1, 182.5, 179.2, 171.6, 169.9, 179.9, 168.8, 172.2, 169.9, 179.6, 164.4, 164.8, 161.5, 163.1, 165.7, 160.9, 159.7, 158.9] Spared: [82.2, 91.9, 94.7, 116.5, 108.2, 78.9, 83.1, 114.6, 87.7, 103.0, 106.0, 102.3, 104.9, 117.0, 96.7, 109.2, 98.0, 108.4, 99.0, 96.8, 90.7, 79.4, 101.7, 119.3, 87.2, 114.7, 90.0, 84.7, 83.5, 84.7, 111.0, 118.1, 112.1, 92.5, 100.9, 114.1, 114.7, 114.1, 113.7, 99.4, 79.3, 100.1, 82.6, 108.9, 103.5, 89.5, 121.8, 156.1, 121.4, 130.3, 157.4, 138.9, 143.0, 145.1, 125.1, 138.5, 143.8, 146.8, 140.1, 136.9, 123.1, 140.2, 153.6, 138.6, 146.5, 143.6, 130.8, 155.7, 128.9, 143.8, 124.0, 134.0, 145.0, 136.0, 121.2, 133.4, 144.0, 126.3, 127.0, 148.3, 144.9, 128.1] 

En supposant que, comme le poids des personnes, vous avez une bonne idée de ce que les valeurs maximales et minimales sont susceptibles d’être utilisées, utilisez une sorte de base pour les sortinger dans O (n). Ensuite, il suffit de travailler de l’extrémité la plus lourde de la liste vers la plus légère. Durée totale: O (n). Malheureusement, il n’y a pas d’implémentation d’un sorting de base dans la STL, mais c’est assez simple à écrire.

Pourquoi n’utilisez-vous pas un quicksort partiel avec une règle d’abandon différente de “Trié”. Vous pouvez le lancer et utiliser seulement la moitié supérieure et continuer jusqu’à ce que le poids dans cette moitié supérieure ne contienne plus le poids qui doit être jeté, que vous revenez d’un pas dans la récursivité et sortingez la liste. Après cela, vous pouvez commencer à lancer des personnes hors du haut de la liste sortingée.

Tournoi massivement parallèle: –

En supposant une norme trois sièges de chaque côté de la ailse: –

  1. Demandez aux passagers du siège de la fenêtre de se déplacer vers le siège central s’ils sont plus lourds que la personne assise sur le siège de la fenêtre.

  2. Demandez aux passagers du siège central d’échanger avec le passager dans le siège de l’allée s’ils sont plus lourds.

  3. Demandez au passager du siège de l’allée de gauche d’échanger avec le passager dans le siège de l’allée de droite.

  4. Bubble sortinge les passagers dans le siège de l’allée droite. (Prend n étapes pour n lignes). – Demander aux passagers du siège de l’allée droite d’échanger avec la personne devant n -1 fois.

5 Kick les dehors la porte jusqu’à ce que vous atteigniez 3000 livres.

3 étapes + n étapes plus 30 étapes si vous avez un chargement de passagers vraiment mince.

Pour un avion à deux allées, les instructions sont plus complexes mais les performances sont à peu près les mêmes.

J’utiliserais probablement std::nth_element pour partitionner les 20 personnes les plus lourdes en temps linéaire. Ensuite, utilisez une méthode plus complexe pour trouver et cogner le plus lourd des lourds.

Vous pouvez passer une seule fois sur la liste pour obtenir la moyenne et l’écart type, puis l’utiliser pour estimer le nombre de personnes qui doivent y aller. Utilisez partial_sort pour générer la liste basée sur ce nombre. Si l’estimation est faible, utilisez à nouveau partial_sort sur le rest avec une nouvelle estimation.

@James a la réponse dans les commentaires: un std::priority_queue si vous pouvez utiliser n’importe quel conteneur, ou une combinaison de std::make_heap et std::pop_heap (et std::push_heap ) si vous voulez utiliser quelque chose comme un std::vector

Voici une solution basée sur le tas utilisant le module heapq intégré de Python. Il est en Python donc ne répond pas à la question initiale, mais c’est plus propre (IMHO) que l’autre solution Python postée.

 import itertools, heapq # Test data from collections import namedtuple Passenger = namedtuple("Passenger", "name seat weight") passengers = [Passenger(*p) for p in ( ("Alpha", "1A", 200), ("Bravo", "2B", 800), ("Charlie", "3C", 400), ("Delta", "4A", 300), ("Echo", "5B", 100), ("Foxtrot", "6F", 100), ("Golf", "7E", 200), ("Hotel", "8D", 250), ("India", "8D", 250), ("Juliet", "9D", 450), ("Kilo", "10D", 125), ("Lima", "11E", 110), )] # Find the heaviest passengers, so long as their # total weight does not exceeed 3000 to_toss = [] total_weight = 0.0 for passenger in passengers: weight = passenger.weight total_weight += weight heapq.heappush(to_toss, (weight, passenger)) while total_weight - to_toss[0][0] >= 3000: weight, repreived_passenger = heapq.heappop(to_toss) total_weight -= weight if total_weight < 3000: # Not enough people! raise Exception("We're all going to die!") # List the ones to toss. (Order doesn't matter.) print "We can get rid of", total_weight, "pounds" for weight, passenger in to_toss: print "Toss {p.name!r} in seat {p.seat} (weighs {p.weight} pounds)".format(p=passenger) 

Si k = le nombre de passagers à lancer et N = le nombre de passagers, alors le meilleur cas pour cet algorithme est O (N) et le pire cas pour cet algorithme est Nlog (N). Le pire des cas se produit si k est proche de N pendant longtemps. Voici un exemple de la pire dissortingbution:

 weights = [2500] + [1/(2**n+0.0) for n in range(100000)] + [3000] 

Cependant, dans ce cas (jeter des personnes hors de l’avion (avec un parachute, je présume)), alors k doit être inférieur à 3000, ce qui est «des millions de personnes». Le temps d'exécution moyen devrait donc concerner Nlog (k), qui est linéaire par rapport au nombre de personnes.