roboforum.ru

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


Задачка

Все здесь

Re: Задачка

Сообщение Michael_K » 25 дек 2009, 20:57

В исходной - да.
Классический коммивояжер.
Насколько я понимаю, решения кроме перебора нет,
(эвристики есть, но не гарантируют _оптимальный_ результат, за число операций меньшее, чем перебор)
Последний раз редактировалось Michael_K 25 дек 2009, 20:59, всего редактировалось 1 раз.
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: Задачка

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

А последняя задача суть - выбрать в ориентированном взвешенном графе часть ребер так, чтобы вес был минимален, и в каждую вершину было минимум 1 входящее и 1 исходящее ребро.

Добавлено спустя 1 минуту:
Michael_K писал(а):Классический коммивояжер.
Насколько я понимаю, решения кроме перебора нет

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

Re: Задачка

Сообщение Michael_K » 25 дек 2009, 21:00

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

Re: Задачка

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

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

Re: Задачка

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

Изначальная постановка задачи была неверной. Правильная - с измененным условием 3.

Короче, вытянули. Вот оригинальная постановка задачи.

Строится химзавод, для производства некоего продукта. Для его производства необходимо ровно n исходных компонентов. Имеется возможность закупить машины, которые из одного компонента делают другой. Не факт, что для любой пары i,j (0<=i<n, 0<=j<n, i<>j) существует машина, которая из i делает j. Стоимость компонентов и эксплуатации машин ничтожно мала, сами машины очень дороги. Необходимо определить, какие машины следует закупить, чтобы их суммарная стоимость была минимальна, и чтобы завод мог функционировать независимо от того, какие исходные компоненты имеются в наличии.
Проект [[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 » 25 дек 2009, 21:16

по крайней мере без применения всяких волшебных квантовых компьютеров :)

А разве волшебный квантовый компьютер что-то вообще может гарантировать? :wink:
Он же вероятностный по сути.

Ну, раз сводится к коммивояджеру, то быстрые эвристики без гарантии оптимума можно тупо в инете поискать...

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

Re: Задачка

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

Андрей, так и с измененным условием 3 задача не верна, где требование связности?

Тебе нужно реально в ориентированном графе найти подмножество ребер обеспечивающее полную связность или как она там называется (т.е. из любой вершины по оставшимся ребрам с учетом их направленности можно пройти в любую другую) и вес ребер не отрицательный.

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

Re: Задачка

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

есть вероятность, что решение вообще невозможно?

Нет.
Проект [[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 » 25 дек 2009, 21:24

где требование связности?

действительно

Добавлено спустя 4 минуты 17 секунд:
Выбирать из графа все ребра с минимальными весами, пока он не "свяжется",
потом исключить ребра с максимальными весами, так чтобы свяность не потерялась.

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

Re: Задачка

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

=DeaD= писал(а):Андрей, так и с измененным условием 3 задача не верна, где требование связности?

Нету :oops:
Проект [[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 » 25 дек 2009, 21:25

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

Re: Задачка

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

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

Re: Задачка

Сообщение Michael_K » 25 дек 2009, 21:31

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

Re: Задачка

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

Michael_K писал(а):Объединять вершины, с минимальными весами ребер, пока не свяжется. Вот так правильно.
(пока все вершины не объединятся в одну)

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

Re: Задачка

Сообщение Michael_K » 25 дек 2009, 21:32

... для неориентированного графа... ...для ориентированных... алгоритм Прима-Краскала

Ага... вот именно эти самые слова :(
Последний раз редактировалось Michael_K 25 дек 2009, 21:33, всего редактировалось 1 раз.
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Пред.След.

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

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

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

Mail.ru counter