Я видел вопрос в codechef, где цель состоит в том, чтобы выбрать ребра из графа так, чтобы выбранные ребра не образовывали цикл, а также произведение весов всех выбранных ребер было максимальным. В редакционной статье указано, что работает алгоритм Прима и Крускала. здесь. На самом деле дано, что он работает для максимизации любой симметричной монотонной функции ребер. Так что же такое симметричная монотонная функция и где еще мы можем использовать эти алгоритмы.
Применение Прима и Крускала, кроме поиска MST
Ответы (1)
Я предполагаю, что авторы имеют в виду следующее:
Если ваша окончательная оценка по остовному дереву равна f(w1, w2, ... wn), где wi — это веса ребер, то f должна быть монотонной по весам. Это означает, что если вы увеличиваете любой вес, f будет либо всегда увеличиваться (монотонно возрастать), либо всегда уменьшаться (монотонно уменьшаться). И сумма, и произведение монотонно возрастают:
f_sum (w1, w2, ... wn) = w1 + w2 + ... + wn
f_prod(w1, w2, ... wn) = w1 * w2 * ... * wn //non-negative-weights
Симметричный относится к порядку. f является симметричным, если вы можете гарантировать, что f(..., wi, ..., wj, ...) = f(..., wj, ..., wi, ...). Должно быть понятно, зачем это нужно. Любой алгоритм MST должен заботиться только о том, какие ребра выбрать, а не об их порядке. И сумма, и произведение являются коммутативными операциями и поэтому симметричны.
Причина, по которой это работает, заключается в том, что все остовные деревья для данного графа имеют одинаковое количество ребер. Если вы жадно возьмете максимально доступное ребро (для монотонно возрастающих функций) или минимальное ребро (для монотонно убывающих функций), вы автоматически максимизируете f.
Большинство приложений, о которых я знаю, являются приложениями MST (в основном для аппроксимации оптимального решения). С точки зрения вероятностных моделей, максимальный продукт может относиться к максимизации конечной вероятности, где ребра представляют вероятности отдельных событий, которые затем объединяются. Я не наткнулся на какие-либо другие функции для построения связующего дерева.
person
Nico Schertler
schedule
01.08.2015
Хороший ответ, но я подозреваю, что симметричность означает, что `f(...,wj...,wk...) = f(...,wk,...,wj,...)', например коммутативный закон сложения или умножения. Вам нужно какое-то условие, которое гарантирует, что вы находитесь в оптимуме, как только вы не можете поменять местами ни одно ребро в остовном дереве на лучшее ребро за пределами дерева (с лучшим определением того, минимизируете вы или максимизируете) при сохранении подключение.
- person John Coleman; 01.08.2015
Я думаю, что Джон Коулман прав насчет симметричности.en.wikipedia.org/wiki/Symmetric_function
- person Naveen Reddy; 01.08.2015
@JohnColeman Понятно. Спасибо за указание на это. Я исправил ответ.
- person Nico Schertler; 01.08.2015
