IPB

Добро пожаловать, гость ( Вход | Регистрация )

> Правила

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

Исполнителям: Вы можете отвечать на поставленную задачу, задавать дополнительные вопросы и т.д. Первый ответивший правильно получает 90% суммы. 10% идет на развитие сайта. Если правильное решение найдено сообща, доли иазначаются модераторами раздела.

 
Ответить в эту темуОткрыть новую тему
> 500руб. за решение задачи., Вроде бы задача не сложная, но у меня от нее цейтнот.
FunFox
29.3.2012, 12:18
Сообщение #1


Новичок
*

Группа: Пользователи Braingames
Сообщений: 4
Регистрация: 13.5.2009
Пользователь №: 14 288



Кину на мобилу 500 руб. Если кто-то решит задачу.

Дано.
Произвольный граф(НЕориентированый).
Из графа вытаскивают вершину и кладут ее в ящик.
После этого соседние с этой вершиной вершины блокируются(их вытаскивать больше нельзя).
Далее снова вытаскивается вершина, и соседние с ней тоже блокируются.
Так пока не останется доступных вершин.
Для произвольного графа нужно разработать алгоритм(порядок) вытаскивания вершин, такой, чтобы количество вершин в ящике оказалось максимальной.

Очень нужно эту задачу решить, а 500руб. как небольшая мотивация.

P.S. Перебор не предлагать.
P.P.S. Если не до конца понятно условие, спрашивайте.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
UNDEFEAT
29.3.2012, 12:57
Сообщение #2


Avorthoren
****

Группа: Модераторы BrainGames
Сообщений: 3 369
Регистрация: 13.11.2010
Из: Kиев
Пользователь №: 21 696



biggrin.gif
Переборы разные бывают.
В любом случае придётся хоть что-нибудь перебрать.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
FunFox
29.3.2012, 13:13
Сообщение #3


Новичок
*

Группа: Пользователи Braingames
Сообщений: 4
Регистрация: 13.5.2009
Пользователь №: 14 288



QUOTE(UNDEFEAT @ 29.3.2012, 13:57) *

biggrin.gif
Переборы разные бывают.
В любом случае придётся хоть что-нибудь перебрать.


Если по умному то можно. Если алгоритм будет решать задачу за полиномиальное время.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
nik_vic
29.3.2012, 14:34
Сообщение #4


Активный участник
***

Группа: Пользователи Braingames
Сообщений: 753
Регистрация: 22.1.2008
Пользователь №: 6 125



QUOTE(FunFox @ 29.3.2012, 14:13) *

Если алгоритм будет решать задачу за полиномиальное время.
А не пытались искать аналог среди NP-полных?


--------------------
Где это видано?
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Mouse
31.3.2012, 17:35
Сообщение #5


и.о. админа
**

Группа: Администраторы
Сообщений: 86
Регистрация: 5.12.2006
Пользователь №: 20



странно, но это общий вариант задачи которую вы не решили smile.gif
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
nik_vic
1.4.2012, 11:18
Сообщение #6


Активный участник
***

Группа: Пользователи Braingames
Сообщений: 753
Регистрация: 22.1.2008
Пользователь №: 6 125



QUOTE(Mouse @ 31.3.2012, 18:35) *

странно, но это общий вариант задачи которую вы не решили smile.gif
О чём речь?


--------------------
Где это видано?
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
WildKOT
4.4.2013, 18:29
Сообщение #7


Новичок
*

Группа: Пользователи Braingames
Сообщений: 25
Регистрация: 6.4.2008
Пользователь №: 7 361



QUOTE(FunFox @ 29.3.2012, 13:18) *
Кину на мобилу 500 руб. Если кто-то решит задачу.

Дано.
Произвольный граф(НЕориентированый).
Из графа вытаскивают вершину и кладут ее в ящик.
После этого соседние с этой вершиной вершины блокируются(их вытаскивать больше нельзя).
Далее снова вытаскивается вершина, и соседние с ней тоже блокируются.
Так пока не останется доступных вершин.
Для произвольного графа нужно разработать алгоритм(порядок) вытаскивания вершин, такой, чтобы количество вершин в ящике оказалось максимальной.

Очень нужно эту задачу решить, а 500руб. как небольшая мотивация.

P.S. Перебор не предлагать.
P.P.S. Если не до конца понятно условие, спрашивайте.


