Алгоритмы заполнения пространства?

Question

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

Представьте, что у нас есть диапазон или какая-то основная линия на бумаге. Теперь мы получили много меньших линий со случайно изменяемой длиной, плюс они указали, в каком диапазоне они начинаются. Мне нужно выбрать набор из этих меньших линий, чтобы места вместе, где мы могли видеть основную линию, были минимально возможными. Итак, в общем, мы пытаемся покрыть основную линию более мелкими кусками, которые наиболее эффективно определяют положение и длину.

Кроме ответа на вопрос о том, как выполнить эту задачу, я был бы рад узнать название этой проблемы, поскольку я уверен, что это довольно часто встречается при программировании и может быть также обобщено до большего числа измерений, чем одно *

Как напомнил мне Титон, ни одно совпадение не допускается (конечно, в противном случае это было бы совершенно бессмысленно)

Answer 1

Это немного напоминает мне http://en.wikipedia.org/wiki/Knapsack_problem, может быть, это немного помогает.

Answer 2

В этой задаче у вас есть набор отрезков линии L1 ... Ln, и некоторые из них перекрываются.Если два отрезка линии Li и Lj пересекаются, то, когда вы не можете иметь их оба в решении, установленном одновременно;таким образом, всякий раз, когда два отрезка линии перекрываются, существует ограничение эксклюзивности, что только один из них может присутствовать в наборе решений.Теперь каждый сегмент линии также имеет длину, которая является «значением» сегмента линии, и ваша задача эквивалентна запросу набора сегментов линии, который имеет максимальное значение, но в котором соблюдаются все ограничения эксклюзивности, т.е. нет перекрытиясегменты в решении.Тот факт, что исходная проблема сформулирована в терминах евклидовой геометрии и действительных чисел, не меняет того факта, что настоящая проблема является комбинаторной и конечной природы.

Это не KNAPSACK и не является SET COVER.,Это похоже на пример взвешенной SET PACKING ( Wikipedia ), но не составляют ли экземпляры проблемы здесь NP-полную проблему, я не знаю, потому что геометрия исходной задачи ограничивает структуры ограничений, которые могутбыть сгенерированным.Вероятно, это так.

ОБНОВЛЕНО

Это ответ @ mcdowella ниже, он не является NP-полным, но является примером проблемы, которая может быть эффективно решена.См. Комментарий ниже для всех ссылок и замечаний.

Answer 3

Для меня это выглядит как динамическое программирование. Прежде всего, рассортируйте интервалы, чтобы иметь дело с ними в неубывающем порядке крайней правой точки. Теперь мы попытаемся найти для каждого x лучший способ покрытия точек <= x. Когда мы выберем новый интервал, заканчивающийся в точке T, мы получим покрытие для точек <= T, и наилучший получится, посмотрев имеющиеся у нас решения, чтобы найти лучшее решение для точек <= S, где S - самая большая S <= левая точка нашего нового интервала. Вы можете быстро найти это лучшее соответствие, сохранив решения в отсортированной коллекции, например, в красном / черном дереве. </p>

Как только вы разберетесь со всеми вашими интервалами, вы сможете просмотреть все лучшие решения, учитывая тот факт, что некоторые из них закончатся до конца вашей линии, и выбрать победителя.

Answer 4

Эта проблема почти эквивалентна Задаче Set Cover , проблеме NP-завершения. Он отличается тем, что SCP определяется в терминах конечных множеств. Ваша версия может быть преобразована в эквивалентную взвешенную задачу SCP, и наоборот, за O (K log K) времени (K = количество сублиней) или почти в эквивалентную задачу SCP без взвешивания, в O (L / e) время, для L = длина главной линии и точность е.

В википедии В статье SCP упоминаются три метода аппроксимации: целочисленная линейная программа, формулировка набора множеств и жадный алгоритм.

Answer 5

Решение: выберите все отрезки.Вы не можете сделать лучше, потому что каждая точка, которая может быть покрыта, будет.