(Мне было трудно найти подобную проблему, поэтому, если есть более подходящее название для этого типа проблемы, пожалуйста, дайте мне знать.)
Я застрял на проблеме, гдеЯ пытаюсь найти несколько центральных точек двоичного дерева.Под этим я подразумеваю, если у меня есть двоичное дерево с n вершинами, я хочу найти набор вершин в дереве S = [v1, v2, ..., vk], чтобы максимальное расстояние (число прыжков) между каждымвершина дерева и ближайшая к нему вершина S минимизирована.Кроме того, вершина в S, ближайшая к каждой вершине, должна быть ее предком.Таким образом, если вершина в дереве не имеет предка в S, ее значение расстояния будет бесконечностью.
Простой пример:
У дерева есть корневой узел 1, который разделяется на два узла 2 и 3, а узел 3 далее разделяется на 4 и 5. Если я выбрал k = 2 вершины для Sоптимальным решением будет S = [1, 3] с общей стоимостью расстояния 3. Субоптимальным решением будет S = [1, 2] с расстоянием 5. Если S = [2,3] расстояниебудет бесконечность.
Я бы предположил, что корень дерева всегда должен быть в множестве S, иначе расстояние будет inf.Но я не уверен, как определить, как следует выбирать другие элементы S.
Я думаю, что, возможно, мне следует сделать рекурсивную попытку, где я начинаю с корня и повторяюсь на каждом из двухдочерние узлы и отслеживать общее расстояние между каждым родительским узлом и всеми узлами под ним.Но я не знаю, куда идти.
Какие-нибудь советы о том, как сделать что-то подобное?