1. Из графа удаляем рёбра соединиющие вершина саму с собой, они будут мешать алгоритму.
2. Для каждой вершины считаем число незаблокированных рёбер
Логично предположить, что следует выбирать вершины, которые имеют минимальное число рёбер, чтобы сумма степеней выбранных вершин была минимальна.
3. Для вершин степени 0 очевидно, что их надо выбрать в первую очередь.
4. Выбор вершины А степени 1 помешает выбору другой вершины Б, но если выбрать Б, то в лучшем случае только А будет заблокирована. Поэтому всегда можно выбирать вершину степени 1.
(при выборе вершины все заблокированные вершины вместе с рёбрами исходящими из них выключаются из рассмотрения)
5. Каждый следующий шаг вытаскиваем вершину с минимальной степенью.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
0
5.4.2013, 2:45
Сообщение #8


Охгдеж
****

Группа: Пользователи Braingames
Сообщений: 1 323
Регистрация: 26.3.2009
Пользователь №: 13 618



QUOTE(WildKOT @ 4.4.2013, 19:29) *
1. Из графа удаляем рёбра соединиющие вершина саму с собой, они будут мешать алгоритму.
2. Для каждой вершины считаем число незаблокированных рёбер
Логично предположить, что следует выбирать вершины, которые имеют минимальное число рёбер, чтобы сумма степеней выбранных вершин была минимальна.
3. Для вершин степени 0 очевидно, что их надо выбрать в первую очередь.
4. Выбор вершины А степени 1 помешает выбору другой вершины Б, но если выбрать Б, то в лучшем случае только А будет заблокирована. Поэтому всегда можно выбирать вершину степени 1.
(при выборе вершины все заблокированные вершины вместе с рёбрами исходящими из них выключаются из рассмотрения)
5. Каждый следующий шаг вытаскиваем вершину с минимальной степенью.

Это неверно.
Для контрпримера можно взять граф из 7 вершин A,B1,B2,B3,C1,C2,C3.
Ребра: (A,Bi) для всех i, (Bi,Cj) для все i и j, (Ci,Cj) для всех i!=j.
Вершина A имеет степень 3, вершины Bi имеют степень 4, вершины Сi имеют степень 5.
Но взяв вершину с минимальной степенью A мы исключим вершины Bi и останется полный граф из которого можно взять только 1 вершину. Итого сможем набрать только 2 вершины.
А взяв сначала вершину B1 мы сможем взять B2 а затем и B3 набрав в итоге 3 вершины.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
FunFox
6.4.2013, 13:08
Сообщение #9


Новичок
*

Группа: Пользователи Braingames
Сообщений: 4
Регистрация: 13.5.2009
Пользователь №: 14 288



QUOTE(WildKOT @ 4.4.2013, 19:29) *
1. Из графа удаляем рёбра соединиющие вершина саму с собой, они будут мешать алгоритму.
2. Для каждой вершины считаем число незаблокированных рёбер
Логично предположить, что следует выбирать вершины, которые имеют минимальное число рёбер, чтобы сумма степеней выбранных вершин была минимальна.
3. Для вершин степени 0 очевидно, что их надо выбрать в первую очередь.
4. Выбор вершины А степени 1 помешает выбору другой вершины Б, но если выбрать Б, то в лучшем случае только А будет заблокирована. Поэтому всегда можно выбирать вершину степени 1.
(при выборе вершины все заблокированные вершины вместе с рёбрами исходящими из них выключаются из рассмотрения)
5. Каждый следующий шаг вытаскиваем вершину с минимальной степенью.

Ахах, все не на столько просто!
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
John777
8.4.2013, 18:57
Сообщение #10


Kорифей
****

Группа: Пользователи Braingames
Сообщений: 1 669
Регистрация: 13.11.2008
Из: Москва
Пользователь №: 10 702



У меня две новости: хорошая и плохая tongue.gif
Хорошая в том, что тот, кто решит эту задачу или хотя бы найдет приближенное решение за полиномиальное время, получит не только 500 рублей на мобильник, но и Филдсовскую премию впридачу за доказательство P=NP.

Короче, это называется Задача о независимом множестве (maximum independent set), и она NP-трудная. Соответственно, любое ее решение для графа общего вида будет перебором с некоторыми эвристиками. Правда, если у вас граф какого-то определенного вида (например, дерево или двудольный граф), то задача решается за полиномиальное время.

А вообще по теме Википедия в помощь - там все достаточно разумно написано. cool.gif


--------------------
Изображение
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Mouse
9.4.2013, 11:13
Сообщение #11


и.о. админа
**

Группа: Администраторы
Сообщений: 86
Регистрация: 5.12.2006
Пользователь №: 20



QUOTE
У меня две новости: хорошая и плохая

смахивает на историю когда ученик опаздал на занятие и увидел на доске задачу.
подумал что это домашнее задание и в результате решил одну из "неразрешимых" smile.gif
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения

Ответить в эту темуОткрыть новую тему
2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0 -

 



- Упрощённая версия Сейчас: 24.7.2019, 2:23