@cancrushem

Задача которую мне необходимо решить сводится к нахождению Minimal Ratio Spanning Tree.
Условие вкратце - дан граф (связный и обыкновенный). Каждое ребро графа имеет 2 веса (допустим Ai и Bi для i-го ребра). Надо найти покрывающее дерево у которого минимально отношение (сумма(Ai)/сумма(Bi)) ребер, входящих в такое дерево. Так и не удалось найти алгоритм, который находит оптимальное поддерево при любых входных данных . Изначально я пытался модифицировать алгоритм Прима, но там не совсем понятно, как реализовать нахождение оптимального ребра на каждом шаге. Прошу помочь мне с данной проблемой.

Добавлено через 22 часа 49 минут
Я так и не смог найти нормальное описание алгоритма поиска такого дерева в литературе - только намеки. Могу запостить описание того алгоритма, который на данный момент написан. Имеются подозрения, что он некорректно обработает определенные графы, хотя неплохо работает на примитивных примерах.

0

@salam

Задача NP-трудная. Пишите перебор. Если есть интерес, попробуйте придумать какие-то оптимизации.

Добавлено через 2 минуты
задача NP-трудная. пишите перебор. если есть интерес, попридумывайте какие-то оптимизации.

0

@cancrushem

То есть кроме перебора всех покрывающих деревьев других вариантов нет ?

0

@salam

Если вы хотите получить наилучшее решение - изучайте литературу.

0