Алгоритм нахождения минимального остовного дерева, когда стоимость определяется умножением весов ребер

Question

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

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

Спасибо.

Answer 1

Поскольку log (произведение затрат на ребра) = сумма (log (затраты на ребра)), просто выполните лог-преобразование весов ребер и найдите минимальное связующее дерево для этих весов.

Answer 2

Поскольку логарифм является монотонным преобразованием, минимальное остовное дерево будет точно таким же, когда вы берете лог всех весов и оставляете все веса такими, какие они есть. Итак: НЕТ разницы в нахождении MST по сумме всех весов и по произведению всех весов.

За статью доказательства факта тот минимальное остовное дерево графа инвариантен к монотонному преобразованию весов в граохе, тип Сага о минимальном остове дерева в гугле. И первая ссылка будет той, которая вам нужна. Страница 167, монотонный изоморфизм.

Answer 3

Моя лучшая идея - найти ВСЕ минимальные (то есть ненужные ребра) остовные деревья грубой силой, выбрать тот, который имеет наименьшее произведение.

Большинство (или все) более эффективных решений больше не применяются - в основном это оптимальные решения, НИКАКИЕ БОЛЬШЕ не обязательно содержат оптимальные подзадачи.(Каковы ограничения? Очень важно - ребра стоимости меньше 1 на самом деле отрицательные затраты, ребра длины 1 бесплатны. ЛУЧШЕ все положительные!)

Я не уверен, действительно ли этот вопрососмысленный.Для одного вы должны либо указать затраты на самоконтроль (либо предположить 1), потому что мы не можем взять продукт с нулем.Разделение пути работает по-другому, путешествие по одному и тому же пути дважды стоит с ^ 2?Кроме того, я чувствую, что это должно быть другое качество пути с другим именем, чем «стоимость»