Задачка

Michael_K

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

=DeaD=

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

Добавлено спустя 1 минуту:

Michael_K писал(а):

Классический коммивояжер.
Насколько я понимаю, решения кроме перебора нет

Скажем так - науке неизвестно решение за полиномиальное время, по крайней мере без применения всяких волшебных квантовых компьютеров

Michael_K

Ну, блин...

...длинные слова меня только расстраивают (с)

=DeaD=

Ну если с матрицами проще... я просто с графами больше работал в таком ключе

blindman

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

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

Строится химзавод, для производства некоего продукта. Для его производства необходимо ровно n исходных компонентов. Имеется возможность закупить машины, которые из одного компонента делают другой. Не факт, что для любой пары i,j (0<=i<n, 0<=j<n, i<>j) существует машина, которая из i делает j. Стоимость компонентов и эксплуатации машин ничтожно мала, сами машины очень дороги. Необходимо определить, какие машины следует закупить, чтобы их суммарная стоимость была минимальна, и чтобы завод мог функционировать независимо от того, какие исходные компоненты имеются в наличии.

Michael_K

Цитата:

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

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

Он же вероятностный по сути.

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

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

=DeaD=

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

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

Ну и ты и запутал задачу

blindman

Цитата:

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

Нет.

Michael_K

Цитата:

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

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

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

Добавлено спустя 22 секунды:
А, нет...
Не факт, что оптимум

blindman

=DeaD= писал(а):

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

Нету

Michael_K

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

=DeaD=

Для неориентированного графа эта задача называется поиском минимального остова, решается алгоритмом Прима-Краскала, для ориентированных сейчас гляну.

Michael_K

не... не слушайте меня - это я тороплюсь.
Реально сделать из нефти парафин может быть сложнее, чем из парафина - нефть...

=DeaD=

Michael_K писал(а):

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

Это алгоритм Прима, только для неориентированных графов

Michael_K

Цитата:

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

Ага... вот именно эти самые слова

roboforum.ru

Задачка

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