|
Модифицированная задача о покрытии множества.
Добрый день,
Имеется следующая модицифированная задача о покрытии множества, в которой подмножетсва взвешенные и ориентированные. Множество, скажем
1,2,3,4,5,6,7,8,9,10 и подмножества
1,4,6 (вес (1->4) + (4->6) = 100 + 200 = 300)
3,2,4,6 (вес (3->2) + (2->4) + (4->6) = 10 + 5 + 125 + 200 = 340)
7,10...
.....
При объединений подмножеств, вес одинаковых пар (4->6) для первого и второго подмножества считается один раз.
Вопрос - как эффективно найти подмножества минимальной стоимости покрывающие исходное множетсво?
Заренее спасибо!
Последний раз редактировалось cat_baxter, 17.04.2011 в 23:49.
|
Линейный вид
