Есть ли способ динамического программирования для вычисления k минимальных остовных деревьев?

Question

Мой учитель попросил нас внедрить решение динамического программирования для этой проблемы, но я думаю, что его не существует, так как я не смог найти его с помощью Google.

В любом случае, учитывая график и a k, скажем, 3, вы должны найти 3 лучших MST из него. Если график таков, что в нем нет k поддеревьев, вы можете возвращать либо одно и то же дерево несколько раз, либо неоптимальные деревья.

Я не могу придумать решение этого вопроса.

Answer 1

Вы меня немного запутали, и я подумал, что вы, возможно, неправильно поняли проблему.Задача "k-MST" состоит в том, чтобы найти k ребер, которые образуют поддерево так, что сумма его ребер меньше или равна всем другим суммам, которые вы можете получить из поддеревьев k ребер.Но потом я увидел множественное число s.

Итак, для вашей проблемы я лично попытался бы найти DP-алгоритм для нахождения MST, который сочетается со способом генерации «следующих» MST.Так как это динамическое программирование, я бы посмотрел на многократную оптимизацию чего-либо (в данном случае де-оптимизацию для каждого шага) или на различные способы разделения ребер на подмножества, которые имеют смысл в настройке MST.Там может быть несколько способов.

Тем не менее, при поиске разделов и минимальных остовных деревьев я нашел это, что может помочь, если вы просто хотите получить ответ: http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382005000200004