c++ - una - cuanto mide el cinturon de seguridad de un avion

Tirar a las personas más gordas de un avión sobrecargado.

Question

Digamos que tienes un avión, y es bajo en combustible. A menos que el avión baje 3000 libras de peso del pasajero, no podrá llegar al próximo aeropuerto. Para salvar la cantidad máxima de vidas, nos gustaría echar a las personas más pesadas del avión primero.

Y oh sí, hay millones de personas en el avión, y nos gustaría un algoritmo óptimo para encontrar a los pasajeros más pesados, sin clasificar necesariamente toda la lista.

Este es un problema de proxy para algo que estoy intentando codificar en C ++. Me gustaría hacer una "orden parcial" en el manifiesto del pasajero por peso, pero no sé cuántos elementos voy a necesitar. Podría implementar mi propio algoritmo "partial_sort" ("partial_sort_accumulate_until"), pero me pregunto si hay alguna forma más fácil de hacerlo utilizando STL estándar.

Answer 1

¿Por qué no utiliza un quicksort parcial con una regla de cancelación diferente a "ordenada"? Puede ejecutarlo y luego usar solo la mitad superior y continuar hasta que el peso dentro de esta mitad superior no contenga el peso que al menos tiene que tirar, ya que retrocede un paso en la recursión y ordena la lista. Después de eso, puede comenzar a expulsar a las personas del extremo superior de esa lista ordenada.

Answer 2

@Blastfurnace estaba en el camino correcto. Utiliza la selección rápida donde los pivotes son umbrales de peso. Cada partición divide un conjunto de personas en conjuntos y devuelve el peso total para cada conjunto de personas. Continúa rompiendo el cucharón apropiado hasta que sus cubos correspondientes a las personas con mayor peso tengan más de 3000 libras, y su cucharón más bajo que se encuentre en ese conjunto tiene 1 persona (es decir, no se puede dividir más).

Este algoritmo es de tiempo lineal amortizado, pero en el peor caso cuadrático. Creo que es el único algoritmo de tiempo lineal .

Aquí hay una solución de Python que ilustra este algoritmo:

#!/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)

Salida:

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]

Answer 3

@James tiene la respuesta en los comentarios: a std::priority_queue si puedes usar cualquier contenedor, o una combinación de std::make_heap y std::pop_heap (y std::push_heap ) si quieres usar algo como un std::vector .

Answer 4

A continuación se muestra una implementación bastante simple de la solución sencilla. No creo que haya una manera más rápida que sea 100% correcta.

size_t total = 0;
std::set<passenger> 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());
}
}
}

Esto funciona rellenando el conjunto de "personas muertas" hasta que alcanza el umbral. Una vez que se alcanza el umbral, seguimos repasando la lista de pasajeros que intentan encontrar a cualquiera que sea más pesado que el muerto más ligero. Cuando hemos encontrado uno, los agregamos a la lista y luego comenzamos a "Guardar" a las personas más ligeras de la lista hasta que no podamos guardar más.

En el peor de los casos, esto funcionará casi igual que una especie de la lista completa. Pero en el mejor de los casos (la "lista muerta" se llena correctamente con las primeras X personas) ejecutará O(n) .

Answer 5

Aquí hay una solución basada en el montón que utiliza el módulo heapq incorporado de Python. Está en Python, por lo que no responde la pregunta original, pero es más limpia (IMHO) que la otra solución de Python publicada.

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 = el número de pasajeros a lanzar y N = el número de pasajeros, entonces el mejor caso para este algoritmo es O (N) y el peor caso para este algoritmo es Nlog (N). El peor de los casos ocurre si k está cerca de N durante mucho tiempo. Aquí hay un ejemplo del peor reparto:

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

Sin embargo, en este caso (arrojar personas fuera del avión (supongo que con un paracaídas)) k debe ser inferior a 3000, que es << "millones de personas". Por lo tanto, el tiempo de ejecución promedio debe ser de Nlog (k), que es lineal al número de personas.

Answer 6

Esto no ayudará a su problema de proxy, sin embargo:

Para que 1,000,000 pasajeros bajen 3000 libras de peso, cada pasajero debe perder (3000/1000000) = 0.003 libras por persona. Esto podría lograrse desechando la camisa o los zapatos de cada uno, o incluso los recortes de uñas, salvando a todos. Esto supone una recogida y eliminación eficientes antes de que la pérdida de peso necesaria aumentara a medida que el avión utilizaba más combustible.

