Найти оптимальное решение, которое минимизирует ограничение?

Question

Давайте назовем эту проблему проблемой Slinger-Bird (на самом деле Slinger аналогичен серверу, а птица - запросу, но у меня был нервный срыв, когда я думал об этом, поэтому я изменил их, надеясь получить другую точку зрения!),

• Есть S метателей камней (стропальщики) и B птиц.
• Стропальщики не находятся в пределах досягаемости друг друга.
• Строп один раз может убить всех птиц в поле зрения стропальщика и потребует один выстрел и одну единицу времени

Я пытаюсь найти оптимальное решение, которое минимизирует время и количество выстрелов, необходимых для того, чтобы убить птиц с учетом конкретной схемы прибытия птиц.Позвольте мне привести пример с абсолютными числами: 3 слингера и 4 птицы.

        Time        1            2            3           4             5
Slinger
S1                B1, B2     B1, B2, B3       B4
S2                               B1         B1, B2      B3,B4     
S3                  B1         B3, B4                 B1,B2,B3,B4

и мои данные выглядят так:

>> print t
[
  {
    1: {S1: [B1, B2], S2: [], S3: [B1]}, 
    2: {S1: [B1, B2, B3], S2: [B1], S3: [B3, B4]},
    3: {S1: [B4], S2: [B1,B2], S3: []},
    4: {S1: [], S2: [B3, B4], S3: [B1, B2, B3, B4]}
  }
]

Есть несколько решений, о которых я мог бы подумать (Sx при t = k подразумевает, что слингер Sx делает выстрел во времениk):

1. S1 при t = 1, S1 при t = 2, S1 при t = 3 <- <strong>Стоимость : 3 выстрела + 3 единицы времени = 6
2. S1 при t = 2, S1 при t = 3 <- <strong>Стоимость : 2 снимка + 3 единицы времени = 5
3. S1 при t = 1, S3 при t = 2 <- <strong>Стоимость : 2 выстрела + 2 единицы времени = 4
4. S3 при t = 4 <- <strong>Стоимость : 1 выстрел + 4 единицы времени = 5

Мне кажется, что решение 3 является оптимальным в этом.Конечно, я сделал это вручную (так что есть вероятность, что я что-то упустил), но я не могу придумать масштабируемый способ сделать это.Кроме того, я обеспокоен тем, что есть крайние случаи, потому что решение одного стрелка может изменить решение других, но поскольку у меня есть глобальная точка зрения, возможно, это не имеет значения.

Что такое быстрый и хороший способ решения этой проблемы в python?Мне трудно придумать хорошую структуру данных, чтобы сделать это, оставив в покое алгоритм для этого.Я думаю об использовании динамического программирования, потому что это, кажется, связано с исследованием пространства состояний, но я немного запутался в том, как действовать дальше.Есть предложения?

Answer 1

Это не оптимальная задача назначения, потому что стропальщики убивают всех птиц в поле зрения.

У вас есть двумерная целевая функция, поэтому между выстрелами и временем может быть несколько компромиссов.Определение минимального количества снимков для определенного временного предела является точно установленной проблемой покрытия (как предполагает mhum).Задача накрытия по множеству является NP-трудной и трудной для аппроксимации, но на практике ветвление и связывание с использованием двойственной формулировки линейного программирования достаточно эффективно для нахождения оптимального значения.

Answer 2

Я предполагаю, что вы знаете все числа, которые вы даете в примере при запуске алгоритма, и не получаете t2 после окончания t1 и т. Д.

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

При первом выборе вы можете присвоить значение каждой ячейке, являясь amountOfBirdsInCell-time.

Это дает вам две ячейки со значениями 1,Будучи S1t1, S1t2, остальное ниже.

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

Теперь удалите птиц, убитых в этом первом выборе, из всех ячеек.

Повторите процесс определения значения для остальных ячеек.В вашем примере, ячейка S3t2 даст наивысший результат, равный 0.

Повторяя этот процесс, вы получите самые ценные ячейки в самое раннее время.

