500руб. за решение задачи., Вроде бы задача не сложная, но у меня от нее цейтнот. |
Добро пожаловать, гость ( Вход | Регистрация )
Заказчикам:
Создайте тему с задачей. В теме напишите название и цену которую вы готовы заплатить за ее решение (минимальная сумма 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 847 Регистрация: 13.11.2010 Из: Kиев Пользователь №: 21 696 |
Переборы разные бывают. В любом случае придётся хоть что-нибудь перебрать. |
FunFox |
29.3.2012, 13:13
Сообщение
#3
|
Новичок Группа: Пользователи Braingames Сообщений: 4 Регистрация: 13.5.2009 Пользователь №: 14 288 |
|
nik_vic |
29.3.2012, 14:34
Сообщение
#4
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
Если алгоритм будет решать задачу за полиномиальное время. -------------------- Где это видано?
|
Mouse |
31.3.2012, 17:35
Сообщение
#5
|
и.о. админа Группа: Администраторы Сообщений: 86 Регистрация: 5.12.2006 Пользователь №: 20 |
странно, но это общий вариант задачи которую вы не решили
|
nik_vic |
1.4.2012, 11:18
Сообщение
#6
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
странно, но это общий вариант задачи которую вы не решили -------------------- Где это видано?
|
WildKOT |
4.4.2013, 18:29
Сообщение
#7
|
Новичок Группа: Пользователи Braingames Сообщений: 30 Регистрация: 6.4.2008 Пользователь №: 7 361 |
Кину на мобилу 500 руб. Если кто-то решит задачу. Дано. Произвольный граф(НЕориентированый). Из графа вытаскивают вершину и кладут ее в ящик. После этого соседние с этой вершиной вершины блокируются(их вытаскивать больше нельзя). Далее снова вытаскивается вершина, и соседние с ней тоже блокируются. Так пока не останется доступных вершин. Для произвольного графа нужно разработать алгоритм(порядок) вытаскивания вершин, такой, чтобы количество вершин в ящике оказалось максимальной. Очень нужно эту задачу решить, а 500руб. как небольшая мотивация. P.S. Перебор не предлагать. P.P.S. Если не до конца понятно условие, спрашивайте. 1. Из графа удаляем рёбра соединиющие вершина саму с собой, они будут мешать алгоритму. 2. Для каждой вершины считаем число незаблокированных рёбер Логично предположить, что следует выбирать вершины, которые имеют минимальное число рёбер, чтобы сумма степеней выбранных вершин была минимальна. 3. Для вершин степени 0 очевидно, что их надо выбрать в первую очередь. 4. Выбор вершины А степени 1 помешает выбору другой вершины Б, но если выбрать Б, то в лучшем случае только А будет заблокирована. Поэтому всегда можно выбирать вершину степени 1. (при выборе вершины все заблокированные вершины вместе с рёбрами исходящими из них выключаются из рассмотрения) 5. Каждый следующий шаг вытаскиваем вершину с минимальной степенью. |
0 |
5.4.2013, 2:45
Сообщение
#8
|
Охгдеж Группа: Пользователи Braingames Сообщений: 1 335 Регистрация: 26.3.2009 Пользователь №: 13 618 |
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 |
1. Из графа удаляем рёбра соединиющие вершина саму с собой, они будут мешать алгоритму. 2. Для каждой вершины считаем число незаблокированных рёбер Логично предположить, что следует выбирать вершины, которые имеют минимальное число рёбер, чтобы сумма степеней выбранных вершин была минимальна. 3. Для вершин степени 0 очевидно, что их надо выбрать в первую очередь. 4. Выбор вершины А степени 1 помешает выбору другой вершины Б, но если выбрать Б, то в лучшем случае только А будет заблокирована. Поэтому всегда можно выбирать вершину степени 1. (при выборе вершины все заблокированные вершины вместе с рёбрами исходящими из них выключаются из рассмотрения) 5. Каждый следующий шаг вытаскиваем вершину с минимальной степенью. Ахах, все не на столько просто! |
John777 |
8.4.2013, 18:57
Сообщение
#10
|
Kорифей Группа: Пользователи Braingames Сообщений: 1 672 Регистрация: 13.11.2008 Из: Москва Пользователь №: 10 702 |
У меня две новости: хорошая и плохая
Хорошая в том, что тот, кто решит эту задачу или хотя бы найдет приближенное решение за полиномиальное время, получит не только 500 рублей на мобильник, но и Филдсовскую премию впридачу за доказательство P=NP. Короче, это называется Задача о независимом множестве (maximum independent set), и она NP-трудная. Соответственно, любое ее решение для графа общего вида будет перебором с некоторыми эвристиками. Правда, если у вас граф какого-то определенного вида (например, дерево или двудольный граф), то задача решается за полиномиальное время. А вообще по теме Википедия в помощь - там все достаточно разумно написано. -------------------- |
Mouse |
9.4.2013, 11:13
Сообщение
#11
|
и.о. админа Группа: Администраторы Сообщений: 86 Регистрация: 5.12.2006 Пользователь №: 20 |
QUOTE У меня две новости: хорошая и плохая смахивает на историю когда ученик опаздал на занятие и увидел на доске задачу. подумал что это домашнее задание и в результате решил одну из "неразрешимых" |
Упрощённая версия | Сейчас: 28.5.2024, 16:29 |