Недавно меня спросили, могу ли я найти алгоритм вычисления дерева привязки минимальных затрат для данного графика, где общая стоимость остовного дерева определяется продукт края стоит, а не их суммой.Алгоритм поиска минимального связующего дерева, когда стоимость задается умножением весов ребер
Существует несколько алгоритмов вычисления обычного миниатюрного остовного дерева, но я не уверен, как их настроить для упомянутого выше случая. Есть идеи?
спасибо.
Поскольку лог (продукт затрат на краю) = сумма (лог (затраты по краю)), просто лог-трансформируйте края-весы и найдите минимальное связующее дерево для этих весов.
Моя лучшая идея - Найдите ВСЕ минимальные (что означает ненужные края), обводя деревья грубой силой, выберите один с наименьшим произведением.
Большинство (или все) более эффективных решений больше не применяются - в основном, оптимальные решения bc НЕ ДОЛЖНЫ обязательно содержать оптимальные подпункты. (Каковы ограничения? Очень важно - края стоимости меньше 1 на самом деле отрицательные затраты, края длины 1 бесплатны, они ЛУЧШЕ все положительные!)
Я не уверен, действительно ли этот вопрос имеет смысл. Во-первых, вы должны либо дать затраты на самозарядку (или принять 1), потому что мы не можем взять продукт с нулем. Разделение пути работает по-разному, путешествие по тому же пути дважды стоит c^2? Кроме того, мне кажется, что это должно быть другое качество пути с другим именем, чем «стоимость»
. Для обсуждения мы могли предположить, что все затраты положительные числа больше или равные 1. Спасибо за идею. – AlexTex
Поскольку логарифм является монотонным преобразованием, минимальное остовное дерево будет точно таким же, когда вы берете журнал всех весов и когда вы оставляете все веса так, как они есть. Итак: нет никакой разницы в поиске MST в соответствии с суммой всех весов и в соответствии с продуктом всех весов.
Для статьи доказательства того факта, что минимального покрывающего дерева графа инвариантно по отношению к монотонной трансформации весов в graoh, типа Сага минимального остова в гугле. И первая ссылка будет той, которая вам нужна. Page 167 монотонный изоморфизм.
oooh хороший ответ! плохо упомянуть ограничения, если это не очевидно - затраты ДОЛЖНЫ все быть положительными, и ДОЛЖНЫ все быть> 1. –
@jon_darkstar Вы правы, они должны быть все положительными, но я считаю, что значения 0-1 в порядке. Полученное дерево не будет минимальным подграфом (поскольку добавление дополнительных ребер может потенциально снизить стоимость), но это будет минимальная стоимость _tree_. – Aniko
Да, вы правы, ограничение «дерева» уже имеет такую глупость. –