Один важный бит, который ваш пример не делаетпокрытие: если ваш первый самый ценный выбор - в t2, следующий самый ценный - может быть в t1 или t2, поэтому вы должны принять это во внимание.Однако, поскольку t2 уже подтверждено, вы не должны принимать во внимание их время для их значения.

Я никогда не писал на python, я просто здесь из-за тега алгоритма, так что вот некоторые java /c-подобный псевдокод:

highestCellTime = 0;
while(birdsRemain)
{
    bestCell;

    for(every cell that has not been picked yet)
    {
        currentCellValue = amountOfBirds;
        if(currentCellTime > highestCellTime)
        {
            currentCellValue = currentCellValue - currentCellTime;
        }

        if(currentCellValue < bestCellValue)
        {
            bestCell = thisCell;
        }
        else if(currentCellValue == bestCellValue && currentCellTime < bestCellTime)
        {
            bestCell = thisCell;
        }
    }
    addCellToPicks(bestCell);
    removeBirdsFromOtherCells(bestCellBirds);
}

Если я ничего не забыл, у вас теперь есть оптимальная комбинация ячеек в вашей коллекции выбора.

Надеюсь, этот код имеет смысл для программиста на Python.Если кто-то может перевести это, пожалуйста, сделайте!И, пожалуйста, удалите этот фрагмент текста и упоминание ранее java / c-псевдокода.

РЕДАКТИРОВАТЬ OP : Первая версия и не заканчивается лучшими ячейками.Я предполагаю, что это должно быть ошибка в моем коде, но тем не менее я публикую здесь.

import math

cellsNotPicked = range(0,12)
cellToBird = {
    0: [1, 2],
    1: [],
    2: [1],
    3: [1,2,3],
    4: [1],
    5: [3,4],
    6: [4],
    7: [1,2],
    8: [],
    9: [],
    10: [3,4],
    11: [1,2,3,4]
}

picks = []

def getCellValue(cell):
    return len(cellToBird[cell])

def getCellTime(cell):
    return int(math.floor(cell / 3)) + 1

birdsRemain = 4

while(birdsRemain > 0):

    bestCell = 0;

    for thisCell in cellsNotPicked:

        currentCellValue = getCellValue(thisCell);

        currentCellTime = getCellTime(thisCell)
        highestCellTime = getCellTime(bestCell)

        if(currentCellTime > highestCellTime):
            currentCellValue = currentCellValue - currentCellTime;

        if(currentCellValue < getCellValue(bestCell)):
            bestCell = thisCell
        elif (currentCellValue == getCellValue(bestCell)) and (currentCellTime < getCellTime(bestCell)):
            bestCell = thisCell

    picks.append(bestCell)
    cellsNotPicked.remove(bestCell)

    birdsToRemove = cellToBird[bestCell]

    for key in cellToBird:
        for bird in birdsToRemove:
            try:
                cellToBird[key].remove(bird)
                birdsRemain -= 1
            except:
                pass

print picks

Answer 3

Я предлагаю использовать растровые изображения для стропальщиков и птиц, т.е.

S1 = B1 = 1, S2 = B2 = 2, S3 = B3 = 4, B4 = 8

Тогда входные данные можно записать в виде

bird_data = [[3, 0, 1], [7, 1, 12], [8, 3, 0], [0, 12, 15]]

Теперь функцию стоимости можно записать так:

def cost(shots):
    hit = units = 0
    for show, shot in zip(bird_data, shots):
        units += 1
        for n, birds in enumerate(show):
            if shot & 1:
                units += 1
                hit |= birds
                if hit == 15: # all are hit
                    return units
            shot >>= 1
    return 99 # penalty when not all are hit

Теперь легко найти оптимальные кадры, рассчитав функцию минимума стоимости:

from itertools import product

shot_sequences = product(*([range(7)]*len(bird_data)))

print min((cost(shots), shots) for shots in shot_sequences)

Это напечатает

(4, (0, 5, 0, 0))

, что означает оптимальный4 единицы, когда S1 и S3 (5 = 1 + 4) срабатывают при t = 2.Конечно, ваше решение также возможно, когда S1 стреляет в t = 1 и S3 в t = 2, оба имеют одинаковую стоимость.

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