Алгоритм (решение проблемы), обеспечивающий максимальную скорость выполнения

Ответ 1

Предположим, что список houses состоит из пар (x,pop) с 0 <= x < 4*L местоположением и pop населением.

Целевая функция, которую мы хотим максимизировать,

def revenue(i):
    return sum(pop * min((i-j)%(4*L), 4*L - (i-j)%(4*L)) for j,pop in houses)

Алгоритм наивного алгоритма O (LN) просто:

max_revenue = max(revenue(i) for i in range(4*L))

Но невероятно расточительно полностью переоценить revenue для каждого местоположения.

Чтобы избежать этого, обратите внимание, что это кусочно-линейная функция; поэтому его производная является кусочно-постоянной, с разрывами в двух типах точек:

• в доме i производная изменяется от slope до slope + 2*population[i]
• в точке, расположенной напротив дома i на острове, производная изменяется от slope до slope - 2*population[i]

Это делает вещи очень простыми:

• Нам нужно только изучить фактические дома или противоположные дома, поэтому сложность падает до O (N²).
• Мы знаем, как обновить slope из дома i-1 до дома i, и для этого требуется только время O (1).
• Поскольку мы знаем доход и наклон в местоположении 0, и поскольку мы знаем, как обновлять slope итеративно, сложность фактически падает до O (N): между двумя соседними домами/противоположными домами, мы может просто умножить наклон на расстояние, чтобы получить разницу в доходах.

Таким образом, полный алгоритм:

def algorithm(houses, L):
    def revenue(i):
        return sum(pop * min((i-j)%(4*L), 4*L - (i-j)%(4*L)) for j,pop in houses)

    slope_changes = sorted(
            [(x, 2*pop) for x,pop in houses] +
            [((x+2*L)%(4*L), -2*pop) for x,pop in houses])

    current_x = 0
    current_revenue = revenue(0)
    current_slope = current_revenue - revenue(4*L-1)
    best_revenue = current_revenue

    for x, slope_delta in slope_changes:
        current_revenue += (x-current_x) * current_slope
        current_slope += slope_delta
        current_x = x
        best_revenue = max(best_revenue, current_revenue)

    return best_revenue

Чтобы упростить задачу, я использовал sorted() для слияния двух типов изменений наклона, но это не является оптимальным, так как имеет сложность O (N log N). Если вы хотите повысить эффективность, вы можете создать в O (N) время отсортированный список, соответствующий противоположным домам, и объединить его со списком домов в O (N) (например, со стандартной библиотекой heapq.merge), Вы также можете передавать из итераторов вместо списков, если хотите минимизировать использование памяти.

TL;DR: это решение достигает наименьшей возможной сложности O (N).

Ответ 2

Ниже представлено менее математическое решение, которое работает в O(n).

Разделим дома (индексирование начинается с 0) на два непересекающихся множества:

• F, "front", где люди ходят по CCW в дом.
• B, "назад", где люди ходят в дом

и один дом p, который обозначает текущее положение, в котором будет строиться завод.

Я основал свою иллюстрацию на примере, приведенном на изображении.

По соглашению, давайте присвойте половине домов F и ровно один раз меньше B.

• F содержит 6 домов
• B содержит 5 домов

С простой модульной арифметикой мы можем легко получить доступ к домам с помощью (p + offset) % 12 благодаря правильной реализации Python оператора modulo, в отличие от some прочее популярный языки.

Если мы произвольно выберем положение для p, мы можем тривиально определить потребление воды в O(L).

Мы могли бы сделать это снова и снова для другой позиции p для выполнения во время выполнения O(L^2).

Однако, если мы только сдвинем p на одну позицию, мы можем определить новое потребление в O(1), если мы сделаем несколько умное наблюдение: количество людей, живущих в F (или B соответственно) определить, насколько изменяется потребление F при установке p' = p+1. (и некоторые поправки, потому что сам F изменится). Я попытался изобразить это здесь в меру своих возможностей.

В итоге получится общее время работы O(L).

Программа для этого алгоритма находится в конце сообщения.

Но мы можем сделать лучше. Пока никакие дома не меняются между наборами, добавляемые c и w будут равны нулю. Мы можем рассчитать, сколько из этих шагов есть и сделать их за один шаг.

Сборы для смены домов, когда:  - Когда p находится в доме  - Когда p противоположно дому

На следующей диаграмме я визуализировал остановки, которые теперь делает алгоритм для обновления c и w s. Выделен дом, который заставляет алгоритм останавливаться.

Алгоритм начинается в доме (или наоборот, мы увидим, почему позже), в данном случае это дом.

Опять же, у нас есть как потребление C(B) = 3*1, так и C(F) = 2 * 1. Если мы сдвинем p вправо на единицу, добавим 4 в C(B) и вычтем 1 из C(F). Если мы снова сдвинем p, произойдет то же самое.

Пока те же самые два набора домов перемещаются ближе и дальше соответственно, изменения в c являются постоянными.

Теперь немного изменим определение B: теперь оно также будет содержать p! (Это не изменяет вышеприведенные параграфы относительно этой оптимизированной версии алгоритма).

Это делается потому, что, когда мы переходим к следующему шагу, мы добавим массу домов, которые уходят многократно. Дом в текущей позиции отходит, когда p перемещается вправо, таким образом W(B) - это правильное слагаемое.

Другой случай - когда дом перестает двигаться и снова приближается. В этом случае c резко меняется, потому что 6*weight переходит от одного c к другому. Это другой случай, когда нам нужно остановиться.

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

О (п):

import itertools

def hippo_island(houses, L):
    return PlantBuilder(houses, L).solution

class PlantBuilder:
    def __init__(self, houses, L):
        self.L = L
        self.houses = sorted(houses)
        self.changes = sorted(
            [((pos + L /2) % L, -transfer) for pos, transfer in self.houses] + 
            self.houses)
        self.starting_position = min(self.changes)[0]

        def is_front(pos_population):
            pos = pos_population[0]
            pos += L if pos < self.starting_position else 0
            return self.starting_position < pos <= self.starting_position + L // 2

        front_houses = filter(is_front, self.houses)
        back_houses = list(itertools.ifilterfalse(is_front, self.houses))

        self.front_count = len(houses) // 2
        self.back_count = len(houses) - self.front_count - 1
        (self.back_weight, self.back_consumption) = self._initialize_back(back_houses)
        (self.front_weight, self.front_consumption) = self._initialize_front(front_houses)
        self.solution = (0, self.back_weight + self.front_weight)
        self.run()

    def distance(self, i, j):
        return min((i - j) % self.L, self.L - (i - j) % self.L)

    def run(self):
        for (position, weight) in self.consumptions():
            self.update_solution(position, weight)

    def consumptions(self):
        last_position = self.starting_position
        for position, transfer in self.changes[1:]:
            distance = position - last_position
            self.front_consumption -= distance * self.front_weight
            self.front_consumption += distance * self.back_weight

            self.back_weight += transfer
            self.front_weight -= transfer

            # We are opposite of a house, it will change from B to F
            if transfer < 0:
                self.front_consumption -= self.L/2 * transfer
                self.front_consumption += self.L/2 * transfer


            last_position = position
            yield (position, self.back_consumption + self.front_consumption)

    def update_solution(self, position, weight):
        (best_position, best_weight) = self.solution
        if weight > best_weight:
            self.solution = (position, weight)

    def _initialize_front(self, front_houses):
        weight = 0
        consumption = 0
        for position, population in front_houses:
            distance = self.distance(self.starting_position, position)
            consumption += distance * population
            weight += population
        return (weight, consumption)

    def _initialize_back(self, back_houses):
        weight = back_houses[0][1]
        consumption = 0
        for position, population in back_houses[1:]:
            distance = self.distance(self.starting_position, position)
            consumption += distance * population
            weight += population
        return (weight, consumption)

О (Л)

def hippo_island(houses):
    return PlantBuilder(houses).solution

