roboforum.ru

Технический форум по робототехнике.


Задачка

Все здесь

Re: Задачка

Сообщение =DeaD= » 25 дек 2009, 21:33

Пытаюсь понять, как обобщить Прима-Краскала на ориентированные графы и не получается с ходу :) и главное в инете на эту тему тишина :)
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Задачка

Сообщение blindman » 25 дек 2009, 21:35

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

Добавлено спустя 1 минуту 28 секунд:
http://en.wikipedia.org/wiki/Minimum_sp ... d_problems
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: Задачка

Сообщение =DeaD= » 25 дек 2009, 21:51

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

Ну вот, я же говорил, что очень уж от задачки 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:
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Задачка

Сообщение blindman » 25 дек 2009, 21:52

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

Похоже, не то :(
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.

Я так понимаю, что если добавление ребра создает замкнутый путь, то это ребро удаляется. А тут без замкнутого пути, как минимум одного, никак
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: Задачка

Сообщение =DeaD= » 25 дек 2009, 22:06

Вот еще указание, что это 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.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Задачка

Сообщение =DeaD= » 26 дек 2009, 09:22

Ну как, принимаешь ответ "нет ответа" ? :wink:
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Задачка

Сообщение blindman » 26 дек 2009, 09:46

Нет. Решение оценивает робот, который слова "нет" не знает
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: Задачка

Сообщение =DeaD= » 26 дек 2009, 13:48

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

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

Ты ведь не надеешься, что кто-то решит тут NP-полную задачу за полиномиальное время и докажет мимоходом эквивалентность NP и P классов задач? ;)
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Задачка

Сообщение Michael_K » 26 дек 2009, 15:06

"Угадать" тестовые данные можно? :)
Число попыток ответа у вас какое? :oops: :crazy:

Добавлено спустя 35 минут 38 секунд:
Вообще в таком случае нужно бы указать порядок n
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: Задачка

Сообщение blindman » 26 дек 2009, 15:11

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

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

Добавлено спустя 1 минуту 25 секунд:
Предположить порядок графа я могу. С вероятностью 50% он не превышает 1000 :)
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: Задачка

Сообщение =DeaD= » 26 дек 2009, 15:17

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

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

С вероятностью 50% не превышает 1000 это откуда взято? Скинь хоть в личку что ли, что это вообще, а то будет как со связностью :)
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Задачка

Сообщение Michael_K » 26 дек 2009, 15:22

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

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


Добавлено спустя 1 минуту:
под флагом какого-нибудь гугла :) для приёма на работу

Тоже так подумал...
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: Задачка

Сообщение blindman » 26 дек 2009, 15:27

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

Оттуда, что ничего про это неизвестно :) Типа шутка юмора
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: Задачка

Сообщение =DeaD= » 26 дек 2009, 15:32

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

Добавлено спустя 57 секунд:
Думаю ни о каких n=1000 не должно быть речи. Кроме случаев когда выкинуть надо совсем мало ребер.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Задачка

Сообщение Michael_K » 26 дек 2009, 15:45

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

Это задача, которую вы ставите перед тестирующей системой,
А тестирующая система ставит перед вами совсем другую задачу :wink:
(например "взломать ее и выковырять файл с правильным ответом" :) )

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

Порядок 1000 тоже считаю нереальным.
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Пред.След.

Вернуться в Свободное общение

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

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 5

Mail.ru counter