НГУ

Форумы НГУ
Текущее время: Вс дек 06, 2020 12:08 am

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 7 ] 
Автор Сообщение
 Заголовок сообщения: Задачка
СообщениеДобавлено: Чт фев 18, 2010 8:13 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Пт сен 02, 2005 12:59 pm
Сообщения: 1421
Откуда: Владимир
A - конечное множество элементов
Bi - подмножества A, i = 1,..,n.
Найти множество C минимального размера такое, что C в пересечении с Bi - непусто для любого i.
.
Это не задачка с семинара и, возможно, она не сильно интересная и даже простая. Возникла в процессе разбора другой задачи, и не могу быстро придумать, как ее решить.

_________________
А мы гуляли, пели, шли своей тропой. Мы открывали двери, хоть вход был запрещен. Мы шли в огонь.
Знай, паскуда, вольных, знай!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 18, 2010 8:24 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт сен 07, 2001 7:00 am
Сообщения: 2844
Откуда: Станислав Березнюк
Очевидно, что если Bi не пересекаются, то |C|=n.

Если пересекаются, то нужно по возможности брать в качестве элементов C элементы из пересечений. Так как все множества - конечные, то полный перебор позволяет решить задачу за конечное время.

_________________
Мордор жил, Мордор жив, Мордор будет жить!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 18, 2010 8:30 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Пт сен 02, 2005 12:59 pm
Сообщения: 1421
Откуда: Владимир
slb писал(а):
Если пересекаются, то нужно по возможности брать в качестве элементов C элементы из пересечений. Так как все множества - конечные, то полный перебор позволяет решить задачу за конечное время.


Нужно полиномиальное решение. Причем как можно более шустрое.
мы тут прикладными вещами занимаемся, а не теоретическими =)

_________________
А мы гуляли, пели, шли своей тропой. Мы открывали двери, хоть вход был запрещен. Мы шли в огонь.
Знай, паскуда, вольных, знай!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Задачка
СообщениеДобавлено: Чт фев 18, 2010 9:14 pm 
Не в сети
Постоянный посетитель

Зарегистрирован: Сб мар 15, 2003 1:40 am
Сообщения: 163
ConWor писал(а):
A - конечное множество элементов
Bi - подмножества A, i = 1,..,n.
Найти множество C минимального размера такое, что C в пересечении с Bi - непусто для любого i.
.
Это не задачка с семинара и, возможно, она не сильно интересная и даже простая. Возникла в процессе разбора другой задачи, и не могу быстро придумать, как ее решить.


Если матрица [tex]B[/tex] - это вектор характеристических векторов [tex]B_i[/tex]-x (их длина [tex]m=|A|[/tex]), то это сводится к задаче линейного 0-1 программирования: [tex]min( x_1+...+x_m)[/tex] при условии, что [tex]B\vec{x}>0[/tex]. Решение [tex]\vec{x}[/tex] дает характеристический вектор множества С. В общем случае эта задача NP-полная.


Последний раз редактировалось guest Чт фев 18, 2010 9:18 pm, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 18, 2010 9:17 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Фиксируем [tex]B_1[/tex] вместо [tex]A[/tex] и на таком [tex]A=B_1[/tex] решаем задачу для [tex]n := n-1[/tex].

Давайте оценим время работы алгоритма. Пусть [tex]|A| = m[/tex]. Даны [tex]n[/tex] двоичных наборов длины [tex]m[/tex], то есть входные данные имеют длину [tex]O(nm)[/tex]. При [tex]n=1[/tex] требуется время порядка [tex]m[/tex] (убедиться, что [tex]B_1[/tex] не пусто и выбрать из него элемент). При [tex]n=2[/tex] требуется время порядка [tex]2m[/tex] (выбрать за [tex]\approx m[/tex] шагов [tex]A = B_1[/tex] и потом убедится, что [tex]B_1 \cap B_2[/tex] не пусто). Для [tex]n=3[/tex] нужно около [tex]3m[/tex] шагов по той же схеме. И т. д.

Вроде полиномиальная задача получается :) Хотя, может, я жестоко заблуждаюсь. Всё-таки со сложностью никогда не работал :-?

Ой! Кажется, я страшную глупость написал :( Решаю совсем другую задачу: проверить, что пересечение всех [tex]B_i[/tex]-ых не пусто.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Задачка
СообщениеДобавлено: Чт фев 18, 2010 9:32 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
guest писал(а):
В общем случае эта задача NP-полная.


Надо переформулировать задачу как задачу распознавания. К примеру, даны [tex]B_1, \ldots, B_n[/tex] и число [tex]k[/tex]; требуется проверить, существует ли множество мощности [tex]k[/tex], имеющее непустое пересечение с каждым из [tex]B_i[/tex]-ых.

То, что задача из класса NP, видно сразу (сертификат --- конкретное [tex]k[/tex]-элементное множество). Теперь бы к этому делу полиномиально свести какую-нибудь из известных NP-полных задач. Например, задачу о проверке возможной истинности высказывания. Надо подумать... (А-а-а, из-за компа гонят!!!)

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 18, 2010 9:33 pm 
Не в сети
Начинающий автор

Зарегистрирован: Сб сен 16, 2006 11:23 am
Сообщения: 290
Рассмотрим граф с множеством вершин А и набором "гиперрёбер" [tex]B_i[/tex]. Тогда, очевидно, задача формулируется как нахождение минимального вершинного покрытия всех "гиперрёбер", что является NP-трудной задачей.
Соответственно, отсюда и совет - можно попробовать прикрутить приближённые алгоритмы от вершинных покрытий в обыкновенных графах.

_________________
No regret, no remorse, no mercy.
Я мёртв.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 10


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB