Блог

Отказ от ответственности # 1: я не профессионал, поэтому многие из моих номенклатур могут быть нестандартными или полезными. Пожалуйста, потерпите меня / отредактируйте меня.

Отказ от ответственности # 2: как следует из тегов, это может показаться теоретическим вопросом, но я думаю, что это вопрос программирования, хотя некоторая теория также была бы хороша.

Сначала позвольте мне описать этот тип отсортированных взвешенных деревьев, которые теперь называются деревьями SWR. Пусть T = (V, E, W, U, m, r) будет дерево SWR. Единственными определяющими свойствами T являются:

• T является m корневым деревом с корнем r , и каждый лист имеет одинаковую высоту / уровень в T
• T имеет предопределенные и неизменные веса на ребрах, определенные функцией W: E -> R ( R это набор положительных действительных чисел)
• T имеет предопределенные и неизменные веса на листьях, определенные функцией U: V_L -> R ( V_L это набор листьев в V )
• Для каждого нелистового узла v T его дочерние элементы сортируются по возрастающим значениям ребер, соединяющих их с v

Теперь позвольте мне описать функцию on T , вызываемую сейчас F(T) . F выдаст число T следующим образом:

• Расширьте функцию U U*: V -> R следующим образом: для каждого нелистового узла v присвоите v наибольшее значение дочерним ребрам v (ребрам, соединяющим v с его дочерними элементами)
• Для каждой высоты / уровня h T вычислите f(h) как минимальное значение вершин (определенных U* ) на этой высоте / уровне
• Суммируйте все f(h) , чтобы получить F(T)

Кроме того, позвольте мне описать правильный процесс обрезки на T . Рассмотрим обрезку ребер. Когда обрезается ребро, его поддерево удаляется. Мало того, все его более крупные ребра (и их поддеревья) также удаляются (имейте в виду, из-за сортировки учитываются только более крупные родственные ребра). Следовательно, оставшееся дерево T' по-прежнему является SWR-деревом и должным образом наследует все свойства T . Очевидно, F(T') изменилось (даже U* и f изменилось).

Поэтому возникает проблема. Учитывая SWR-дерево T , как можно правильно обрезать его, чтобы получить SWR-дерево T' с максимальным значением F ?

Отказ от ответственности # 3: я осознаю тот факт, что проблема похожа на упавшую с неба и довольно грязную. Пожалуйста, не стесняйтесь переформулировать его по своему усмотрению. Кроме того, просто формулировка самой проблемы меня немного утомляет, поэтому у меня пока не было возможности решить эту проблему.

Давайте сначала немного упростим определение вашей проблемы, удалив веса листьев. Теперь, когда ни один из весов не является отрицательным, мы можем поместить по одному дочернему элементу под каждым листом и переместить вес каждого листа на его новый дочерний край.

Я могу записать то, что кажется довольно жесткой целочисленной программой, которая фиксирует эту проблему. Для каждого ребра e переменная x[e] равна 1, если мы сохраняем ребро, в противном случае 0. Переменная y[e] равна 1, если e это минимальное значение максимального родственного значения на ее уровне, в противном случае 0.

 maximize sum_{e} W(e) y[e]
subject to
for all e, x[e] ∈ {0, 1}
for all e, y[e] ∈ {0, 1}
for all e sibling of e' with W(e) ≤ W(e'), x[e'] − x[e] ≤ 0
for all e parent of e', x[e'] − x[e] ≤ 0
for all levels ℓ, for all e at level ℓ, for all p at level ℓ−1, y[e]   x[p] − sum_{e' child of p with W(e) ≤ W(e')} x[e] ≤ 1
for all levels ℓ, sum_{e at level ℓ} y[e] = 1
 

Первые две группы ограничений накладывают ограничения на обрезку. Следующая группа ограничений гласит, что, по сути, ребро не может быть минимальным значением максимального дочернего элемента на своем уровне, если каждая группа дочерних элементов на своем уровне не имеет ребра, по крайней мере, такого же значения или полностью отсутствует. Окончательное ограничение необходимо только для разрыва связей.

Эта формулировка может быть решена как есть с помощью решателя целочисленных программ, но я сильно подозреваю, что существует более эффективный алгоритм.