Помощь - Поиск - Пользователи - Календарь
Полная версия: 500руб. за решение задачи.
Форум Игры разума [braingames] > Главный форум > Разминка для мозгов > Kоммерческие задачи
FunFox
Кину на мобилу 500 руб. Если кто-то решит задачу.

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

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

P.S. Перебор не предлагать.
P.P.S. Если не до конца понятно условие, спрашивайте.
UNDEFEAT
biggrin.gif
Переборы разные бывают.
В любом случае придётся хоть что-нибудь перебрать.
FunFox
QUOTE(UNDEFEAT @ 29.3.2012, 13:57) *

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


Если по умному то можно. Если алгоритм будет решать задачу за полиномиальное время.
nik_vic
QUOTE(FunFox @ 29.3.2012, 14:13) *

Если алгоритм будет решать задачу за полиномиальное время.
А не пытались искать аналог среди NP-полных?
Mouse
странно, но это общий вариант задачи которую вы не решили smile.gif
nik_vic
QUOTE(Mouse @ 31.3.2012, 18:35) *

странно, но это общий вариант задачи которую вы не решили smile.gif
О чём речь?
WildKOT
QUOTE(FunFox @ 29.3.2012, 13:18) *
Кину на мобилу 500 руб. Если кто-то решит задачу.

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

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

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


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

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

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

А вообще по теме Википедия в помощь - там все достаточно разумно написано. cool.gif
Mouse
QUOTE
У меня две новости: хорошая и плохая

смахивает на историю когда ученик опаздал на занятие и увидел на доске задачу.
подумал что это домашнее задание и в результате решил одну из "неразрешимых" smile.gif
Это упрощенная версия форума. Для просмотра полной версии нажмите нажмите сюда.
Invision Power Board © 2001-2019 Invision Power Services, Inc.