Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.snto-msu.net/showflat.php?Number=8777472&src=arc&showlite=
Дата изменения: Unknown
Дата индексирования: Wed Apr 13 13:15:25 2016
Кодировка: Windows-1251
[мм, алгоритмы] является ли NP-трудной задача... - Public forum of MSU united student networks
Root | Google | Yandex | Mail.ru | Kommersant | Afisha | LAN Support
  
General Discussion >> Study (Archive)

Страницы: 1
Striker
sir

Рег.: 16.02.2005
Сообщений: 1201
Из: ГЗ, сектор Б
Рейтинг: 219
  [мм, алгоритмы] является ли NP-трудной задача...
      21.06.2009 13:57
1

Дано конечное множество M и семейство S его подможеств (покрытие). Требуется выбрать из S максимальное (по мощности получаемого объединения) семейство непересекающихся подмножеств K. Мощность самого K значения не имеет. Мощности M и S одного порядка.

На языке графов: выделить семейство независимых вершин (не соединены ребрами) так, чтобы число ребер, инцидентных вершинам, было максимально. Заметте, что это НЕ задача о максимальном независимом множестве вершин, так как само число вершин роли не играет, максимизируется число "покрываемых" ребер.

Есть также близкая по постановке задача о выделении наименьшего подпокрытия, она NP-полна (сводится к наименьшему вершинному покрытию графа). Здесь же, во первых, не требуется, чтобы K в объединении давало M, нужно лишь, чтобы оно "накрывало" как можно больше элементов. Во-вторых, подмножества в K дизъюнктны. В третьих, число подможеств не имеет значения.

Если вопрос оказался простым, то задача может быть усложнена так: подможества из K имеют право пересекаться, но так, что каждый элемент входит не более, чем в k подможеств (на языке графов - каждое ребро инцедентно не более, чем k выбранным вершинам). Предполагается, что k много меньше мощности всего M.

Именно в такой постановке эта задача возникла на практике - составление "расписания" для параллельного обхода сайтов роботом: нельзя лезть на один сайт более чем k процессами одновременно, есть множество S групп сайтов, группу надо ставить или не ставить в очередь целиком, M - объединение всех групп. Требуется найти максимальный (по числу сайтов) набор групп K, которые можно обходить одновременно. M и S содержат порядка десятков миллионов элементов, k = 10.



я плакалъ...
Non_trivial
enthusiast

Рег.: 06.12.2006
Сообщений: 335
Из: ГЗ
Рейтинг: 101
  Re: [мм, алгоритмы] является ли NP-трудной задача... [re: Striker]
      13.07.2009 00:25
 

побробуй свести к твоей задаче задачу целочисленного (или лучше 0,1) линейного программирования

Truefet
Biathlon geek

Рег.: 22.05.2009
Сообщений: 3464
Рейтинг: 3724
  Re: [мм, алгоритмы] является ли NP-трудной задача... [re: Non_trivial]
      13.07.2009 02:30
-1

лично моя небогатая практика показывает, что сводить к ЛП не всегда целесообразно, я сначала пробую придумать какие-нибудь банальные контр-примеры, потом проверять на эквивалентность общеизвестным алгоритмам... \но думаю автор это уже делал\

вообще у меня встречный вопрос:

неевклидово пространство!
у онлайнового алгоритма мера каждого сервера 2, у оффлайнового 1, запросы появляются в рандомных местах и последовательно, существует ли онлайновый алгоритм, решающий задачу с оцениваемой ошибкой? (ну или хотя бы NP проверку, также)

Страницы: 1

General Discussion >> Study (Archive)

Дополнительная информация
1 зарегистрированных и 0 анонимных пользователей просматривают этот форум.

Модераторы:  Basilio, The_Nameless_One 

Печать темы

Права
      Вы можете создавать новые темы
      Вы можете отвечать на сообщения
      HTML отключен
      UBBCode включен

Рейтинг:
Просмотров темы:

Переход в