Алгоритм для нахождения максимальной суммы в последовательности перекрывающихся интервалов

Ответ 1

Это взвешенная вариация интервальное планирование; он разрешен в 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[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) наихудшего исполнения) или другой серии двоичных ищет наиболее подходящий индекс.

К сожалению, я снова говорю гены? Я имею в виду интервалы.

Связанные вопросы

• Расширение бинарного поиска, чтобы найти первый и последний индекс значения ключа

Ответ 2

Прежде всего, я думаю, что максимум 59, а не 55. Если вы выберете интервалы [0-5], [8-21] и [25,30], вы получите 15 + 19 + 25 = 59. Для этого вы можете использовать какое-то динамическое программирование.

Сначала вы сортируете все интервалы по начальной точке, а затем итерации от начала до конца. Для каждого элемента в списке вы выбираете максимальную сумму от этой точки до последней как max(S[i]+S[j], S[i+1]), где я - элемент, на котором вы находитесь, 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).

Ответ 3

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

Ответ 4

Звучит как вариация проблемы Рунцака. Вы можете найти вдохновение в поиске этих решений.

Сколько интервалов мы говорим? Если это всего около 5 (как в вашем примере), то, вероятно, более практично просто попробовать каждую комбинацию. Если это будет больше, будет ли выполнено приближение идеального решения? Опять же, решения Knapsack (такие как алгоритм жадного алгоритма Джорджа Данцига) могут стать хорошим началом для начала.

Ответ 5

Я подумал об этом немного и придумал что-то.

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

Построение дерева занимает O (N Log N), время и поиск - время O (Log N). Поскольку мы просматриваем все элементы, решение становится O (N Log N).

Однако, если мы сталкиваемся с чем-то вроде вышеприведенного примера, где наивысший интервал оценки в одной группе уменьшает общее число, алгоритм терпит неудачу, потому что мы не знаем, что самый высокий интервал оценки не должен использоваться раньше. Очевидным способом этого было бы вычисление как (или всех) итогов в случае, если мы не уверены, но это возвращает нас к потенциально O (N ^ 2) или худшему решению.

Ответ 6

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

S[i] обозначает оценку каждого интервала Interval[i] обозначает все интервалы

ResMax[i] = max(ResMax[i-1] + S[i] //if i is included
           ,max(R[i-1],S[i]) 
         )

Я не проверен полностью, но он должен работать, я верю.