roboforum.ru

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

Задачка

Все здесь

Re: Задачка

Сообщение =DeaD= » 27 дек 2009, 00:40

Есть ощущение, что минимум ребер в решении может быть n, а максимум 2n-2. Минимум почему такой - очевидно, а вот максимум - есть у кого мнения, что может больше?

Добавлено спустя 4 минуты 15 секунд:
Еще можно проанализировать граф и сразу какие-то ребра записать в решение.
Например, если без какого-то ребра граф становится не сильно связанным - значит это ребро включаем обязательно.

Но в худшем случае в граф будет полным и просто будут разные веса ребер.

Добавлено спустя 5 минут 22 секунды:
При поиске методом ветвей и границ можно использовать:

1. Если уже ребер набрали в решение весом больше, чем до этого нашли оптимальней решение - сваливаем;
2. Если компонент слабой связности k, а ребер можем взять еще не более чем k, не выходя за уже найденный минимальный вес - сваливаем;

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

Re: Задачка

Сообщение Michael_K » 27 дек 2009, 01:15

Меня вот другое интересует...
Существует ли какой-то критерий, который бы позволил определить,
насколько мы приблизились к оптимуму? Может мы его нашли уже?
Или наличие такого критерия сразу делает задачу не NP-трудной?

Добавлено спустя 9 минут 9 секунд:
Интересно, в оригинальной постановке задача допускает несколько решений?
Или решением является не какие машины купить, а только сумма, которую надо на них потратить?
Последний раз редактировалось Michael_K 27 дек 2009, 03:42, всего редактировалось 1 раз.
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: Задачка

Сообщение Виталий » 27 дек 2009, 03:09

Интересно, в оригинальной постановке задача допускает несколько решений?

А если в матрице одинаковые числа?
Все новости о моих проектах http://savethebest.ru
Аватара пользователя
Виталий
 
Сообщения: 2114
Зарегистрирован: 08 окт 2004, 16:43
Откуда: St. Petersburg
Skype: quark-bot
ФИО: Клебан Виталий

Re: Задачка

Сообщение Michael_K » 27 дек 2009, 03:52

Нашел я эту задачку...
Там, как мне кажется, (хотя гарантировать, конечно, нельзя)
сильно прореженная матрица (или граф) задается.
Да, нужно в ответе указать какие конкретно машины купить.
И вряд ли условия допускают два одинаковых решения.
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: Задачка

Сообщение blindman » 27 дек 2009, 08:58

Если бот "честный", то он обязан задавать условия так, чтобы было ровно одно решение.

Добавлено спустя 1 час 17 минут 25 секунд:
Создатели задачи конечно понимают, что в общем виде задача нерешаема. Поэтому наверняка исходный граф удовлетворяет неким условиям, которые позволяют найти решение. Поэтому фактически решение состоит из 2 частей : сделать верное предположение о структуре исходного графа, и решить основываясь на этом предположении.

В первую очередь, напрашивается предположение что граф разрежен. Это подтверждается словами одного из решивших задачу: "there are more compounds than you think, but fewer machines"

Добавлено спустя 16 минут 26 секунд:
Вполне возможно, тестовые данные генерятся примерно так: соединяем все n вершин n дугами в кольцо, в каждую вершину входит ровно 1 дуга и выходит ровно 1. Потом случайным образом добавляем некоторое количество дуг, подбирая их вес так, чтобы решение в виде кольца было не оптимальным, и проверяя, чтобы оптимальное решение было единственным.
Проект [[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: Задачка

Сообщение MegaBIZON » 27 дек 2009, 09:44

c ума посходили все :no:
.............солнце светит, птички поют, я - зелёный бамбук меня тянет к солнцуЯ - зелёный бамбук, я - зелёный бамбук , меня тянет к солнцу. Я - не огурчик и не лягушка, я - зелёный бамбук. Меня курят...............
Аватара пользователя
MegaBIZON
 
Сообщения: 6285
Зарегистрирован: 12 янв 2007, 00:34
Откуда: Масква

Re: Задачка

Сообщение =DeaD= » 27 дек 2009, 11:10

Michael_K писал(а):Нашел я эту задачку...
Там, как мне кажется, (хотя гарантировать, конечно, нельзя)
сильно прореженная матрица (или граф) задается.

Мы делали не так.

Michael_K писал(а):Да, нужно в ответе указать какие конкретно машины купить.
И вряд ли условия допускают два одинаковых решения.

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

blindman писал(а):Создатели задачи конечно понимают, что в общем виде задача нерешаема. Поэтому наверняка исходный граф удовлетворяет неким условиям, которые позволяют найти решение. Поэтому фактически решение состоит из 2 частей : сделать верное предположение о структуре исходного графа, и решить основываясь на этом предположении.

Не факт, может быть задачу можно решить за N^2*2^N операций, тогда при n=20 это всего 420млн операций.

blindman писал(а):В первую очередь, напрашивается предположение что граф разрежен. Это подтверждается словами одного из решивших задачу: "there are more compounds than you think, but fewer machines"

Если бы я ставил задачу на решение которой надо реально заморочиться - я бы брал пачку тестов - с сильно разреженным графом, с полным графом, почти решение (всего 2-3 ребра выкинуть надо из огромного графа, скажем n=400, кол-во ребер 403) - в общем потребовал бы до кучи выбор алгоритма решения в зависимости от входящего набора данных :)


blindman писал(а):Вполне возможно, тестовые данные генерятся примерно так: соединяем все n вершин n дугами в кольцо, в каждую вершину входит ровно 1 дуга и выходит ровно 1. Потом случайным образом добавляем некоторое количество дуг, подбирая их вес так, чтобы решение в виде кольца было не оптимальным, и проверяя, чтобы оптимальное решение было единственным.

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

Re: Задачка

Сообщение blindman » 27 дек 2009, 11:49

Достоверно известно, что на входе всегда данные, ведущие ровно к 1 оптимальному решению.
Проект [[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: Задачка

Сообщение Michael_K » 27 дек 2009, 15:21

Насчет одного кольца я бы не предполагал - это вряд ли.
Задача генерится "от обратного" - да, вполне может быть.
Хотя может быть и решена (или проверена) полным перебором за неделю.

Наверняка, _алгоритмическим_ оптимумом будет применение нескольких алгоритмов
(Из опыта решения такого рода задач). Может также быть оптимум основанный на реализации.

Это по ощущениям... то есть просто предположение.

blindman, а что сервер возвращает в ответ?
Ну, может быть время выполнения вашей программы, сколько она памяти заняла,
или еще какие-нибудь данные? Что-нибудь, чтобы можно было оценить параметры заданий?

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

Re: Задачка

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

а что сервер возвращает в ответ

Прошел, не прошел.

"не прошел" может означать что угодно - неверный результат, программа не компилируется, и т.п.
Проект [[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: Задачка

Сообщение Michael_K » 27 дек 2009, 16:10

"there are more compounds than you think, but fewer machines"

Очевидно полный перебор будет более реален,
а вот проверка на связность - более сложной...

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

Re: Задачка

Сообщение blindman » 27 дек 2009, 16:13

Пробовал, не проходит
Проект [[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= » 27 дек 2009, 16:30

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

Re: Задачка

Сообщение Michael_K » 27 дек 2009, 17:04

Надо попросить сетара выделить десяток терафлопсов,
а в проге открыть сокет и приконнектиться :)

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

Re: Задачка

Сообщение blindman » 27 дек 2009, 17:11

Ага, типа ты один такой умный :D
Проект [[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(?)
ФИО: Андрей Юрьевич

Пред.След.

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

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

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

cron