В исходной - да.
Классический коммивояжер.
Насколько я понимаю, решения кроме перебора нет,
(эвристики есть, но не гарантируют _оптимальный_ результат, за число операций меньшее, чем перебор)
roboforum.ru
Технический форум по робототехнике.
Задачка
Re: Задачка
Последний раз редактировалось Michael_K 25 дек 2009, 20:59, всего редактировалось 1 раз.
Re: Задачка
А последняя задача суть - выбрать в ориентированном взвешенном графе часть ребер так, чтобы вес был минимален, и в каждую вершину было минимум 1 входящее и 1 исходящее ребро.
Добавлено спустя 1 минуту:
Скажем так - науке неизвестно решение за полиномиальное время, по крайней мере без применения всяких волшебных квантовых компьютеров
Добавлено спустя 1 минуту:
Michael_K писал(а):Классический коммивояжер.
Насколько я понимаю, решения кроме перебора нет
Скажем так - науке неизвестно решение за полиномиальное время, по крайней мере без применения всяких волшебных квантовых компьютеров
Re: Задачка
Ну, блин...
...длинные слова меня только расстраивают (с)
...длинные слова меня только расстраивают (с)
Re: Задачка
Ну если с матрицами проще... я просто с графами больше работал в таком ключе
Re: Задачка
Изначальная постановка задачи была неверной. Правильная - с измененным условием 3.
Короче, вытянули. Вот оригинальная постановка задачи.
Строится химзавод, для производства некоего продукта. Для его производства необходимо ровно n исходных компонентов. Имеется возможность закупить машины, которые из одного компонента делают другой. Не факт, что для любой пары i,j (0<=i<n, 0<=j<n, i<>j) существует машина, которая из i делает j. Стоимость компонентов и эксплуатации машин ничтожно мала, сами машины очень дороги. Необходимо определить, какие машины следует закупить, чтобы их суммарная стоимость была минимальна, и чтобы завод мог функционировать независимо от того, какие исходные компоненты имеются в наличии.
Короче, вытянули. Вот оригинальная постановка задачи.
Строится химзавод, для производства некоего продукта. Для его производства необходимо ровно n исходных компонентов. Имеется возможность закупить машины, которые из одного компонента делают другой. Не факт, что для любой пары i,j (0<=i<n, 0<=j<n, i<>j) существует машина, которая из i делает j. Стоимость компонентов и эксплуатации машин ничтожно мала, сами машины очень дороги. Необходимо определить, какие машины следует закупить, чтобы их суммарная стоимость была минимальна, и чтобы завод мог функционировать независимо от того, какие исходные компоненты имеются в наличии.
Re: Задачка
по крайней мере без применения всяких волшебных квантовых компьютеров
А разве волшебный квантовый компьютер что-то вообще может гарантировать?
Он же вероятностный по сути.
Ну, раз сводится к коммивояджеру, то быстрые эвристики без гарантии оптимума можно тупо в инете поискать...
Условие "не факт, что для любой пары" просто прореживает матрицу или граф...
(или цена этой ветки заведомо огромна)... и есть вероятность, что решение вообще невозможно?
Re: Задачка
Андрей, так и с измененным условием 3 задача не верна, где требование связности?
Тебе нужно реально в ориентированном графе найти подмножество ребер обеспечивающее полную связность или как она там называется (т.е. из любой вершины по оставшимся ребрам с учетом их направленности можно пройти в любую другую) и вес ребер не отрицательный.
Ну и ты и запутал задачу
Тебе нужно реально в ориентированном графе найти подмножество ребер обеспечивающее полную связность или как она там называется (т.е. из любой вершины по оставшимся ребрам с учетом их направленности можно пройти в любую другую) и вес ребер не отрицательный.
Ну и ты и запутал задачу
Re: Задачка
есть вероятность, что решение вообще невозможно?
Нет.
Re: Задачка
где требование связности?
действительно
Добавлено спустя 4 минуты 17 секунд:
Выбирать из графа все ребра с минимальными весами, пока он не "свяжется",
потом исключить ребра с максимальными весами, так чтобы свяность не потерялась.
Добавлено спустя 22 секунды:
А, нет...
Не факт, что оптимум
Re: Задачка
=DeaD= писал(а):Андрей, так и с измененным условием 3 задача не верна, где требование связности?
Нету
Re: Задачка
Объединять вершины, с минимальными весами ребер, пока не свяжется. Вот так правильно.
(пока все вершины не объединятся в одну)
(пока все вершины не объединятся в одну)
Re: Задачка
Для неориентированного графа эта задача называется поиском минимального остова, решается алгоритмом Прима-Краскала, для ориентированных сейчас гляну.
Re: Задачка
не... не слушайте меня - это я тороплюсь.
Реально сделать из нефти парафин может быть сложнее, чем из парафина - нефть...
Реально сделать из нефти парафин может быть сложнее, чем из парафина - нефть...
Re: Задачка
Michael_K писал(а):Объединять вершины, с минимальными весами ребер, пока не свяжется. Вот так правильно.
(пока все вершины не объединятся в одну)
Это алгоритм Прима, только для неориентированных графов
Re: Задачка
... для неориентированного графа... ...для ориентированных... алгоритм Прима-Краскала
Ага... вот именно эти самые слова
Последний раз редактировалось Michael_K 25 дек 2009, 21:33, всего редактировалось 1 раз.