Задачка

=DeaD=

Пытаюсь понять, как обобщить Прима-Краскала на ориентированные графы и не получается с ходу

и главное в инете на эту тему тишина

blindman

http://en.wikipedia.org/wiki/Chu%E2%80% ... _algorithm - это?

Добавлено спустя 1 минуту 28 секунд:
http://en.wikipedia.org/wiki/Minimum_sp ... d_problems

=DeaD=

Короче надо из орграфа выкинуть часть ребер, чтобы он остался сильно связанным, а сумма оставшихся ребер была минимальной

Ну вот, я же говорил, что очень уж от задачки NP-полнотой попахивает:
http://www.sciencedirect.com/science?_o ... b16af6c306

Цитата:

A linear time 5/3-approximation algorithm is presented for the NP-hard problem of finding a minimum strongly-connected spanning subgraph.

minimum strongly-connected spanning subgraph - это как раз аналог минимального остова для орграфа в смысле сильной связности.

Добавлено спустя 4 минуты 22 секунды:

blindman писал(а):

http://en.wikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm - это?

Ща пойму, что это они тут ищут, но вроде не то что нам надо.

blindman писал(а):

http://en.wikipedia.org/wiki/Minimum_spanning_tree#Related_problems

А вот это вообще про обычные (не ориентированные графы).

Добавлено спустя 1 минуту 51 секунду:
Понял, "The Directed Minimum Spanning Tree Problem" - это такой субграф орграфа, что он является покрывающим граф деревом в смысле направленности ребер, т.е. в нём из корня можно попасть во все листья, но не наоборот.

Добавлено спустя 31 секунду:
В общем твоя задачка NP-полна похоже :pardon:

blindman

Цитата:

Ща пойму, что это они тут ищут, но вроде не то что нам надо.

Похоже, не то

Цитата:

To find a maximum path length, the largest edge value is found and connected between the two nodes, then the next largest value, and so on. If an edge creates a loop, it is erased.

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

=DeaD=

Вот еще указание, что это NP-полная задачка:
http://citeseerx.ist.psu.edu/viewdoc/su ... 1.1.26.719

Цитата:

We consider the problem (MSSS) of finding a strongly connected spanning subgraph with the minimum number of arcs in a strongly connected digraph. This problem is NP-hard for general digraphs since it generalizes the hamiltonian cycle problem.

=DeaD=

Ну как, принимаешь ответ "нет ответа" ? :wink:

blindman

Нет. Решение оценивает робот, который слова "нет" не знает

=DeaD=

Ты в автоматизированную систему типа acm.uva.es online judge задачки сдаёшь что ли?

Добавлено спустя 8 минут 49 секунд:
Ну и даже если так - ты сейчас ждешь существенно более эффективных алгоритмов, чем n! ?
Например n^2*2^n пойдёт?

Ты ведь не надеешься, что кто-то решит тут NP-полную задачу за полиномиальное время и докажет мимоходом эквивалентность NP и P классов задач?

Michael_K

"Угадать" тестовые данные можно?

Число попыток ответа у вас какое? :oops:

Добавлено спустя 35 минут 38 секунд:
Вообще в таком случае нужно бы указать порядок n

blindman

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

Добавлено спустя 2 минуты:
Число попыток неограничено, но задержка между отправкой решения и ответом бота составляет часы. Вариантов ответа 2 - проошел/не прошел

Добавлено спустя 1 минуту 25 секунд:
Предположить порядок графа я могу. С вероятностью 50% он не превышает 1000

=DeaD=

Ну ты темнишь

давай тогда хотя-бы - какие ограничения по времени и по памяти для решений?

Очень похоже на какие-то специфичные соревнования под флагом какого-нибудь гугла

для приёма на работу - типа сдал, - приходи пообщаться

С вероятностью 50% не превышает 1000 это откуда взято? Скинь хоть в личку что ли, что это вообще, а то будет как со связностью

Michael_K

Цитата:

С вероятностью 50% он не превышает 1000

Гыгык... "ищем современных Эйлеров"...
Участвовал как-то в таких...
Только задача была на скорость... (типа, кто быстрее определит простоту чисел - что-то такое)
В конце концов оказалось, что все победители опустились до асма.
То есть не только алгоритмом взяли, но и знанием архитектуры тестирующей системы.

Добавлено спустя 1 минуту:

Цитата:

под флагом какого-нибудь гугла

для приёма на работу

Тоже так подумал...

blindman

Условия полностью сформулированы здесь: viewtopic.php?f=17&t=7292&start=45#p141154 (за исключением форматов ввода/вывода - считаю несущественным)
Ограничения по времени - "your program must be fast, and give a correct answer within a matter of minutes"

Больше добавить нечего.

Цитата:

С вероятностью 50% не превышает 1000 это откуда взято?

Оттуда, что ничего про это неизвестно

Типа шутка юмора

=DeaD=

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

Добавлено спустя 57 секунд:
Думаю ни о каких n=1000 не должно быть речи. Кроме случаев когда выкинуть надо совсем мало ребер.

Michael_K

Цитата:

Условия полностью сформулированы здесь: viewtopic.php?f=17&t=7292&start=45#p141154

Это задача, которую вы ставите перед тестирующей системой,
А тестирующая система ставит перед вами совсем другую задачу :wink:

(например "взломать ее и выковырять файл с правильным ответом"

)

Вероятно, тут нужно идти от обратного - выкидывать заведомо ненужные ветви,
прореживая граф. А остальное перебором довести. Типа "ветвей-границ"

Порядок 1000 тоже считаю нереальным.

roboforum.ru

Задачка

Кто сейчас на конференции