Выберите оптимальное минимальное количество элементов для охвата региона

Question

У меня проблема оптимизации. Я никогда не изучал алгоритмы, только учил себя python, поэтому я не уверен, что это трудная или легкая проблема для решения. Не абстрактное применение этой проблемы - это определение самого дешевого способа последовательности ДНК с использованием доступных реагентов. Теперь проблема ...

Существует круговая область, скажем 0-10, где 10 обращается назад к 0. Есть элементы длины 1, каждая из которых охватывает часть региона и конечной целью является минимизация количество элементов при покрытии каждой позиции. У меня есть несколько элементов длины 1, но эти элементы не охватывают весь регион. Поэтому мне нужно будет добавить дополнительные элементы по цене.

Таким образом, окончательная стоимость будет примерно равна (количество элементов) + 2 (количество приобретенных элементов), и целью было бы свести к минимуму стоимость. Легко ли решить эту проблему или потребовать значительных усилий для ее решения?

Таким образом, в этом примере, я выбрал бы добавить значение примерно в 2 и 5,75, и удалить некоторые значения около 2,5.

Answer 1

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

Предположим, что ваши элементы имеют два свойства: begin и end, которые определяют координату X, где они соответственно, ну, начинаются и заканчиваются! (Даже если ваш конец всегда начинается + 1. Если элемент начинается с 9.5, считайте, что он заканчивается на 10.5 вместо 0,5)

Поместите все свои элементы в массив elem [] и отсортируйте их с нижним begin. Скопируйте первый элемент и поместите его в конец массива, увеличивая 10 как на своих begin, так и на end координатах. (так что это может стать чем-то вроде 10.2-11.2). Это должно охватывать круглый аспект вашей проблемы, мы используем его только для справки, но не считаем это дважды в расходах.

X = 0 (the farthest you have got covered so far) 
foreach element i in array, in order, except for last element: 
    if elem[i+1].begin <= X 
    continue; // this means you dont need the current element, discard it and go to the next iteration of the loop. 
    if elem[i].begin <= X 
    X = elem[i].end // you will use this element to expand your reach 
    else // bad news, you got an empty hole 
    add_elements += ceil(elem[i].begin - X) // ceil = round up to an integer number of elements needed to cover the hole 
    X = elem[i].end // you will use this element anyway! 

if X < 10 // after the loop ends 
    add_elements += ceil(elem[last].begin - X) 

Вы можете переписать последний, если/еще требовать просто if, я просто подумал, что этот путь будет более дидактический и легче понять.

add_elements содержит количество дополнительных элементов, которые необходимо добавить. Функция ceil() такова, что если у вас есть непрерывное отверстие длиной 2,4, вы знаете, что вам нужно как минимум 3 новых элемента, чтобы исправить это.

Этот алгоритм довольно прост и быстр, сложность времени O (n logn) из-за начальной сортировки, так как я не знаю, сколько элементов вам нужно обрабатывать. Вы не можете получить его дешевле, чем это с помощью координат с плавающей запятой.

Possibility of improvement: Когда вы знаете, есть отверстие, которое необходимо добавить новые элементы, чтобы исправить, можно было бы отказаться от ранее определен элемента, либо в начале и/или в конце отверстия. Например, рассмотрим элементы {(0,1), (0,7, 1,7), (1,8, 2,8), (2,3)}. Между вторым и третьим элементами есть отверстие длиной 0,1, но если вы добавите новый элемент длины 1 и поместите его между 1.0 и 2.0, вы можете фактически выбросить как второй, так и третий элементы.