Jogando as pessoas mais gordas de um avião sobrecarregado.

200

Digamos que você tenha um avião, e ele está com pouco combustível. A menos que o avião caia 3000 libras de peso do passageiro, ele não poderá chegar ao próximo aeroporto. Para salvar o número máximo de vidas, gostaríamos de tirar as pessoas mais pesadas do avião primeiro.

E sim, existem milhões de pessoas no avião, e gostaríamos de um algoritmo ideal para encontrar os passageiros mais pesados, sem necessariamente classificar a lista inteira.

Este é um problema de proxy para algo que estou tentando codificar em C ++. Gostaria de fazer uma "parcial_sort" no manifesto do passageiro por peso, mas não sei quantos elementos vou precisar. Eu poderia implementar meu próprio algoritmo "parcial_sort" ("parcial_sort_accumulate_until"), mas estou pensando se há alguma maneira mais fácil de fazer isso usando o STL padrão.

IvyMike
fonte
5
Se a analogia com o ser humano é válida, você pode começar jogando fora pessoas que pesam mais que X, por exemplo, 120 kg, uma vez que essas pessoas provavelmente estão entre as pessoas mais gordas.
RedX
132
Todos os passageiros cooperariam com alguma etapa do algoritmo?
Lior Kogan 12/10
34
tópicos como este são o motivo pelo qual eu amo TI.
Markus
14
Posso perguntar para qual companhia aérea é essa? Quero ter certeza de que só voarei com eles antes da temporada de festas - não depois de me entregar.
Jp2code
24
A cooperação dos passageiros não é necessária com o equipamento adequado (como assentos ejetores com balanças embutidas).
Jim Fred

Respostas:

102

Uma maneira seria usar um heap mínimo ( std::priority_queueem C ++). Aqui está como você faria isso, assumindo que você teve uma MinHeapaula. (Sim, meu exemplo está em C #. Acho que você entendeu.)

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 acordo com as referências padrão, o tempo de execução deve ser proporcional a n log k, onde né o número de passageiros ek o número máximo de itens na pilha. Se assumirmos que o peso dos passageiros normalmente será de 100 libras ou mais, é improvável que o heap contenha mais de 30 itens a qualquer momento.

O pior caso seria se os passageiros fossem apresentados na ordem do menor para o maior. Isso exigiria que todos os passageiros fossem adicionados à pilha e todos os passageiros fossem removidos da pilha. Ainda assim, com um milhão de passageiros e assumindo que o mais leve pesa 100 libras, on log k resultado é um número razoavelmente pequeno.

Se você obtiver os pesos dos passageiros aleatoriamente, o desempenho será muito melhor. Uso algo assim para um mecanismo de recomendação (seleciono os 200 itens principais de uma lista de vários milhões). Normalmente, acabo com apenas 50.000 ou 70.000 itens realmente adicionados ao heap.

Eu suspeito que você verá algo bem parecido: a maioria dos seus candidatos será rejeitada porque é mais leve que a pessoa mais leve que já está na pilha. E Peeké uma O(1)operação.

Para obter mais informações sobre o desempenho da seleção de pilha e seleção rápida, consulte Quando a teoria atender à prática . Versão curta: se você estiver selecionando menos de 1% do número total de itens, a seleção de heap é uma clara ganhadora da seleção rápida. Mais de 1%, use a seleção rápida ou uma variante como o Introselect .

Jim Mischel
fonte
1
A SoapBox postou a resposta mais rápida.
Mooing Duck
7
Na minha leitura, a resposta da SoapBox é o equivalente moral da resposta de Jim Mischel. O SoapBox escreveu seu código em C ++ e, portanto, ele usa um std :: set, que possui o mesmo tempo de adição de log (N) que o MinHeap.
IvyMike 12/10
1
Existe uma solução de tempo linear. Eu vou adicionar.
Neil G
2
Há uma classe STL para um min-heap:std::priority_queue
bdonlan
3
@MooingDuck: Talvez você tenha entendido errado. Meu código cria um heap vazio, assim como o código do SoapBox cria um conjunto vazio. A principal diferença, a meu ver, é que o código dele apara o conjunto de excesso de peso à medida que itens de peso mais alto são adicionados, enquanto o meu mantém o excesso e apara no final. O conjunto dele diminuirá de tamanho à medida que ele avança na lista de pessoas mais pesadas. Minha pilha permanece do mesmo tamanho depois que atinge o limite de peso, e eu a apareço após verificar o último item da lista.
Jim Mischel
119

Isso não ajudará no seu problema de proxy, no entanto:

Para que 1.000.000 de passageiros deixem cair 3000 libras de peso, cada passageiro deve perder (3000/1000000) = 0,003 libras por pessoa. Isso poderia ser alcançado através do descarte de todas as camisas, sapatos ou, provavelmente, até recortes de unhas, salvando a todos. Isso pressupõe coleta e descarte eficientes antes que a perda de peso necessária aumente conforme o avião consome mais combustível.

Na verdade, eles não permitem mais cortadores de unhas a bordo, então está fora.

aportr
fonte
14
Adore a capacidade de analisar o problema e encontrar uma maneira verdadeiramente melhor.
Fncomp 19/10/11
19
Você é um gênio. :) #
19611 Jonathan
3
Acho que sapatos sozinho cobriria este
Mooing Duck
0.003 lbs é 0.048 oz, que é um pouco menos de 1/20 de uma onça. Portanto, se apenas uma em cada sessenta pessoas no avião estivesse aproveitando a regra do xampu de três onças, você poderia salvar o dia apenas jogando fora todo aquele xampu.
Ryan Lundy
43

