Жадный алгоритм поиска базы минимального веса — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 12: Строка 12:
 
     <tex>B \leftarrow B \cup ArgOf(X[i])</tex>
 
     <tex>B \leftarrow B \cup ArgOf(X[i])</tex>
 
Рассмотрим шаг алгоритма, когда мы пытаемся добавить элемент <tex>ArgOf(X[i])</tex>. Заметим, что если его можно добавить с сохранением независимости множества <tex>B</tex>, то это элемент минимального веса не из <tex>B</tex>, который можно добавить (при условии сохранения независимости <tex>B</tex> при добавлении). В самом деле, пусть <tex>ArgOf(X[j])</tex> — элемент минимального веса, который можно добавить к <tex>B</tex> с сохранением его независимости, тогда <tex>j<i</tex>. Но тогда он уже был бы добавлен на <tex>j</tex>-ом шаге алгоритма.
 
Рассмотрим шаг алгоритма, когда мы пытаемся добавить элемент <tex>ArgOf(X[i])</tex>. Заметим, что если его можно добавить с сохранением независимости множества <tex>B</tex>, то это элемент минимального веса не из <tex>B</tex>, который можно добавить (при условии сохранения независимости <tex>B</tex> при добавлении). В самом деле, пусть <tex>ArgOf(X[j])</tex> — элемент минимального веса, который можно добавить к <tex>B</tex> с сохранением его независимости, тогда <tex>j<i</tex>. Но тогда он уже был бы добавлен на <tex>j</tex>-ом шаге алгоритма.
 +
 
Понятно, что все базы имеют одинаковую мощность (иначе в меньшую можно было бы добавить элемент из большей по аксиоме матроидов, что противоречит определению базы). По [[Теорема Радо-Эдмондса (жадный алгоритм)|теореме Радо-Эдмондса]] множество минимального веса, имеющее мощность базы, (то есть база минимального веса) ищется последовательным добавлением в изначально пустое множество элементов минимального веса из <tex>X</tex> так, чтобы после каждого добавления множество оставалось независимым.
 
Понятно, что все базы имеют одинаковую мощность (иначе в меньшую можно было бы добавить элемент из большей по аксиоме матроидов, что противоречит определению базы). По [[Теорема Радо-Эдмондса (жадный алгоритм)|теореме Радо-Эдмондса]] множество минимального веса, имеющее мощность базы, (то есть база минимального веса) ищется последовательным добавлением в изначально пустое множество элементов минимального веса из <tex>X</tex> так, чтобы после каждого добавления множество оставалось независимым.
 +
 
Алгоритм работает за <tex>O(\mid X \mid log(\mid X \mid))</tex>: <tex>O(\mid X \mid log(\mid X \mid))</tex> — на сортировку массива весов элементов <tex>X</tex> и <tex>O(\mid X \mid)<tex> шагов цикла, каждый из которых работает <tex>O(1)</tex> времени (если считать, что проверка множества на независимость происходит за <tex>O(1)</tex>).
 
Алгоритм работает за <tex>O(\mid X \mid log(\mid X \mid))</tex>: <tex>O(\mid X \mid log(\mid X \mid))</tex> — на сортировку массива весов элементов <tex>X</tex> и <tex>O(\mid X \mid)<tex> шагов цикла, каждый из которых работает <tex>O(1)</tex> времени (если считать, что проверка множества на независимость происходит за <tex>O(1)</tex>).
 
}}
 
}}

Версия 21:56, 17 мая 2011

Теорема (жадный алгоритм поиска базы минимального веса):
Пусть на носителе матроида [math]M = \langle X, I \rangle[/math] задана весовая функция [math]\omega: X \to \mathbb R[/math]. Для любого [math]A \subset X[/math] выполнено: [math]\omega(A) = \sum\limits _{x \in A} \omega(x)[/math]. Тогда база минимального веса матроида [math]M[/math] ищется жадно.
Доказательство:
[math]\triangleright[/math]

Псевдокод алгоритма:

[math]sort(X)[/math]    // сортируем элементы по возрастанию веса
[math]B \leftarrow \emptyset[/math]
for [math]i \leftarrow 0[/math] to [math]\mid X \mid[/math] do
  if [math]B \cup ArgOf(X[i]) \in I[/math]
    [math]B \leftarrow B \cup ArgOf(X[i])[/math]

Рассмотрим шаг алгоритма, когда мы пытаемся добавить элемент [math]ArgOf(X[i])[/math]. Заметим, что если его можно добавить с сохранением независимости множества [math]B[/math], то это элемент минимального веса не из [math]B[/math], который можно добавить (при условии сохранения независимости [math]B[/math] при добавлении). В самом деле, пусть [math]ArgOf(X[j])[/math] — элемент минимального веса, который можно добавить к [math]B[/math] с сохранением его независимости, тогда [math]j\lt i[/math]. Но тогда он уже был бы добавлен на [math]j[/math]-ом шаге алгоритма.

Понятно, что все базы имеют одинаковую мощность (иначе в меньшую можно было бы добавить элемент из большей по аксиоме матроидов, что противоречит определению базы). По теореме Радо-Эдмондса множество минимального веса, имеющее мощность базы, (то есть база минимального веса) ищется последовательным добавлением в изначально пустое множество элементов минимального веса из [math]X[/math] так, чтобы после каждого добавления множество оставалось независимым.

Алгоритм работает за [math]O(\mid X \mid log(\mid X \mid))[/math]: [math]O(\mid X \mid log(\mid X \mid))[/math] — на сортировку массива весов элементов [math]X[/math] и [math]O(\mid X \mid)\lt tex\gt шагов цикла, каждый из которых работает \lt tex\gt O(1)[/math] времени (если считать, что проверка множества на независимость происходит за [math]O(1)[/math]).
[math]\triangleleft[/math]