Сбрасывать самых перегруженных людей с перегруженного самолета.

Question

Допустим, у вас есть самолет, и у него мало топлива. Если самолет не сбросит 3000 фунтов веса пассажира, он не сможет добраться до следующего аэропорта. Чтобы сохранить максимальное количество жизней, мы хотели бы сначала сбросить с самолета самых тяжелых людей.

И о, да, в самолете миллионы людей, и мы хотели бы найти оптимальный алгоритм поиска самых тяжелых пассажиров без необходимости сортировки всего списка.

Это проблема с прокси для чего-то, что я пытаюсь кодировать на C ++. Я хотел бы сделать «part_sort» для пассажирского манифеста по весу, но я не знаю, сколько элементов мне понадобится. Я мог бы реализовать свой собственный алгоритм "partal_Sort "(" Partrial_Sort_accumulate_until "), но мне интересно, есть ли какой-нибудь более простой способ сделать это с использованием стандартного STL.

Answer 1

Однако это не поможет при проблемах с прокси:

Чтобы 1 000 000 пассажиров сбросили 3000 фунтов веса, каждый пассажир должен потерять (3000/1000000) = 0,003 фунта на человека. Этого можно добиться, сбросив каждую рубашку, обувь или, возможно, даже вырезанные ногти, чтобы спасти всех. Это предполагает эффективный сбор и сброс до того, как потеря веса увеличилась, поскольку самолет использовал больше топлива.

На самом деле, они больше не допускают кусачки для ногтей на борту, так что это не так.

Answer 2

Один из способов - использовать min кучу (std::priority_queue в C ++).Вот как вы это сделаете, если у вас класс MinHeap.(Да, мой пример на C #. Я думаю, вы поняли идею.)

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.

Согласно стандартным ссылкам, время выполнения должно быть пропорционально n log k, где n - это числопассажиры и k это максимальное количество элементов в куче.Если предположить, что вес пассажиров обычно составляет 100 фунтов или более, то маловероятно, что куча будет содержать более 30 предметов в любой момент.

Худший случай будет, если пассажиры представлены в порядкесамый низкий вес к самому высокомуДля этого потребуется, чтобы каждый пассажир был добавлен в кучу, а каждый пассажир был удален из кучи.Тем не менее, при миллионе пассажиров и при условии, что самый легкий вес составляет 100 фунтов, n log k работает до достаточно небольшого числа.

Если вы случайно выбираете вес пассажиров, производительность значительно улучшается.Я использую что-то вроде этого для механизма рекомендаций (я выбираю лучшие 200 пунктов из списка из нескольких миллионов).Я обычно заканчиваю тем, что добавляю в кучу только 50 000 или 70 000 элементов.

Я подозреваю, что вы увидите нечто очень похожее: большинство ваших кандидатов будут отклонены, потому что они легче, чем самый легкий человек.уже в куче.И Peek является операцией O(1).

Для получения дополнительной информации о производительности выбора и быстрого выбора кучи см. Когда теория соответствует практике .Короткая версия: если вы выбираете менее 1% от общего количества предметов, то выбор кучи - явный победитель быстрого выбора.Более 1%, затем используйте быстрый выбор или такой вариант, как Introselect .

Answer 3

Ниже приведена довольно простая реализация простого решения. Я не думаю, что есть более быстрый способ, который на 100% правильный.

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

Это работает, заполняя набор «мертвых людей», пока не достигнет порога. Как только порог достигнут, мы продолжаем просматривать список пассажиров, пытаясь найти тех, кто тяжелее самого легкого мертвого человека. Найдя их, мы добавляем их в список, а затем начинаем «Сохранять» самых легких людей из списка, пока не можем больше сохранять.

В худшем случае это будет работать примерно так же, как и весь список. Но в лучшем случае («мертвый список» правильно заполняется первыми X людьми) он будет выполнять O(n).

Answer 4

При условии, что все пассажиры будут сотрудничать: используйте сеть параллельной сортировки . (см. также это )

Вот живая демонстрация

Обновление: Альтернативное видео (переход на 1:00)

Попросите пары людей сравнить-обменяться - вы не можете получить быстрее, чем это.

Answer 5

@ Blastfurnace был на правильном пути. Вы используете быстрый выбор, где стержни являются порогами веса. Каждый раздел разбивает один набор людей на наборы и возвращает общий вес для каждого набора людей. Вы продолжаете разбивать соответствующее ведро до тех пор, пока ваши ведра, соответствующие людям с самым высоким весом, не превысят 3000 фунтов, а ваше самое низкое ведро, которое находится в этом наборе, имеет 1 человека (то есть его нельзя разделить дальше).

Этот алгоритм амортизируется по линейному времени, но в наихудшем квадратичном случае. Я думаю, что это единственный алгоритм линейного времени .

---

Вот решение Python, которое иллюстрирует этот алгоритм:

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

Выход:

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 6

Предполагая, что, подобно весам людей, у вас есть хорошее представление о том, какие максимальные и минимальные значения, вероятно, будут использоваться для сортировки по осям, чтобы отсортировать их по O (n).Тогда просто работайте от самого тяжелого конца списка к самому легкому.Общее время работы: O (n).К сожалению, в STL нет реализации радикальной сортировки, но написать ее довольно просто.

Answer 7

Массово параллельный турнир Сортировка: -

Предполагая три стандартных места с каждой стороны от прохода: -

1. Попросите пассажиров на сиденье у окна перейти ксреднее сиденье, если оно тяжелее человека на сиденье у окна.

2. Попросите пассажиров на среднем сиденье поменяться местами с пассажиром на месте у прохода, если они тяжелее.

3. Попросите пассажира на левом месте прохода поменяться с пассажиром на правом месте прохода, если они тяжелее.

4. Пузырьки отсортируют пассажиров справаместо у прохода.(Делает n шагов для n строк).- попросите пассажиров в правом сиденье у прохода поменяться с лицом вперед n -1 раз.

5 Выбивайте их из двери, пока не наберете 3000 фунтов.

3 шага + n шагов плюс 30 шагов, если у вас действительно тощий пассажирский груз.

Для двухпроходного самолета - инструкции более сложны, но производительность примерно одинакова.

Answer 8

Почему бы вам не использовать частичную быструю сортировку с правилом прерывания, отличным от "отсортированного". Вы можете запустить его, а затем использовать только верхнюю половину и продолжать до тех пор, пока вес в этой верхней половине не будет содержать вес, который, по крайней мере, должен быть отброшен больше, чем вы вернетесь на один шаг в рекурсии и отсортируете список. После этого вы можете начать выбрасывать людей из верхней части этого отсортированного списка.

Answer 9

Я бы, вероятно, использовал std::nth_element, чтобы разделить 20 самых тяжелых людей за линейное время. Затем используйте более сложный метод, чтобы найти и отбить самые тяжелые из них.

Answer 10

@ Джеймс имеет ответ в комментариях: a std::priority_queue, если вы можете использовать любой контейнер, или комбинацию std::make_heap и std::pop_heap (и std::push_heap), если вы хотите использовать что-то вроде std::vector.