roboforum.ru

[Michael_K]

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

[=DeaD=]

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

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

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

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

[Michael_K]

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

[=DeaD=]

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

[blindman]

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

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

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

[Michael_K]

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

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

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

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

[=DeaD=]

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

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

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

[blindman]

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

Нет.

[Michael_K]

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

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

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

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

[blindman]

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

Нету

[Michael_K]

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

[=DeaD=]

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

[Michael_K]

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

[=DeaD=]

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

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

[Michael_K]

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

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