En realidad, ya no permiten que las podadoras de uñas a bordo, así que eso está fuera.

Answer 7

Podría hacer una pasada sobre la lista para obtener la media y la desviación estándar, y luego usarla para aproximarse al número de personas que tienen que ir. Use partial_sort para generar la lista basada en ese número. Si la estimación fue baja, use partial_sort nuevamente en el resto con una nueva estimación.

Answer 8

Probablemente usaría std::nth_element para dividir a las 20 personas más pesadas en tiempo lineal. Luego use un método más complejo para encontrar y golpear el más pesado de los pesados.

Answer 9

Suponiendo que todos los pasajeros cooperarán: use una red de clasificación paralela . (ver también this )

Aquí hay una demostración en vivo.

Actualización: video alternativo (saltar a 1:00)

Pedir a parejas de personas que comparen intercambios: no se puede llegar más rápido que esto.

Answer 10

Suponiendo que, al igual que los pesos de las personas, tenga una buena idea de cuáles son los valores máximos y mínimos que probablemente se utilizarán utilizando una clasificación de raíz para clasificarlos en O (n). Luego simplemente trabaja desde el final más pesado de la lista hacia el más ligero. Tiempo total de ejecución: O (n). Desafortunadamente, no hay una implementación de un tipo de radix en el STL, pero es bastante sencillo de escribir.

Answer 11

Torneo masivo paralelo: -

Suponiendo un estándar de tres asientos a cada lado del ailse: -

1. Pida a los pasajeros en el asiento de la ventana que se muevan al asiento del medio si son más pesados ​​que la persona que está en el asiento de la ventana.

2. Pida a los pasajeros en el asiento del medio que intercambien con el pasajero en el asiento del pasillo si son más pesados.

3. Pídale al pasajero en el asiento del pasillo izquierdo que intercambie con el pasajero en el asiento del pasillo derecho id. Son más pesados.

4. Burbuja clasifica a los pasajeros en el asiento del pasillo derecho. (Da n pasos para n filas). - Pida a los pasajeros en el asiento del pasillo derecho que intercambien con la persona que está delante n -1 veces.

5 Sácalos de la puerta hasta que alcances las 3000 libras.

3 pasos + n pasos más 30 pasos si tiene una carga de pasajeros realmente delgada.

Para un plano de dos pasillos, las instrucciones son más complejas pero el rendimiento es aproximadamente el mismo.

Answer 12

Una forma sería usar un montón mínimo ( std::priority_queue en C ++). Así es como lo harías, asumiendo que MinHeap una clase MinHeap . (Sí, mi ejemplo está en C #. Creo que entiendes la idea).

int targetTotal = 3000;
int totalWeight = 0;
// this creates an empty heap!
var myHeap = new MinHeap<Passenger>(/* 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.

De acuerdo con las referencias estándar, el tiempo de ejecución debe ser proporcional a n log k , donde n es el número de pasajeros y k es el número máximo de elementos en el montón. Si asumimos que el peso de los pasajeros generalmente será de 100 lb o más, entonces es poco probable que el montón contenga más de 30 artículos en cualquier momento.

El peor de los casos sería si los pasajeros se presentan en orden del peso más bajo al más alto. Eso requeriría que cada pasajero se agregue al montón, y que cada pasajero sea retirado del montón. Aún así, con un millón de pasajeros y suponiendo que el más ligero pesa 100 libras, el n log k funciona en un número razonablemente pequeño.

Si obtiene el peso de los pasajeros al azar, el rendimiento es mucho mejor. Uso algo parecido a esto para un motor de recomendaciones (selecciono los 200 elementos principales de una lista de varios millones). Normalmente termino con solo 50,000 o 70,000 artículos realmente agregados al montón.

Sospecho que verá algo muy similar: la mayoría de sus candidatos serán rechazados porque son más ligeros que la persona más ligera que ya está en el montón. Y Peek es una operación O(1) .

Para obtener más información sobre el rendimiento de la selección del montón y la selección rápida, consulte Cuándo la teoría se encuentra con la práctica . Versión corta: si selecciona menos del 1% del número total de artículos, entonces la selección de pila es un claro ganador sobre la selección rápida. Más del 1%, luego use selección rápida o una variante como Introselect .