Взвешенный матроид

В комбинаторике , разделе математики , взвешенный матроид — это матроид, наделенный функцией, которая присваивает вес каждому элементу. Формально пусть $M=(E,I)$ быть матроидом, где E — множество элементов, а I — семейство независимых множеств. Взвешенный матроид имеет весовую функцию $w:E\rightarrow \mathbb {R} ^{+}$ for присваивает строго положительный вес каждому элементу $E$. Распространяем функцию на подмножества $E$ путем суммирования; $w(A)$ это сумма $w(x)$ над $x$ в $A$.

Нахождение независимого множества максимального веса

Основная проблема взвешенных матроидов — найти независимый набор с максимальным общим весом. Эту проблему можно решить с помощью следующего простого жадного алгоритма :

• Инициализируйте набор A пустым набором. Обратите внимание, что по определению матроида A является независимым множеством.
• Для каждого элемента x в E \ A проверьте, является ли Au{x} независимым множеством.
  • Если таких элементов нет, то остановитесь, так как A больше не может быть расширен.
  • Если есть хотя бы один такой элемент, то выберите тот, у которого максимальный вес, и добавьте его в A.

Этому алгоритму не нужно ничего знать о структуре матроида; ему просто нужен оракул независимости для матроида - подпрограмма для проверки того, является ли набор независимым.

Джек Эдмондс доказал, что этот простой алгоритм действительно находит независимое множество с максимальным весом. Обозначим найденное алгоритмом множество через e ₁ ,..., _ek . Из свойств матроида ясно, что k=rank(M), иначе множество можно было бы расширить. Предположим от противного, что существует другое множество с большим весом. Без ограничения общности можно предположить, что это множество тоже имеет элементы ранга(М); обозначим его через f ₁ ,...,f _k . Упорядочите эти элементы так, чтобы w(f ₁ ) ≥ ... ≥ w(f _k ). Пусть j будет первым индексом, для которого w(f _j ) > w(e _j ). Примените свойство увеличения к наборам {f ₁ ,...,f _j } и {e ₁ ,...,e _j-1 }; мы заключаем, что должен существовать некоторый i ⩽ j такой, что f _i можно было бы добавить к {e ₁ ,...,e _j-1 }, сохраняя при этом его независимость. Но w(fi ₎ ≥ w(f _j ) > w(e _j ), поэтому _{следовало выбрать fi} на шаге j вместо e _j - противоречие.

Пример: алгоритмы охватывающего леса

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

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

В поисках основы

Существует простой алгоритм поиска основы:

• Первоначально пусть $A$ быть пустым множеством.
• Для каждого $x$ в $E$
  • если $A\cup \{x\}$ независима, то положим $A$ к $A\cup \{x\}$.

В результате получается, очевидно, независимое множество. Это максимальное независимое множество, потому что если $B\cup \{x\}$ не является независимым для некоторого подмножества $B$ из $A$, затем $A\cup \{x\}$ также не является независимым (противоположное следует из наследственного свойства ). Таким образом, если мы пропустим элемент, у нас никогда не будет возможности использовать его позже. Мы обобщим этот алгоритм для решения более сложной задачи.

Расширение до оптимального

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

• Первоначально пусть $A$ быть пустым множеством.
• Для каждого $x$ в $E$, взятые в (монотонном) порядке убывания веса
  • если $A\cup \{x\}$ независима, то положим $A$ к $A\cup \{x\}$.

Этот алгоритм находит базис, поскольку является частным случаем приведенного выше алгоритма. Он всегда выбирает элемент наибольшего веса, который может, сохраняя при этом независимость (отсюда и термин «жадный»). Это всегда дает оптимальный набор: предположим, что он производит $A=\{e_{1},e_{2},\ldots ,e_{r}\}$ и это $B=\{f_{1},f_{2},\ldots ,f_{r}\}$. Теперь для любого $k$ с $1\leq k\leq r$, рассмотрим открытые множества $O_{1}=\{e_{1},\ldots ,e_{k-1}\}$ и $O_{2}=\{f_{1},\ldots ,f_{k}\}$. С $O_{1}$ меньше, чем $O_{2}$, есть какой-то элемент $O_{2}$ который можно положить в $O_{1}$ при этом результат по-прежнему остается независимым. Однако $e_{k}$ — элемент максимального веса, который можно добавить к $O_{1}$ для сохранения независимости. Таким образом $e_{k}$ имеет не меньший вес, чем некоторый элемент $O_{2}$, и, следовательно, $e_{k}$ имеет по крайней мере большой вес, так как $f_{k}$. Поскольку это верно для всех $k$, $A$ тяжелее, чем $B$.

Анализ сложности

Самый простой способ обойти члены $E$ в желаемом порядке — отсортировать их. Это требует $O(|E|\log |E|)$ сравнения время с использованием алгоритма сортировки . Нам также необходимо протестировать каждый $x$ ли $A\cup \{x\}$ является независимым; предполагая, что тесты независимости требуют $O(f(|E|))$ время, общее время работы алгоритма $O(|E|\log |E|+|E|f(|E|))$.

Если вместо этого мы хотим найти минимальное остовное дерево, мы просто «инвертируем» весовую функцию, вычитая ее из большой константы. Точнее, пусть $w_{\text{min}}(x)=W-w(x)$, где $W$ превышает общий вес по всем ребрам графа. Этим тривиальным способом можно решить гораздо больше задач по оптимизации всех видов матроидов и весовых функций, хотя во многих случаях можно найти более эффективные алгоритмы, использующие более специализированные свойства.

Требование Матроида

Заметим также, что если мы возьмем набор $I$ «независимых» множеств, которые являются даун-множествами, но не матроидами, то жадный алгоритм не всегда будет работать. Ибо тогда существуют независимые множества $I_{1}$ и $I_{2}$ с $|I_{1}|<|I_{2}|$, но такой, что ни за что $e\in I_{2}\setminus I_{1}$ является $I_{1}\cup e$ независимый.

Выберите $\epsilon >0$ и $\tau >0$ такой, что $(1+2\epsilon )|I_{1}|+\tau |E|<|I_{2}|$. Взвесьте элементы $I_{1}\cup I_{2}$ в диапазоне $2$ к $2+2\epsilon$, элементы $I_{1}\setminus I_{2}$ в диапазоне $1+\epsilon$ к $1+2\epsilon$, элементы $I_{2}\setminus I_{1}$ в диапазоне $1$ к $1+\epsilon$, а остальное в диапазоне $0$ к $\tau$. Жадный алгоритм выберет элементы $I_{1}$, а затем не может выбрать ни одного элемента $I_{2}\setminus I_{1}$. Следовательно, построенное им независимое множество будет иметь вес не более $(1+2\epsilon )|I_{1}|+\tau |E|+|I_{1}\cup I_{2}|$, что меньше веса $I_{2}$.

Характеристика

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

Обобщения

Понятие матроида было обобщено, чтобы учесть другие типы множеств, на которых жадный алгоритм дает оптимальные решения; см. в разделе «Встраивание Greedoid и Maroid» дополнительную информацию . Корте и Ловас обобщили бы эти идеи на объекты, называемые жадными алгоритмами , которые позволяют решать еще более широкие классы задач с помощью жадных алгоритмов.