и главное в инете на эту тему тишина roboforum.ru
Технический форум по робототехнике.
Задачка
Re: Задачка
Пытаюсь понять, как обобщить Прима-Краскала на ориентированные графы и не получается с ходу и главное в инете на эту тему тишина
и главное в инете на эту тему тишина Re: Задачка
- это?
Добавлено спустя 1 минуту 28 секунд:
Добавлено спустя 1 минуту 28 секунд:
Re: Задачка
Короче надо из орграфа выкинуть часть ребер, чтобы он остался сильно связанным, а сумма оставшихся ребер была минимальной
Ну вот, я же говорил, что очень уж от задачки NP-полнотой попахивает:
minimum strongly-connected spanning subgraph - это как раз аналог минимального остова для орграфа в смысле сильной связности.
Добавлено спустя 4 минуты 22 секунды:
Ща пойму, что это они тут ищут, но вроде не то что нам надо.
А вот это вообще про обычные (не ориентированные графы).
Добавлено спустя 1 минуту 51 секунду:
Понял, "The Directed Minimum Spanning Tree Problem" - это такой субграф орграфа, что он является покрывающим граф деревом в смысле направленности ребер, т.е. в нём из корня можно попасть во все листья, но не наоборот.
Добавлено спустя 31 секунду:
В общем твоя задачка NP-полна похоже
Ну вот, я же говорил, что очень уж от задачки NP-полнотой попахивает:
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-полна похоже
Re: Задачка
Ща пойму, что это они тут ищут, но вроде не то что нам надо.
Похоже, не то
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.
Я так понимаю, что если добавление ребра создает замкнутый путь, то это ребро удаляется. А тут без замкнутого пути, как минимум одного, никак
Re: Задачка
Вот еще указание, что это NP-полная задачка:
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.
Re: Задачка
Ну как, принимаешь ответ "нет ответа" ? 
Re: Задачка
Нет. Решение оценивает робот, который слова "нет" не знает
Re: Задачка
Ты в автоматизированную систему типа acm.uva.es online judge задачки сдаёшь что ли?
Добавлено спустя 8 минут 49 секунд:
Ну и даже если так - ты сейчас ждешь существенно более эффективных алгоритмов, чем n! ?
Например n^2*2^n пойдёт?
Ты ведь не надеешься, что кто-то решит тут NP-полную задачу за полиномиальное время и докажет мимоходом эквивалентность NP и P классов задач?
Добавлено спустя 8 минут 49 секунд:
Ну и даже если так - ты сейчас ждешь существенно более эффективных алгоритмов, чем n! ?
Например n^2*2^n пойдёт?
Ты ведь не надеешься, что кто-то решит тут NP-полную задачу за полиномиальное время и докажет мимоходом эквивалентность NP и P классов задач?
Re: Задачка
"Угадать" тестовые данные можно?
Число попыток ответа у вас какое?
Добавлено спустя 35 минут 38 секунд:
Вообще в таком случае нужно бы указать порядок n
Число попыток ответа у вас какое?
Добавлено спустя 35 минут 38 секунд:
Вообще в таком случае нужно бы указать порядок n
Re: Задачка
Есть приближенные алгоритмы с полиномальным и даже линейным временем. Задачу можно считать решенной, если бот после прогона на своих тестовых наборах не обнаружит расхождений со своими ответами. Тестовые данные неизвестны, разумеется. И даже их характер предположить невозможно, известно только, что для любого тестового набора решение гарантированно существует.
Добавлено спустя 2 минуты:
Число попыток неограничено, но задержка между отправкой решения и ответом бота составляет часы. Вариантов ответа 2 - проошел/не прошел
Добавлено спустя 1 минуту 25 секунд:
Предположить порядок графа я могу. С вероятностью 50% он не превышает 1000
Добавлено спустя 2 минуты:
Число попыток неограничено, но задержка между отправкой решения и ответом бота составляет часы. Вариантов ответа 2 - проошел/не прошел
Добавлено спустя 1 минуту 25 секунд:
Предположить порядок графа я могу. С вероятностью 50% он не превышает 1000
Re: Задачка
Ну ты темнишь давай тогда хотя-бы - какие ограничения по времени и по памяти для решений?
Очень похоже на какие-то специфичные соревнования под флагом какого-нибудь гугла для приёма на работу - типа сдал, - приходи пообщаться
С вероятностью 50% не превышает 1000 это откуда взято? Скинь хоть в личку что ли, что это вообще, а то будет как со связностью
давай тогда хотя-бы - какие ограничения по времени и по памяти для решений?Очень похоже на какие-то специфичные соревнования под флагом какого-нибудь гугла
для приёма на работу - типа сдал, - приходи пообщаться С вероятностью 50% не превышает 1000 это откуда взято? Скинь хоть в личку что ли, что это вообще, а то будет как со связностью
Re: Задачка
С вероятностью 50% он не превышает 1000
Гыгык... "ищем современных Эйлеров"...Участвовал как-то в таких...
Только задача была на скорость... (типа, кто быстрее определит простоту чисел - что-то такое)
В конце концов оказалось, что все победители опустились до асма.
То есть не только алгоритмом взяли, но и знанием архитектуры тестирующей системы.
Добавлено спустя 1 минуту:
под флагом какого-нибудь гугла
Тоже так подумал...
Re: Задачка
Условия полностью сформулированы здесь: viewtopic.php?f=17&t=7292&start=45#p141154 (за исключением форматов ввода/вывода - считаю несущественным)
Ограничения по времени - "your program must be fast, and give a correct answer within a matter of minutes"
Больше добавить нечего.
Оттуда, что ничего про это неизвестно Типа шутка юмора
Ограничения по времени - "your program must be fast, and give a correct answer within a matter of minutes"
Больше добавить нечего.
С вероятностью 50% не превышает 1000 это откуда взято?
Оттуда, что ничего про это неизвестно
Типа шутка юмораRe: Задачка
Думаю надо брать приближенный и реализовывать, его использовать как отправную точку для ветвей и границ, а дальше уж как сможешь ветви и границы настроить
Добавлено спустя 57 секунд:
Думаю ни о каких n=1000 не должно быть речи. Кроме случаев когда выкинуть надо совсем мало ребер.
Добавлено спустя 57 секунд:
Думаю ни о каких n=1000 не должно быть речи. Кроме случаев когда выкинуть надо совсем мало ребер.
Re: Задачка
Условия полностью сформулированы здесь: viewtopic.php?f=17&t=7292&start=45#p141154
Это задача, которую вы ставите перед тестирующей системой,
А тестирующая система ставит перед вами совсем другую задачу
(например "взломать ее и выковырять файл с правильным ответом"
)Вероятно, тут нужно идти от обратного - выкидывать заведомо ненужные ветви,
прореживая граф. А остальное перебором довести. Типа "ветвей-границ"
Порядок 1000 тоже считаю нереальным.