Нахождение подмножеств дизъюнктивных интервалов с максимальными весами

Question

Я ищу алгоритм, который мог бы использовать для решения этой проблемы, а не код.Я задавался вопросом об использовании линейного программирования с релаксацией, но, может быть, есть более эффективные способы решения этой проблемы?

Задача

У меня есть набор интервалов с весами.Интервалы могут перекрываться.Мне нужно найти максимальную сумму весов подмножеств дизъюнктивных интервалов.

Пример

Интервалы с весами:

|--3--|          |---1-----|
    |----2--| |----5----|

Ответ: 8

Answer 1

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

но в вашем случае я думаюЭто NPC (должен подумать об этом), но вы можете использовать аналогичный жадный алгоритм по значению каждый интервал по весу / длине, и каждый раз получать один из возможных интервалов в отсортированном формате. Также вы можете использовать имитационный отжиг, то есть каждый разполучить лучший ответ по указанному выше значению с вероятностью P (p близко к 1) или выбрать другой интервал с вероятностью 1- P.Вы можете сделать это в цикле while n раз, чтобы найти хороший ответ.

Answer 2

Вот идея:

Рассмотрим следующий график: создайте узел для каждого интервала.Если интервал I1 и интервал I2 не перекрываются и I1 предшествует I2, добавьте направленное ребро от узла I1 к узлу I2.Обратите внимание, что этот график ацикличен.Каждый узел имеет стоимость, равную длине соответствующего интервала.

Теперь идея состоит в том, чтобы найти самый длинный путь в этом графе, который можно найти за полиномиальное время для ациклических графов (используя динамическое программирование дляпример).Проблема в том, что затраты находятся в узлах, а не в краях.Вот хитрость: разбить каждый узел v на v 'и v' '.Все ребра, входящие в v, теперь будут вводить v ', а все ребра, выходящие из v, теперь будут выходить из v' '.Затем добавьте ребро из v 'в v' 'со стоимостью узла, в данном случае длиной интервала.Все остальные ребра будут стоить 0.

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

Answer 3

Я имею в виду точный алгоритм O (nlog n) DP .Поскольку это домашнее задание, вот подсказка:

Сортируйте интервалы по положению правого края, как подсказывает Саид, а затем пронумеруйте их с 1. Определите f (i) как наивысший достижимый вес, используя только интервалыне продолжайте правее правого края интервала i.

РЕДАКТИРОВАТЬ: Подсказка 2: Рассчитать каждый f (i) в порядке возрастания i.Имейте в виду, что каждый интервал будет либо присутствовать, либо отсутствовать.Чтобы рассчитать оценку для «настоящего» случая, вам нужно будет отыскать «самый правый» интервал, который совместим с интервалом i, что потребует двоичного поиска по решениям, которые вы уже вычислили.

Это была важная персона, я не уверен, что смогу дать больше подсказок, не объяснив ее полностью;)

Answer 4

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

Кроме того, то, что проблема может быть сформулирована как целочисленная программа (решение которой NP-Hard), не означает, что сам класс задачи является NP-Hard. Таким образом, как указывает Ульрих, может существовать полиномиально разрешимая формулировка / алгоритм, такой как постановка / решение задачи в виде линейной программы.

Answer 5

Правильное решение (от конца до конца) объясняется здесь: http://tkramesh.wordpress.com/2011/02/03/dynamic-programming-1-weighted-interval-scheduling/