Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум Игры разума [braingames] _ Kоммерческие задачи _ 500руб. за решение задачи.
Автор: FunFox 29.3.2012, 12:18
Кину на мобилу 500 руб. Если кто-то решит задачу.
Дано.
Произвольный граф(НЕориентированый).
Из графа вытаскивают вершину и кладут ее в ящик.
После этого соседние с этой вершиной вершины блокируются(их вытаскивать больше нельзя).
Далее снова вытаскивается вершина, и соседние с ней тоже блокируются.
Так пока не останется доступных вершин.
Для произвольного графа нужно разработать алгоритм(порядок) вытаскивания вершин, такой, чтобы количество вершин в ящике оказалось максимальной.
Очень нужно эту задачу решить, а 500руб. как небольшая мотивация.
P.S. Перебор не предлагать.
P.P.S. Если не до конца понятно условие, спрашивайте.
Автор: UNDEFEAT 29.3.2012, 12:57
Переборы разные бывают.
В любом случае придётся хоть что-нибудь перебрать.
Автор: FunFox 29.3.2012, 13:13
Переборы разные бывают.
В любом случае придётся хоть что-нибудь перебрать.
Если по умному то можно. Если алгоритм будет решать задачу за полиномиальное время.
Автор: nik_vic 29.3.2012, 14:34
Если алгоритм будет решать задачу за полиномиальное время.
Автор: Mouse 31.3.2012, 17:35
странно, но это общий вариант задачи которую вы не решили 
Автор: nik_vic 1.4.2012, 11:18
странно, но это общий вариант задачи которую вы не решили
Автор: WildKOT 4.4.2013, 18:29
Дано.
Произвольный граф(НЕориентированый).
Из графа вытаскивают вершину и кладут ее в ящик.
После этого соседние с этой вершиной вершины блокируются(их вытаскивать больше нельзя).
Далее снова вытаскивается вершина, и соседние с ней тоже блокируются.
Так пока не останется доступных вершин.
Для произвольного графа нужно разработать алгоритм(порядок) вытаскивания вершин, такой, чтобы количество вершин в ящике оказалось максимальной.
Очень нужно эту задачу решить, а 500руб. как небольшая мотивация.
P.S. Перебор не предлагать.
P.P.S. Если не до конца понятно условие, спрашивайте.
1. Из графа удаляем рёбра соединиющие вершина саму с собой, они будут мешать алгоритму.
2. Для каждой вершины считаем число незаблокированных рёбер
Логично предположить, что следует выбирать вершины, которые имеют минимальное число рёбер, чтобы сумма степеней выбранных вершин была минимальна.
3. Для вершин степени 0 очевидно, что их надо выбрать в первую очередь.
4. Выбор вершины А степени 1 помешает выбору другой вершины Б, но если выбрать Б, то в лучшем случае только А будет заблокирована. Поэтому всегда можно выбирать вершину степени 1.
(при выборе вершины все заблокированные вершины вместе с рёбрами исходящими из них выключаются из рассмотрения)
5. Каждый следующий шаг вытаскиваем вершину с минимальной степенью.
Автор: 0 5.4.2013, 2:45
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
2. Для каждой вершины считаем число незаблокированных рёбер
Логично предположить, что следует выбирать вершины, которые имеют минимальное число рёбер, чтобы сумма степеней выбранных вершин была минимальна.
3. Для вершин степени 0 очевидно, что их надо выбрать в первую очередь.
4. Выбор вершины А степени 1 помешает выбору другой вершины Б, но если выбрать Б, то в лучшем случае только А будет заблокирована. Поэтому всегда можно выбирать вершину степени 1.
(при выборе вершины все заблокированные вершины вместе с рёбрами исходящими из них выключаются из рассмотрения)
5. Каждый следующий шаг вытаскиваем вершину с минимальной степенью.
Ахах, все не на столько просто!
Автор: John777 8.4.2013, 18:57
У меня две новости: хорошая и плохая 
Хорошая в том, что тот, кто решит эту задачу или хотя бы найдет приближенное решение за полиномиальное время, получит не только 500 рублей на мобильник, но и Филдсовскую премию впридачу за доказательство P=NP.
Короче, это называется Задача о независимом множестве (maximum independent set), и она NP-трудная. Соответственно, любое ее решение для графа общего вида будет перебором с некоторыми эвристиками. Правда, если у вас граф какого-то определенного вида (например, дерево или двудольный граф), то задача решается за полиномиальное время.
А вообще по теме Википедия в помощь - там все достаточно разумно написано. 
Автор: Mouse 9.4.2013, 11:13
смахивает на историю когда ученик опаздал на занятие и увидел на доске задачу.
подумал что это домашнее задание и в результате решил одну из "неразрешимых"