Существует ли Динамическое программирование способ вычислить k минимальные связующие деревья?
Мой учитель попросил, чтобы мы реализовали решение для Динамического программирования той проблемы, но я думаю, что каждый не существует, так как я не мог найти это Google использования.
Так или иначе, учитывая график и k, скажите 3, необходимо найти 3 лучших MSTs от него. Если график таков, что не имеет k поддеревьев, можно возвратить или то же дерево многократно или субоптимальные деревья.
Я не могу действительно думать о решении его.
1 ответ
Вы меня немного сбили с толку, и я подумал, что вы могли неправильно понять проблему. Задача «k-MST» состоит в нахождении k ребер, которые образуют поддерево, сумма которых меньше или равна всем другим суммам, которые вы можете получить из поддеревьев из k ребер. Но потом я увидел множественное число s.
Итак, для вашей проблемы я бы лично попытался найти DP-алгоритм для поиска MST, который сочетается со способом генерации «следующих» MST. Поскольку это динамическое программирование, я бы рассмотрел возможность многократной оптимизации чего-либо (в данном случае деоптимизации для каждого шага) или различных способов разделения ребер на подмножества, которые имеют смысл в настройке MST. Может быть несколько способов.
Тем не менее, при поиске разделов и минимальных остовных деревьев я обнаружил это, что может оказаться более полезным, если вам просто нужен ответ: http://www.scielo.br/scielo.php?script=sci_arttext&pid= S0101-74382005000200004