Abaixo está uma implementação bastante simples da solução direta. Não acho que exista uma maneira mais rápida e 100% correta.

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());
        }
    }
 }

Isso funciona preenchendo o conjunto de "pessoas mortas" até atingir o limite. Uma vez atingido o limite, continuamos analisando a lista de passageiros que tentam encontrar outros que sejam mais pesados ​​que a pessoa morta mais leve. Quando encontramos um, os adicionamos à lista e começamos a "Salvar" as pessoas mais leves da lista até que não possamos mais salvar.

Na pior das hipóteses, isso terá o mesmo desempenho que uma espécie de lista inteira. Mas, na melhor das hipóteses (a "lista de mortos" é preenchida corretamente com as primeiras pessoas X), ela será executada O(n).

SoapBox
fonte
1
Eu acho que você deve atualizar ao totallado de continue; Other than that, esta é a resposta que eu ia postar. Solução super rápida
Mooing Duck
2
Esta é a resposta correta, é a resposta mais rápida, também é a resposta com a menor complexidade.
Xander Tulip
Você provavelmente poderia apertar um pouco mais fora dele pelo cache dead.begin () e rearranjando coisas um pouco para minimizar ramificação, que em processadores modernos é bastante lento
Wug
dead.begin () provavelmente é um rival e quase certamente seria incorporado apenas a um acesso a dados. Mas sim, mover alguns dos ifs obteria um pouco mais de desempenho ao reduzir filiais ... mas provavelmente com um grande custo de legibilidade.
SoapBox
1
Isso é logicamente elegante e atende a TODOS os requisitos do OP, incluindo o desconhecimento do número de passageiros na frente. No entanto, tendo passado boa parte dos últimos 5 meses trabalhando com mapas e conjuntos STL, tenho certeza de que o uso extensivo dos iteradores usados ​​prejudicaria o desempenho. Basta preencher o conjunto e iterar da direita para a esquerda até que a soma das pessoas mais pesadas seja superior a 3.000. Um conjunto de 1 milhão de elementos, apresentado em ordem aleatória, será carregado a ~ 30 milhões / s nos núcleos i5 || i7 3.4Ghz. Iteração pelo menos 100X mais lenta. O KISS ganhará aqui.
user2548100
32

Supondo que todos os passageiros cooperem: Use uma rede de classificação paralela . (veja também isso )

Aqui está uma demonstração ao vivo

Atualização: vídeo alternativo (pule para 1:00)

Pedindo a pares para troca de comparação - você não pode ficar mais rápido que isso.

