Алгоритм для нахождения максимальной суммы в последовательности перекрывающихся интервалов
Проблема, которую я пытаюсь решить, имеет список интервалов на числовой оси, каждом с предопределенным счетом. Я должен возвратить максимальный возможный общий счет.
Выгода - то, что интервалы накладываются, и перекрывающихся интервалов я могу использовать только один. Вот пример.
Intervals - Score
0- 5 - 15
4- 9 - 18
10-15 - 12
8-21 - 19
25-30 - 25
Здесь, интервалы 0-5, перекрытие 8-21 и 4-9.
Интервалы 10-15 и 8-21 также перекрытие.
Максимальная сумма была бы 55 (18+12+25).
Важно отметить здесь, что мы выбираем интервал 4-9 из первого пакета перекрывающихся интервалов даже при том, что это не имеет самого высокого счета трех.
Это вызвано тем, что выбор интервала 8-21 препятствовал бы тому, чтобы мы использовали интервал 10-15 позже, таким образом, уменьшая полную сумму (В этом случае, полная сумма будет 19+25=44).
Я ищу O (nlogn) или O (n) решение этой проблемы. Я думаю, что динамическое программирование может использоваться, но я могу быть неправым. Кто-то мог предложить решение (решения)/алгоритм, которое могло добиться цели здесь?
Править: Интервалы без определенного порядка.
5 ответов
Это взвешенная вариация интервального планирования; она решается за O(N log N) с помощью динамического программирования.
Пусть интервал - это g(start, stop, score), и пусть они отсортированы по stop. Для простоты предположим пока, что все stop уникальны.
Пусть best[i] - это лучший результат, который мы можем получить, если нам разрешено использовать g[1], ..., g[i]. Конечно, мы не обязаны использовать их все, и вообще не можем, потому что подмножество интервалов, которые мы используем, должно быть непересекающимся.
- Очевидно, что
best[0] = 0. То есть, поскольку мы не можем использовать любой интервал, то наилучшая оценка, которую мы можем получить, равна 0. - Для любого
1 <= k <= N, имеем:best[k] = max( best[k-1], best[j] + g[k].score ), где.j- наибольший индекс, такой, чтоg[j].stop < g[k].start(jможет быть нулем)
То есть, учитывая, что нам разрешено использовать g[1], ... g[k], лучшее, что мы можем сделать - это лучшая оценка этих двух вариантов:
- Мы не включаем
g[k]. Таким образом, оценка этого варианта равнаbest[k-1]- ... потому что это лучшее, что мы можем сделать с
g[1], ... g[k-1]
- ... потому что это лучшее, что мы можем сделать с
- Мы включаем
g[k], а слева от него делаем лучшее, что можем, со всеми генами, которые не пересекаются сg[k], т.е. всеg[k]. т.е. всеg[1], ..., g[j], гдеg[j].stop < g[k].startиjкак можно больше. Таким образом, оценка этого варианта равнаbest[j] + g[k].score.
(Обратите внимание на оптимальную подструктуру и перекрывающиеся компоненты подпроблем динамического программирования, воплощенные в приведенном выше уравнении).
Общий ответ на вопрос - best[N], т.е. лучший результат, который мы можем получить, когда нам разрешено использовать все гены. Упс, я сказал гены? Я имею в виду интервалы.
Это O(N log N), потому что:
- Сортировка всех интервалов занимает
O(N log N) - Нахождение
jдля каждогоkсоставляетO(log N)при использовании двоичного поиска
Если несколько генов могут иметь одинаковые stop значения, то ничего не изменилось: вам по-прежнему придется искать самый правый j. В Python, например, это легко сделать с помощью bisect_right. В Java, где бинарный поиск стандартной библиотеки не гарантирует, какой индекс будет возвращен в случае равенства, вы можете (среди многих вариантов) использовать линейный поиск (для O(N) наихудшей производительности) или другую серию бинарных поисков, чтобы найти самый правый индекс.
Упс, я опять сказал "гены"? Я имел в виду интервалы.
Похожие вопросы
Во-первых, я думаю, что максимум 59, а не 55. Если выбрать интервалы [0-5], [8-21] и [25,30], то получится 15+19+25=59. Для решения этой задачи можно использовать что-то вроде динамического программирования.
Сначала вы сортируете все интервалы по их начальной точке, затем выполняете итерацию от конца к началу. Для каждого элемента списка вы выбираете максимальную сумму от этой точки до последней как max(S[i]+S[j], S[i+1]), где i - элемент, на котором вы находитесь, j - элемент, который является первой непересекающейся записью после вашего элемента (то есть первый элемент, начало которого больше конца текущего элемента). Чтобы ускорить алгоритм, вы хотите хранить максимальную частичную сумму S[j] для каждого элемента.
Чтобы пояснить, позвольте мне решить ваш пример следующим образом. Сначала отсортируйте интервалы:
1: 0- 5 - 15
2: 4- 9 - 18
3: 8-21 - 19
4: 10-15 - 12
5: 25-30 - 25
Итак,
S[5] = 25
S[4] = max(12+S[5], 25)=37
S[3] = max(19+S[5], S[4])=max(19+25,37)=44
S[2] = max(18+S[4], S[3])=max(18+37,44)=55
S[1] = max(15+S[3], S[2])=max(15+44, 55)=59
Это адаптация алгоритма из этого поста, но, к сожалению, не имеет приятного времени работы O(n). Для вырожденного списка, где каждая запись перекрывает следующую, это время будет O(n^2).
Звучит как вариация на тему задачи о ранце. Вы можете найти некоторое вдохновение в поиске этих решений.
О скольких интервалах идет речь? Если всего около 5 (как в вашем примере), то, вероятно, практичнее просто попробовать все комбинации. Если больше, то подойдет ли приближенное идеальное решение? Опять же, решения Knapsack (такие как жадный алгоритм аппроксимации Джорджа Данцига) могут быть хорошим местом для начала.
Возможно, можно было бы использовать подход, как в этом ответе, который является O(n), по крайней мере, для этой задачи. Это будет означать однократное прохождение итераций по интервалам и отслеживание только тех комбинаций интервалов, которые все еще могут привести к оптимальному окончательному решению.
Я немного подумал и кое-что придумал.
Деревья интервалов обеспечивают эффективный способ поиска всех интервалов, которые перекрывают данный интервал. Пройдя через весь набор интервалов, мы можем найти все перекрывающиеся интервалы для данного. Когда они у нас есть, мы можем найти интервал с наибольшим количеством очков, сохранить его и двигаться дальше.
Построение дерева занимает O (N Log N) времени, а поиск занимает O (Log N) времени. Поскольку мы ищем все элементы, решение становится O (N Log N).
Однако, если мы сталкиваемся с чем-то вроде приведенного выше примера, где интервал наивысшего балла в одной группе уменьшает общую сумму, алгоритм не работает, потому что у нас нет возможности узнать, что интервал наивысшего балла не должен использоваться заранее. Очевидный способ обойти это - вычислить оба (или все) итоговые значения, если мы не уверены, но это возвращает нас к потенциально O (N ^ 2) или худшему решению.