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

Question

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

Проблема

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

Пример

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

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

Ответ: 8

Answer 1

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

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

EDIT: Clue 2: Рассчитать каждый f (i) в порядке возрастания i. Имейте в виду, что каждый интервал будет либо присутствовать, либо отсутствовать. Чтобы вычислить оценку для «настоящего» случая, вам нужно будет искать «самый правый» интервал, совместимый с интервалом i, который потребует двоичного поиска через уже вычисленные вами решения.

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

Answer 2

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

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

Answer 3

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

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

Answer 4

Вот идея:

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

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

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

Answer 5

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