Недавно меня спросили, могу ли я найти алгоритм для вычисления остовного дерева с минимальной стоимостью данного графа, где общая стоимость остовного дерева определяется произведением стоимостей ребер, а не их суммой.
Существует несколько алгоритмов для вычисления обычного остовного дерева миниума, но я не уверен, как их настроить для упомянутого выше случая. Есть идеи?
Спасибо.
Поскольку log(произведение затрат на ребра) = сумма (log(стоимости на ребрах)), просто преобразуйте веса ребер в логарифмическое преобразование и найдите остовное дерево с минимальной стоимостью для этих весов.
Поскольку логарифмирование — это монотонное преобразование, минимальное остовное дерево будет точно таким же, если взять логарифм всех весов и оставить все веса такими, какие они есть. Итак: НЕТ разницы в нахождении МСТ по сумме всех весов и по произведению всех весов.
Для статьи о доказательстве того факта, что минимальное остовное дерево графа инвариантно к монотонному преобразованию весов в графе, наберите в гугле «Сага о минимальном остовном дереве». И первая ссылка будет той, которая вам нужна. Стр. 167, монотонный изоморфизм.
Моя лучшая идея - найти ВСЕ минимальные (в смысле ненужных ребер) остовные деревья методом грубой силы, выбрать тот, у которого наименьший продукт.
Большинство (или все) более эффективных решений больше не применяются - в основном, потому что оптимальные решения БОЛЬШЕ НЕ обязательно содержат оптимальные подзадачи. (Какие ограничения? Очень важно - ребра со стоимостью меньше 1 на самом деле имеют отрицательную стоимость, ребра длины 1 свободны. ЛУЧШЕ, чтобы все они были положительными!)
Я не уверен, что этот вопрос действительно имеет смысл. Во-первых, вы должны либо указать стоимость цикла (или принять 1), потому что мы не можем взять продукт с нулем. Разделение пути работает по-другому, путешествие по одному и тому же пути дважды стоит c ^ 2? Кроме того, я чувствую, что это должно быть другое качество пути с другим именем, чем «стоимость».