Lior Kogan
fonte
1
Ainda é uma classificação e será O (nlogn). Você certamente pode ficar mais rápido, como um O (nlogk) onde k << n, solução foi fornecida.
Adam
1
@ Adam: É uma classificação paralela. A classificação tem um limite inferior de etapas O (nlog n) SEQUENTIAL. No entanto, eles podem ser paralelos, portanto a complexidade do tempo pode ser muito menor. veja, por exemplo, cs.umd.edu/~gasarch/ramsey/parasort.pdf
Lior Kogan
1
Bem, o OP diz "Este é um problema de proxy para algo que estou tentando codificar em C ++". Portanto, mesmo que os passageiros cooperem, eles não calcularão para você. É uma idéia interessante, mas a suposição desse artigo de que você obtém nprocessadores não se sustenta.
Adam
@LiorKogan - o vídeo de demonstração ao vivo não está mais disponível no youtube
Adelin
@Adelin: Obrigado, vídeo alternativo adicionado
Lior Kogan
21

@Blastfurnace estava no caminho certo. Você usa a seleção rápida onde os pivôs são limites de peso. Cada partição divide um conjunto de pessoas em conjuntos e retorna o peso total de cada conjunto de pessoas. Você continua quebrando o balde apropriado até que seus baldes correspondentes às pessoas com maior peso tenham mais de 3000 libras e seu balde mais baixo nesse conjunto tenha 1 pessoa (ou seja, não poderá mais ser dividido).

Esse algoritmo é amortizado no tempo linear, mas no pior dos casos quadrático. Eu acho que é o único algoritmo de tempo linear .


Aqui está uma solução Python que ilustra esse 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)

Resultado:

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]
Neil G
fonte
3
+1. Essa é uma ideia interessante, embora não tenha certeza de que seja bastante linear. A menos que esteja faltando alguma coisa, você precisa iterar sobre os itens para calcular o peso total do balde e recalcular o balde alto (pelo menos parcialmente) toda vez que dividir. Ainda será mais rápido do que minha abordagem baseada em heap no caso geral, mas acho que você está subestimando a complexidade.
Jim Mischel
2
@ Jim: deve ter a mesma complexidade que a seleção rápida . Sei que a descrição na wikipedia não é a melhor, mas a razão pela qual é o tempo amortizado linear é que toda vez que você faz uma partição, trabalha com apenas um lado da partição. Sem rigor, imagine que cada partição divida o conjunto de pessoas em duas. Então, o primeiro passo toma O (n), então O (n / 2), etc. e, n + n / 2 + n / 4 + ... = 2n.
21711 Neil G
2
@ Jim: De qualquer forma, seu algoritmo tem o melhor tempo de pior caso, enquanto o meu tem o melhor tempo médio de caso. Eu acho que as duas são boas soluções.
Neil G
2
@ JimMischel, NeilG: codepad.org/FAx6hbtc Eu verifiquei que todos têm os mesmos resultados e corrigi os de Jim. FullSort: 1828 carrapatos. JimMischel: 312 ticks. SoapBox 109 ticks. NeilG: 641 carrapatos.
Mooing Duck
2
@ NeilG: codepad.org/0KmcsvwD Eu usei std :: partition para tornar minha implementação do seu algoritmo muito mais rápida. stdsort: 1812 ticks. FullHeap 312 ticks. Soapbox / JimMichel: 109 ticks, NeilG: 250 ticks.
Mooing Duck
11

Supondo que, como o peso das pessoas, você tenha uma boa idéia de quais valores máximos e mínimos provavelmente usarão uma classificação radix para classificá-los em O (n). Em seguida, simplesmente trabalhe do final mais pesado da lista para o mais leve. Tempo total de execução: O (n). Infelizmente, não há uma implementação de uma classificação radix no STL, mas é bastante simples de escrever.

Keith Irwin
fonte
No entanto, eu não usaria uma classificação geral, pois você não precisa classificar completamente a lista para obter a resposta.
Mooing Duck
1
Para esclarecer, uma classificação radix é uma boa ideia. Apenas certifique-se de escrever um otimizado personalizado.
Mooing Duck
1
@Mooing: É verdade que você não precisa fazer uma classificação completa de radix, mas no momento em que publiquei isso, não havia algoritmos O (n) publicados e isso foi fácil de ver. Acho que a resposta de Neil G é a melhor, agora que ele a explicou de maneira mais completa e explícita, e começou a usar a mediana como o pivô de sua seleção. Mas o uso de uma classificação de raiz padrão é um pouco mais fácil e menos provável de ter sutis erros de implementação, por isso vou deixar minha resposta em aberto. Fazer uma classificação de raiz parcial personalizada seria definitivamente mais rápido, mas não assintoticamente.
perfil completo de Keith Irwin
6

