Задачка по Computer Science

Ktitiss

Кто в алгоритмах рюхает, помогите решить задачку, плиз:
Задано дерево с $N$ вершинами, каждой из которых приписан вес --- неотрицательное
целое число. Требуется удалить из него наименьшее по весу подмножество вершин, так чтобы
после этого оно распалось на $K$ или более компонент связности. Сложность $O(K^2 N)$.

Ktitiss

up
еще не решил. :-)

alexei-andreev

Первое пришедшее в голову решение (и видимо подразумевающееся в условии) :
1) Посчитаем для каждой вершины полезность = вес/(степень вершины - 1) и выкинем вершины с минимальной полезностью (у вершин степени 1 - полезность равна бесконечности)
2) чтобы сумма (степенй вершин -1) из этого набора была >= K
Алгоритм:
обход всех вершин дерева (сложность N ) с формированием массива из K-1 наимение полезных вершин (на это уйдет O(K^2
После этого набираем необходимое число вершин из полученного массива для выполнения условия 2
Итоговая сложность : O(NxK^2)
Причем тут
Computer Science
? на мой взгляд - дискра обыкновенная

Ktitiss

Спасибо, за ответ.
К сожалению K-1 самых «бесполезных» в твоей терминологии вершин это не всегда то, что нам нужно. Например такой граф: Вершины a,b и c имеют веса 1, 2 и 5. А их (степени-1) соответственно равны 1, 4, 15. Остальные вершины имеют степень 1. При K=5 нам надо было бы выбросить a и b c суммарным весом 3, а твой алгоритм выкинет самую «бесполезную» вершину то есть c, вес которой равен 5-и.

Ktitiss

на мой взгляд - дискра обыкновенная

По моему дискра это наука о бинарных функциях, КНФ, предполных классах и т.п. А построение и анализ алгоритмов это все таки computer science.

Ktitiss

Все, я решил!
Каждый кто знал, что такое динамическое программирование, думал больше одной минуты и не решил -- лох!
А кто не думал -- мудак.
Надеюсь, теперь меня не отчислят....

Custodian

А ты к какой категории относишься?
Я знаю что такое ДП, идея решения есть (отсекаем одну компоненту, а далее рекурсия или можно то же самое сделать прямым вычислением но есть проблемы с реализацией. Интересно узнать твое решение.

Ktitiss

К первой. Но осознание того, что ты лох это первый шаг к тому, чтобы перестать им быть. :-)
Решение такое:
У нас есть массив вершин от 1 до N, про каждую мы знаем вес – w(i) и число ветвей (степень-1) -- c(i). Давай найдем минимальный суммарный вес вершин, суммарное число ветвей у которых больше k, если разрешить выбрасывать вершины 1..i. Обозначим эту величину val[k, i].
Предположим, что мы уже нашли все значения val[1..k,1..i-1]. Рассматриваем вершину i:
1) Если мы ее выкинем, то нам останется выкинуть еще k-c(i) веток. Но мы уже знаем решение этой задачи: val[k-c(i i-1].
2) Если мы ее оставим, то вес выкинутых вершин останется прежним: val[k,i-1]
Положим val[k,i] минимальному из этих значений: min(val[k-c(i i-1]+w(i val[k,i-1])
Перебрав все значения k от 1 до K и для каждой перебрав i от 1 до N мы получим искомое val[K,N]

alexanderm

Все правильно - только сложность такого алгоритма O(N*(N-1)*(N-2)*...*(N-K+1 - а это не совсем то что тербовалось в задаче
Сложность вычисляется так: S(N,K) = N*S(N-1,K-1) (это для наихудшего случая - когда все вершины степени 2 (кроме крайних
Чтобы получить требуемую сложность надо довести до конца первый предложенный алгоритм - это я думаю тебе вполне по силам

Ktitiss

For k=1 to K do
| For i=1 to N do
| | val[k,i] =min(val[k-c(i i-1]+w(ival[k,i-1])
| Next
Next
Какая-какая сложность у этого алгоритма?

alexei-andreev

For k=1 to K do
| For i=1 to N do
| | val[k,i] =min(val[k-c(i i-1]+w(ival[k,i-1])
| Next
Next

Второй For если следовать описанному тобой алгоритму должен пробегать все N-k элементные подмножества {1,.....N}, а иначе приведенная реализация неверна - сам придумаешь контрпример или подсказать ? (отчислят ведь )

Ktitiss

Ну подскажи.... А то я пока тебя не очень понимаю.
Кстати меня так и так отчислят. У меня кроме этой задачи еще две не решаются.

alexei-andreev

Если 2 другие такие же как эта то за час решим
контрпример:
---1---100---100---100---
N=6
K=4
посчитай val[*,*] по своему алгоритму (подсказка - у тебя получится val[6,4]=3 - а теперь скажи где тут 3 вершины с весом 1? )
(значения в концевых вершинах не важны - т к их выкидывание не увеличивает числа компонент связности )

Ktitiss

Да нет, все нормально 301 получается....
Вот собственно массив val[k,i]:
Null 001 001 001 001 001
Null Null 101 101 101 101
Null Null Null 201 201 201
Null Null Null Null 301 301
(по вертикали вниз идет k, по горизонтали слева на право i)

alexei-andreev


For k=1 to K do
| For i=1 to N do
| | val[k,i] =min(val[k-c(i i-1]+w(ival[k,i-1])
| Next
Next

Да нет, все нормально 301 получается....
Вот собственно массив val[k,i]:
Null 001 001 001 001 001
Null Null 101 101 101 101
Null Null Null 201 201 201
Null Null Null Null 301 301
(по вертикали вниз идет k, по горизонтали слева на право i)

Я могу показать что ты не прав - проделав по шагам этот цикл - но мне лень - если не понимаешь что ты не прав - аккуратно напиши все на бумашке (или прогу - раз это типа Computer Science ) - если не помогает - значит правильно отчислят

alexei-andreev

если это программа выдает то поставь вершину с 1 посередине:
---100---1---100---100---
тогда точно неправильный результат получится
удачи

Ktitiss

Похоже кто-то из нас тупит и не хочет этого признавать. Дело осложняется тем, что мы оба кидаем пальцы...
Вообщем я там в соседнем треде запостил другую задачку. Если ты ее правда в течении часа решишь, я тебе законный приз занесу и заодно выясним кто из нас тут не прав. :-)

Ktitiss

А! Тебя видимо смущает, что не понятно как обрабатывать Null'ы (ситуации когда для данных k и i нет решения)?
Поясню:
Min(Null,число) = число всегда.
Null + w(i) = Null в случае если с(i)<k
Null + w(i) = w(i) в случае если с(i)>=k
С этими допущениями второй пример легко прокатывает.

Custodian

По ходу val[*, *] ты считаешь правильно, но как оно связано с ответом задачи? Удаляя вершину в дереве степени $p$ ты получаешь $p$ компонент связности, но при этом у некоторых вершин меняется степень. Т.е. при их удалении образуется уже меньшее кол-во компонент . Ты никак не учитываешь, что c(i) меняется. Если я не глючу, завтра утром построю контр пример.

Ktitiss

Custodian

Не догнал, ты со мной согласен? Тебе еще решение к задаче нужно? Если да, я завтра подумаю и ко второй тоже.

Ktitiss

Нет. Это я испугался, что ты прав. Но потом мы обсудили это с анонимусом_120 () и решили, что никакой проблемы тут нет. Просто надо предполагать, что когда мы выкидываем вершину, мы выкидываем ее не вместе с ребрами, а как бы делим. То есть чтобы выкинуть вершину A степени 3, мы вместо нее создаем 3 висячие вершины A1, A2, A3 и «затыкаем» ими ребра которые шли в A. В таком понимании выкидывания все реаботает. :-)
Если подумаешь над второй задачкой, буду очень благодарен. :-)

Custodian

Представь, что у тебя есть "цепочка" 1-2-3-4-5. И вот тебе две ситуации:
1) удаляешь 2 и 4
2) удаляешь 2 и 3
Ты эти случаи не различаешь в обоих у тебя получается по 4 компоненты (ты считаешь сумму степеней вершин). Т.е. смущает три вещи:
1) твое понимание задачи. Во втором случае приходится считать, что есть компонента 2-3, состоящая из удаленных вершин. Но если например из исходной цепочки удалить одну вершину, то компоненты из "удаленных" вершин не возникает. Т.е. в одном случае ты считаешь такие компоненты в другом нет
2) Ты считаешь, что при удалении вершины степени $p$ образуется $p$ компонент. Здесь есть ошибка: ты забываешь про то, что изначально уже существует одна компонента, а при удалении образуется $p-1$ новая! Контр пример построить не сложно (см. выше). Это поправить в программе так же не сложно.
3) Сложность твоего алгоритма O(NK)

Ktitiss

Спасибо, за комментарии, .
1) В обоих случаях мое понимание задачи одно и тоже: в первом случае получаем компоненты: 1-2 2-3-4 4-5, а во втором: 1-2 2-3 3-4-5. Если понимать задачу по другому, она по-моему о-очень сильно усложняется.
2)Верно. Исправлю.
3)Ну это типа круто. :-)

batonov

Только вот удаление вершин обычно понимается как раз "по-другому".

batonov

И ещё такое соображение - чтобы определить сколько рёбер выходит из каждой вершины, я думаю, нужно время порядка O(N^2 а это как-то расходится с условием O(K^2 N).

Custodian

Ты гонишь, это же не произвольный граф, а дерево. Просто пробегаешь по всем ребрам $(v, w)\in E$ и увеличиваешь c(v)++, c(w)++. Все получается За линейное время.

Custodian

Я поговорил со своим знакомым и случайно обнаружил, что он автор этих задач. Он очень сильно огорчен . Я со своей стороны всякую помощь в решении задач прекращаю

batonov

Да, согласен, сразу не подумал об этом. Но там ведь не для одного конкретного дерева надо будет вычислять, если делать это "в лоб"... Там что-то попроще должно быть.

kravecnata

> Я поговорил со своим знакомым и случайно обнаружил ...
Неужели тебе это не приходило в голову раньше? Число людей неподалёку, способных давать такие задачи, невелико, и вероятность, что это твой знакомый, априори довольно значительна.

Custodian

Маза не решение задачи написать в форуме, а попробовать самому решить . На удивление задачи оказались достаточно тяжелые, и поэтому я решил обратиться за помощью.

Ktitiss

Для всех кто не в теме (не является членом или тренером сборной мехмата по программированию, не водит дружбы с , , Максом Бабенко, Андреем Румянцевым, сотрудниками кафедры логики и т.п.) и у кого нет каких-либо других причин мне не помогать, сообщаю:
От очень огорченного автора задач поступила информация, что мое понимание «выкидывания вершин» -- не правильное. Так что задача остается открытой.
Оставить комментарий
Имя или ник:
Комментарий: