Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 18.04.2011, 00:11
Новичок

Отправить личное сообщение для cat_baxter Посмотреть профиль Найти все сообщения от cat_baxter
 
Регистрация: 16.11.2010
Сообщений: 6

Модифицированная задача о покрытии множества.
Добрый день,

Имеется следующая модицифированная задача о покрытии множества, в которой подмножетсва взвешенные и ориентированные. Множество, скажем

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, 18.04.2011 в 00:49.
  #2  
Старый 18.04.2011, 11:14
Пользователь

Отправить личное сообщение для maxal Посмотреть профиль Найти все сообщения от maxal
 
Регистрация: 28.11.2006
Сообщений: 68

Вариация на тему http://en.wikipedia.org/wiki/Path_cover
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Разбиение множества. ugo Математические алгоритмы 35 27.09.2010 22:17
Задача минимального покрытия множества l0ki Математические алгоритмы (другое) 0 15.09.2010 01:54
число ребер в наименьшем покрытии ребер sergey2189 Графы 4 09.10.2009 20:55
Еще одна задача на разбиение множества jungle4ever Математические алгоритмы 7 23.06.2009 17:30
задача о наименьшем покрытии Катя Реализация, исходники, языки 5 21.05.2008 14:43