Por que você não usa um quicksort parcial com uma regra de cancelamento diferente de "classificado". Você pode executá-lo e, em seguida, usar apenas a metade superior e continuar até que o peso nessa metade superior não contenha o peso que precisa ser jogado fora, pelo menos, você retrocede um passo na recursão e classifica a lista. Depois disso, você pode começar a expulsar pessoas da extremidade alta dessa lista classificada.

Sim
fonte
Esse é o conceito básico por trás do algoritmo de Neil G, eu acho .
Mooing Duck
essa é a essência do quickselect, que é o que Neil G está usando.
Michael Donohue 25/10
6

Massively Parallel Tournament Sort: -

Assumindo três assentos padrão de cada lado da ailse: -

  1. Peça aos passageiros no assento da janela que se movam para o assento do meio, se forem mais pesados ​​que a pessoa no assento da janela.

  2. Peça aos passageiros no assento do meio que troquem com o passageiro no assento do corredor, se eles forem mais pesados.

  3. Peça ao passageiro no banco do corredor esquerdo que troque com o passageiro no banco do corredor direito, se eles forem mais pesados.

  4. Bolha classifique os passageiros no assento do corredor direito. (Executa n etapas para n linhas). - peça aos passageiros no assento do corredor direito que troquem com a pessoa na frente n -1 vezes.

5 Chute-os para fora da porta até atingir 3000 libras.

3 degraus + n degraus mais 30 degraus, se você tiver uma carga de passageiros muito fina.

Para um plano de dois corredores - as instruções são mais complexas, mas o desempenho é praticamente o mesmo.

James Anderson
fonte
igual à resposta de Lior Kogan, mas com muito mais detalhes.
Mooing Duck
7
Uma solução "suficientemente boa" seria oferecer "cachorros-quentes gratuitos" e jogar fora os quinze primeiros que chegaram à frente. Não fornecerá sempre a solução ideal, mas será executado em "O" simples.
James Anderson
Não seria melhor jogar fora os últimos 15, já que os mais pesados ​​provavelmente serão mais lentos?
Peter
@Patriker - Eu acredito que o objetivo é perder 3000 libras com o número mínimo de pessoas. Embora você possa otimizar o algoritmo, altere a etapa 4 para "trocar com a pessoa de n - 29 vezes", o que levaria os 30 porcos mais para a frente, porém, não em ordem estrita de peso.
James Anderson
4

Eu provavelmente usaria std::nth_elementpara dividir as 20 pessoas mais pesadas em tempo linear. Em seguida, use um método mais complexo para encontrar e esbarrar no mais pesado dos pesados.

Forno alto
fonte
3

Você pode fazer uma passagem na lista para obter a média e o desvio padrão e usá-lo para aproximar o número de pessoas que precisam ir. Use o parcial_sort para gerar a lista com base nesse número. Se o palpite estiver baixo, use o parcial_sort novamente no restante com um novo palpite.

Mark Ransom
fonte
2

Aqui está uma solução baseada em heap usando o módulo heapq interno do Python. Está em Python, portanto, não responde à pergunta original, mas é mais limpo (IMHO) do que a outra solução 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)

Se k = o número de passageiros a lançar e N = o número de passageiros, o melhor caso para esse algoritmo é O (N) e o pior caso para esse algoritmo é Nlog (N). O pior caso ocorre se k estiver próximo de N por um longo período de tempo. Aqui está um exemplo do pior elenco:

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

No entanto, nesse caso (jogando pessoas fora do avião (com pára-quedas, presumo)), então k deve ser menor que 3000, ou seja, "milhões de pessoas". O tempo médio de execução deve, portanto, ser sobre o Nlog (k), que é linear ao número de pessoas.

Andrew Dalke
fonte