class PlantBuilder:
    def __init__(self, houses):
        self.houses = houses
        self.front_count = len(houses) // 2
        self.back_count = len(houses) - self.front_count - 1
        (self.back_weight, self.back_consumption) = self.initialize_back()
        (self.front_weight, self.front_consumption) = self.initialize_front()
        self.solution = (0, self.back_weight + self.front_weight)
        self.run()

    def run(self):
        for (position, weight) in self.consumptions():
            self.update_solution(position, weight)

    def consumptions(self):
        for position in range(1, len(self.houses)):
            self.remove_current_position_from_front(position)

            self.add_house_furthest_from_back_to_front(position)
            self.remove_furthest_house_from_back(position)

            self.add_house_at_last_position_to_back(position)
            yield (position, self.back_consumption + self.front_consumption)

    def add_house_at_last_position_to_back(self, position):
        self.back_weight += self.houses[position - 1]
        self.back_consumption += self.back_weight

    def remove_furthest_house_from_back(self, position):
        house_position = position - self.back_count - 1
        distance = self.back_count
        self.back_weight -= self.houses[house_position]
        self.back_consumption -= distance * self.houses[house_position]

    def add_house_furthest_from_back_to_front(self, position):
        house_position = position - self.back_count - 1
        distance = self.front_count
        self.front_weight += self.houses[house_position]
        self.front_consumption += distance * self.houses[house_position]

    def remove_current_position_from_front(self, position):
        self.front_consumption -= self.front_weight
        self.front_weight -= self.houses[position]

    def update_solution(self, position, weight):
        (best_position, best_weight) = self.solution
        if weight > best_weight:
            self.solution = (position, weight)

    def initialize_front(self):
        weight = 0
        consumption = 0
        for distance in range(1, self.front_count + 1):
            consumption += distance * self.houses[distance]
            weight += self.houses[distance]
        return (weight, consumption)

    def initialize_back(self):
        weight = 0
        consumption = 0
        for distance in range(1, self.back_count + 1):
            consumption += distance * self.houses[-distance]
            weight += self.houses[-distance]
        return (weight, consumption)

Результат:

>>> hippo_island([0, 3, 0, 1, 0, 0, 0, 0, 0, 0, 1, 2])
(7, 33)

Ответ 3

Я предоставлю несколько советов, чтобы у вас все еще есть возможность для себя.

Позвольте мне начать с упрощенной версии:

На прямой улице есть N домов, либо либо заполнено, либо пусто.

0 1 1 0 1

Позвольте рассчитать оценку для них, зная, что в n-м доме есть оценка, равная сумме всех расстояний до других домов, которые не являются пустыми. Таким образом, оценка первого дома 1+2+4 = 7, так как есть 3 других населенных дома, и они находятся на расстоянии 1, 2, 4.

Полный массив баллов выглядит следующим образом:

7 4 3 4 5

Как рассчитать это? Очевидный подход...

for every house i
    score(i) = 0
    for every other house j
        if j is populated, score(i) += distance(i, j)

Это дает вам сложность O (N ^ 2). Однако есть более быстрый способ, который вычисляет все оценки в O (N), потому что в нем нет вложенного цикла. Это связано с префиксом сумм. Вы можете найти его?

Ответ 4

Нет необходимости вычислять каждый дом!!!

Он не полностью развит, но я думаю, что стоит подумать об этом:

по модулю N

N - количество всех домов, n - "адрес" (количество) некоторых домов.

Если вы ходите по острову, вы обнаружите, что n поднимает на 1 для каждого дома, который вы проходите. Если вы дойдете до дома, где n - N, то следующий дом имеет номер 1.

Воспользуемся другой системой нумерации: увеличьте количество каждого дома на 1. Затем n переходит от 0 до N-1. это точно так же, как будут вести себя номера по модулю N.

Литеры - это функция номера дома n (по модулю N)

Вы можете рассчитать количество литров за каждый номер дома, построив сумму всех продуктов расстояния и людей, живущих там.

Вы также можете нарисовать график этой функции: x есть n, y - количество литров.

функция периодическая

Если вы понимаете, что означает по модулю, вы поймете, что график, который вы только что нарисовали, является всего лишь одним периодом периодической функции, так как Liter (n) ist eaqual to Liter (n + x * N), где x - целое число (это тоже может быть отрицательным).

, если N велико, функция "Псевдо-непрерывная"

Что я имею в виду: если N действительно большой, тогда количество литров не изменится очень сильно, если вы перейдете от дома a к его соседу, разместите a + 1. Таким образом, вы можете использовать методы интерполяции.

вы ищете место "глобального" максимума периодической псевдо-непрерывной функции (только на самом деле глобально в течение одного периода)

Это мое предложение:

Шаг 1: выберите расстояние d, которое больше 1 и меньше N. Я не могу сказать, почему, но я бы использовал d = int (sqrt (N)) (возможно, может быть лучший выбор, попробуйте это).
Шаг 2: вычислить литеры для дома 0, d, 2d, 3d,... Шаг 3: вы найдете некоторые значения, которые выше, чем их соседи. Используйте эти высокие точки, и их соседи подают их, используя метод интерполяции, чтобы вычислить больше точек, близких к этим точкам (интервальное расщепление).

Повторяйте эту интерполяцию для других высоких точек, пока у вас есть время (у вас есть 1 секунда, что долгое время!)

Переходите с одной высокой точки на другую, если видите, что глобальный максимум должен быть в другом месте.