Итеративное сжатие: различия между версиями
[отпатрулированная версия] | [отпатрулированная версия] |
MoreVnu3 (обсуждение | вклад) оформление, стилевые правки, орфография, пунктуация, источники, дополнение, уточнение, исправление, обновление |
Liasmi (обсуждение | вклад) м оформление, проверка орф., пункт. |
||
Строка 1: | Строка 1: | ||
'''Итеративное сжатие''' |
'''Итеративное сжатие''' — это [[алгоритм]]ическая техника разработки {{не переведено 5|Параметрическая сложность|фиксированно-параметрически разрешимых алгоритмов||parameterized complexity}}. В данной технике на каждом шаге в [[Задача|задачу]] добавляется один элемент (такой как [[Вершина (теория графов)|вершина графа]]), а перед его добавлением находится небольшое решение задачи. |
||
== История== |
== История == |
||
Технику разработали Рид, Смит и Ветта{{sfn|Reed, Smith, Vetta|2004|с=299–301}}, чтобы показать, что {{не переведено 5|задача об удалении нечётных циклов|||odd cycle transversal}} разрешима за время <math>O(3^{k}kmn)</math> для графов |
Технику разработали Рид, Смит и Ветта{{sfn|Reed, Smith, Vetta|2004|с=299–301}}, чтобы показать, что {{не переведено 5|задача об удалении нечётных циклов|||odd cycle transversal}} разрешима за время <math>O(3^{k}kmn)</math> для графов с {{mvar|n}} вершинами, {{mvar|m}} рёбрами и числом удаляемых вершин {{mvar|k}}. Задача об удалении нечётных циклов — это задача поиска наименьшего набора вершин, который включает по меньшей мере по одной вершине из любого нечётного цикла. Параметрическая сложность этой задачи долгое время оставалась открытой{{sfn|Niedermeier|2006|с=184}}{{sfn|Cygan, Fomin, Kowalik и др.|2015|с=555}}. Позже эта техника стала очень полезна для доказательства результатов по {{не переведено 5|Параметрическая сложность|фиксированно-параметрической разрешимости||fixed-parameter tractable}}. Сейчас эту технику принято считать одной из фундаментальных в области параметризованных алгоритмов. |
||
Итеративное сжатие успешно использовалось во многих задачах, например для [[Двудольный граф|удаления нечётных циклов]] (см. ниже) и [[Двудольный граф|удаления рёбер для получения двудольности]], [[Разрезающее циклы множество вершин|нахождения разрезающих циклов вершин]], удаления кластерных вершин и нахождения разрезающих ориентированных циклов вершин{{sfn|Guo, Moser, Niedermeier|2009|с=65–80}}. Метод также успешно использовался для точных [[Временная сложность алгоритма#Экспоненциальное время|алгоритмов экспоненциального времени]] для нахождения [[Задача о независимом множестве|независимого множества]]{{sfn|Fomin, Gaspers, Kratsch и др.|2010|с=1045–1053}}. |
Итеративное сжатие успешно использовалось во многих задачах, например для [[Двудольный граф|удаления нечётных циклов]] (см. ниже) и [[Двудольный граф|удаления рёбер для получения двудольности]], [[Разрезающее циклы множество вершин|нахождения разрезающих циклов вершин]], удаления кластерных вершин и нахождения разрезающих ориентированных циклов вершин{{sfn|Guo, Moser, Niedermeier|2009|с=65–80}}. Метод также успешно использовался для точных [[Временная сложность алгоритма#Экспоненциальное время|алгоритмов экспоненциального времени]] для нахождения [[Задача о независимом множестве|независимого множества]]{{sfn|Fomin, Gaspers, Kratsch и др.|2010|с=1045–1053}}. |
||
==Техника== |
== Техника == |
||
Итеративное сжатие применимо, например, для параметризованных [[Теория графов|задач на графах]], входом которых является граф {{math|1=''G''=(''V'',''E'')}} и |
Итеративное сжатие применимо, например, для параметризованных [[Теория графов|задач на графах]], входом которых является граф {{math|1=''G''=(''V'',''E'')}} и [[натуральное число]] {{mvar|k}}, а задача ставится как проверка существования решения (набора вершин) размера <math>\leqslant k</math>. Предположим, что задача замкнута относительно [[Порождённый подграф|порождённых подграфов]] (если решение существует для <math>\leqslant k</math> для данного графа, то решение этого размера или меньшего существует для любого порождённого подграфа) и что существует эффективная процедура, которая определяет, может ли решение {{mvar|Y}} размера <math>k + 1</math> быть сжато до меньшего решения размера {{mvar|k}}. |
||
Если это предположение выполняется, то задача может быть решена путём добавления вершин по одной за раз и нахождения решения для порождённого подграфа следующим образом: |
Если это предположение выполняется, то задача может быть решена путём добавления вершин по одной за раз и нахождения решения для порождённого подграфа следующим образом: |
||
#Начинаем с подграфа, порождённого набором вершин {{mvar|S}} размера {{mvar|k}} и решения {{mvar|X}}, которое равно самому {{mvar|S}}. |
# Начинаем с подграфа, порождённого набором вершин {{mvar|S}} размера {{mvar|k}} и решения {{mvar|X}}, которое равно самому {{mvar|S}}. |
||
#Пока <math>S \ne V</math> осуществляем следующие шаги: |
# Пока <math>S \ne V</math> осуществляем следующие шаги: |
||
#*Пусть {{mvar|v}} будет любой вершиной <math>V \backslash S</math>, добавим {{mvar|v}} в {{mvar|S}} |
#* Пусть {{mvar|v}} будет любой вершиной <math>V \backslash S</math>, добавим {{mvar|v}} в {{mvar|S}} |
||
#*Проверяем, можно ли решение с {{math|(''k'' + 1)}} вершинами {{mvar|1=''Y''=''X'' ∪ {x}}} для {{mvar|S}} сжать до решения с {{mvar|k}} вершинами. |
#* Проверяем, можно ли решение с {{math|(''k'' + 1)}} вершинами {{mvar|1=''Y''=''X'' ∪ {x}}} для {{mvar|S}} сжать до решения с {{mvar|k}} вершинами. |
||
#*Если решение не может быть сжато, прерываем алгоритм |
#* Если решение не может быть сжато, прерываем алгоритм — входной граф не имеет решения с {{mvar|k}} вершинами. |
||
#*В противном случае, полагаем {{mvar|X}} новым сжатым решением и возвращаем к началу цикла. |
#* В противном случае, полагаем {{mvar|X}} новым сжатым решением и возвращаем к началу цикла. |
||
Этот алгоритм вызывает подпрограмму сжатия линейное число раз. Поэтому, если вариант сжимающей процедуры работает за фиксированно-параметрически разрешимое время, то есть |
Этот алгоритм вызывает подпрограмму сжатия линейное число раз. Поэтому, если вариант сжимающей процедуры работает за фиксированно-параметрически разрешимое время, то есть <math>f(k) \cdot n^c</math> для некоторой константы ''c,'' то процедура итеративного сжатия для решения полной задачи работает за время <math>f(k) \cdot n^{c+1}</math>. |
||
Ту же самую технику можно применять для нахождения множеств рёбер для свойств графов, замкнутых относительно подграфов (отличных от порождённого подграфа) или других свойств в теории графов. Когда значение параметра {{mvar|k}} неизвестно, оно может быть найдено с помощью внешнего уровня {{не переведено 5|Экспоненциальный поиск|экспоненциального поиска||exponential search}} или [[Линейный поиск|линейного поиска]] для оптимального выбора {{mvar|k}}, с поиском на каждом шаге, основываясь на том же алгоритме итеративного сжатия. |
Ту же самую технику можно применять для нахождения множеств рёбер для свойств графов, замкнутых относительно подграфов (отличных от порождённого подграфа) или других свойств в теории графов. Когда значение параметра {{mvar|k}} неизвестно, оно может быть найдено с помощью внешнего уровня {{не переведено 5|Экспоненциальный поиск|экспоненциального поиска||exponential search}} или [[Линейный поиск|линейного поиска]] для оптимального выбора {{mvar|k}}, с поиском на каждом шаге, основываясь на том же алгоритме итеративного сжатия. |
||
==Приложения== |
== Приложения == |
||
В оригинальной статье Рид, Смит и Ветта показали, как сделать граф двудольным путём удаления не более ''k'' вершин за время <math>O(3^kkmn)</math>. Позднее Локштанов, Саурабх и Сикдар дали более простой алгоритм, также использующий итеративное сжатие{{sfn|Lokshtanov, Saurabh, Sikdar|2009|с=380–384}}. |
В оригинальной статье Рид, Смит и Ветта показали, как сделать граф двудольным путём удаления не более ''k'' вершин за время <math>O(3^kkmn)</math>. Позднее Локштанов, Саурабх и Сикдар дали более простой алгоритм, также использующий итеративное сжатие{{sfn|Lokshtanov, Saurabh, Sikdar|2009|с=380–384}}. |
||
Чтобы сжать удаляемое множество {{mvar|Y}} размера {{math|''k'' + 1}} до множества {{mvar|X}} размера {{mvar|k}} их алгоритм проверяет все <math>3^{k+1}</math> разбиения множества {{mvar|Y}} на три подмножества |
Чтобы сжать удаляемое множество {{mvar|Y}} размера {{math|''k'' + 1}} до множества {{mvar|X}} размера {{mvar|k}} их алгоритм проверяет все <math>3^{k+1}</math> разбиения множества {{mvar|Y}} на три подмножества — подмножество множества {{mvar|Y}}, которое принадлежит новому удаляемому множеству, и два подмножества множества {{mvar|Y}}, которые принадлежат двум долям двудольного графа, остающегося после удаления множества {{mvar|X}}. Когда эти три множества выбраны, оставшиеся вершины удаляемого множества {{mvar|X}} (если таковое существует) могут быть найдены из них, применяя алгоритм [[Теорема Форда — Фалкерсона|Форда — Фалкерсона]]. |
||
[[Задача о вершинном покрытии|Вершинное покрытие]] |
[[Задача о вершинном покрытии|Вершинное покрытие]] — это другой пример, для которого может быть применено итеративное сжатие. В задаче вершинного покрытия в качестве входных данных даётся граф <math>G=(V, E)</math> и натуральное число {{mvar|k}}, а алгоритм должен решить, существует ли множество {{mvar|X}} с {{mvar|k}} вершинами, такое что любое ребро инцидентно вершине в {{mvar|X}}. В варианте сжатия входом является множество {{mvar|Y}} с <math>k + 1</math> вершинами, которое инцидентно всем рёбрам графа, и алгоритм должен найти множество {{mvar|X}} размера {{mvar|k}} с тем же свойством, если таковое существует. Один из способов сделать это — тестируются все <math>2^{k + 1}</math> варианта, какими множество {{mvar|Y}} удаляется из покрытия и вставляется обратно в граф. Такой перебор может работать только если никакие две удаляемые вершины не смежны и для каждого такого варианта подпрограмма должна включать в покрытие все вершины вне {{mvar|Y}} инцидентные ребру, которое становится непокрытым при этом удалении. Использование такой подпрограммы в алгоритме итеративного сжатия даёт простой алгоритм со временем работы <math>O(2^k n^2)</math> для покрытия вершин. |
||
==См. также== |
== См. также == |
||
* [[Параметрическая редукция]], другая техника для фиксированно-параметрически разрешимых алгоритмов |
* [[Параметрическая редукция]], другая техника для фиксированно-параметрически разрешимых алгоритмов |
||
==Примечания== |
== Примечания == |
||
{{примечания |
{{примечания}} |
||
==Литература== |
== Литература == |
||
{{refbegin|colwidth=30em}} |
|||
*{{статья |
* {{статья |
||
|автор=Bruce Reed, Kaleigh Smith, Adrian Vetta |
|автор=Bruce Reed, Kaleigh Smith, Adrian Vetta |
||
|ref=Reed, Smith, Vetta |
|ref=Reed, Smith, Vetta |
||
Строка 44: | Строка 44: | ||
|год=2004 |
|год=2004 |
||
}} |
}} |
||
*{{книга |
* {{книга |
||
|автор=Rolf Niedermeier |
|автор=Rolf Niedermeier |
||
|ref=Niedermeier |
|ref=Niedermeier |
||
Строка 54: | Строка 54: | ||
|isbn=9780198566076 |
|isbn=9780198566076 |
||
}} |
}} |
||
*{{книга |
* {{книга |
||
|автор=Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh |
|автор=Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh |
||
|ref=Cygan, Fomin, Kowalik и др. |
|ref=Cygan, Fomin, Kowalik и др. |
||
Строка 62: | Строка 62: | ||
|isbn=978-3-319-21274-6 |
|isbn=978-3-319-21274-6 |
||
}} |
}} |
||
*{{книга |
* {{книга |
||
|автор=Jiong Guo, Hannes Moser, Rolf Niedermeier |
|автор=Jiong Guo, Hannes Moser, Rolf Niedermeier |
||
|ref=Guo, Moser, Niedermeier |
|ref=Guo, Moser, Niedermeier |
||
Строка 75: | Строка 75: | ||
|isbn=978-3-642-02093-3 |
|isbn=978-3-642-02093-3 |
||
}} |
}} |
||
*{{статья |
* {{статья |
||
|автор=Fedor Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Saket Saurabh |
|автор=Fedor Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Saket Saurabh |
||
|ref=Fomin, Gaspers, Kratsch и др. |
|ref=Fomin, Gaspers, Kratsch и др. |
||
|doi=10.1016/j.tcs.2009.11.012 |
|doi=10.1016/j.tcs.2009.11.012 |
||
|выпуск=7 |
|выпуск=7 |
||
|издание= |
|издание=Theoretical Computer Science |
||
|страницы=1045–1053 |
|страницы=1045–1053 |
||
|заглавие=Iterative compression and exact algorithms |
|заглавие=Iterative compression and exact algorithms |
||
Строка 86: | Строка 86: | ||
|год=2010 |
|год=2010 |
||
}} |
}} |
||
*{{книга |
* {{книга |
||
|автор=Daniel Lokshtanov, Saket Saurabh, Somnath Sikdar |
|автор=Daniel Lokshtanov, Saket Saurabh, Somnath Sikdar |
||
|ref=Lokshtanov, Saurabh, Sikdar |
|ref=Lokshtanov, Saurabh, Sikdar |
||
Строка 93: | Строка 93: | ||
|страницы=380–384 |
|страницы=380–384 |
||
|часть=Simpler parameterized algorithm for OCT |
|часть=Simpler parameterized algorithm for OCT |
||
| |
|серия=Lecture Notes in Computer Science |
||
|издательство=Springer |
|издательство=Springer |
||
|том=5874 |
|том=5874 |
||
Строка 99: | Строка 99: | ||
|isbn=978-3-642-10216-5 |
|isbn=978-3-642-10216-5 |
||
}} |
}} |
||
{{refend}} |
|||
[[Категория:Алгоритмы на графах]] |
[[Категория:Алгоритмы на графах]] |
||
[[Категория:Параметрическая сложность]] |
[[Категория:Параметрическая сложность]] |
||
[[Категория:Анализ алгоритмов]] |
[[Категория:Анализ алгоритмов]] |
||
{{rq|checktranslate|style |
{{rq|checktranslate|style}} |
Текущая версия от 07:03, 13 февраля 2021
Итеративное сжатие — это алгоритмическая техника разработки фиксированно-параметрически разрешимых алгоритмов[англ.]. В данной технике на каждом шаге в задачу добавляется один элемент (такой как вершина графа), а перед его добавлением находится небольшое решение задачи.
История
[править | править код]Технику разработали Рид, Смит и Ветта[1], чтобы показать, что задача об удалении нечётных циклов[англ.] разрешима за время для графов с n вершинами, m рёбрами и числом удаляемых вершин k. Задача об удалении нечётных циклов — это задача поиска наименьшего набора вершин, который включает по меньшей мере по одной вершине из любого нечётного цикла. Параметрическая сложность этой задачи долгое время оставалась открытой[2][3]. Позже эта техника стала очень полезна для доказательства результатов по фиксированно-параметрической разрешимости[англ.]. Сейчас эту технику принято считать одной из фундаментальных в области параметризованных алгоритмов.
Итеративное сжатие успешно использовалось во многих задачах, например для удаления нечётных циклов (см. ниже) и удаления рёбер для получения двудольности, нахождения разрезающих циклов вершин, удаления кластерных вершин и нахождения разрезающих ориентированных циклов вершин[4]. Метод также успешно использовался для точных алгоритмов экспоненциального времени для нахождения независимого множества[5].
Техника
[править | править код]Итеративное сжатие применимо, например, для параметризованных задач на графах, входом которых является граф G=(V,E) и натуральное число k, а задача ставится как проверка существования решения (набора вершин) размера . Предположим, что задача замкнута относительно порождённых подграфов (если решение существует для для данного графа, то решение этого размера или меньшего существует для любого порождённого подграфа) и что существует эффективная процедура, которая определяет, может ли решение Y размера быть сжато до меньшего решения размера k.
Если это предположение выполняется, то задача может быть решена путём добавления вершин по одной за раз и нахождения решения для порождённого подграфа следующим образом:
- Начинаем с подграфа, порождённого набором вершин S размера k и решения X, которое равно самому S.
- Пока осуществляем следующие шаги:
- Пусть v будет любой вершиной , добавим v в S
- Проверяем, можно ли решение с (k + 1) вершинами Y=X ∪ {x} для S сжать до решения с k вершинами.
- Если решение не может быть сжато, прерываем алгоритм — входной граф не имеет решения с k вершинами.
- В противном случае, полагаем X новым сжатым решением и возвращаем к началу цикла.
Этот алгоритм вызывает подпрограмму сжатия линейное число раз. Поэтому, если вариант сжимающей процедуры работает за фиксированно-параметрически разрешимое время, то есть для некоторой константы c, то процедура итеративного сжатия для решения полной задачи работает за время . Ту же самую технику можно применять для нахождения множеств рёбер для свойств графов, замкнутых относительно подграфов (отличных от порождённого подграфа) или других свойств в теории графов. Когда значение параметра k неизвестно, оно может быть найдено с помощью внешнего уровня экспоненциального поиска[англ.] или линейного поиска для оптимального выбора k, с поиском на каждом шаге, основываясь на том же алгоритме итеративного сжатия.
Приложения
[править | править код]В оригинальной статье Рид, Смит и Ветта показали, как сделать граф двудольным путём удаления не более k вершин за время . Позднее Локштанов, Саурабх и Сикдар дали более простой алгоритм, также использующий итеративное сжатие[6]. Чтобы сжать удаляемое множество Y размера k + 1 до множества X размера k их алгоритм проверяет все разбиения множества Y на три подмножества — подмножество множества Y, которое принадлежит новому удаляемому множеству, и два подмножества множества Y, которые принадлежат двум долям двудольного графа, остающегося после удаления множества X. Когда эти три множества выбраны, оставшиеся вершины удаляемого множества X (если таковое существует) могут быть найдены из них, применяя алгоритм Форда — Фалкерсона.
Вершинное покрытие — это другой пример, для которого может быть применено итеративное сжатие. В задаче вершинного покрытия в качестве входных данных даётся граф и натуральное число k, а алгоритм должен решить, существует ли множество X с k вершинами, такое что любое ребро инцидентно вершине в X. В варианте сжатия входом является множество Y с вершинами, которое инцидентно всем рёбрам графа, и алгоритм должен найти множество X размера k с тем же свойством, если таковое существует. Один из способов сделать это — тестируются все варианта, какими множество Y удаляется из покрытия и вставляется обратно в граф. Такой перебор может работать только если никакие две удаляемые вершины не смежны и для каждого такого варианта подпрограмма должна включать в покрытие все вершины вне Y инцидентные ребру, которое становится непокрытым при этом удалении. Использование такой подпрограммы в алгоритме итеративного сжатия даёт простой алгоритм со временем работы для покрытия вершин.
См. также
[править | править код]- Параметрическая редукция, другая техника для фиксированно-параметрически разрешимых алгоритмов
Примечания
[править | править код]- ↑ Reed, Smith, Vetta, 2004, с. 299–301.
- ↑ Niedermeier, 2006, с. 184.
- ↑ Cygan, Fomin, Kowalik и др., 2015, с. 555.
- ↑ Guo, Moser, Niedermeier, 2009, с. 65–80.
- ↑ Fomin, Gaspers, Kratsch и др., 2010, с. 1045–1053.
- ↑ Lokshtanov, Saurabh, Sikdar, 2009, с. 380–384.
Литература
[править | править код]- Bruce Reed, Kaleigh Smith, Adrian Vetta. Finding odd cycle transversals // Operations Research Letters. — 2004. — Т. 32, вып. 4. — doi:10.1016/j.orl.2003.10.009.
- Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms. — Oxford University Press, 2006. — Т. 31. — (Oxford lecture series in mathematics and its applications). — ISBN 9780198566076.
- Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh. Parameterized Algorithms. — Springer, 2015. — ISBN 978-3-319-21274-6.
- Jiong Guo, Hannes Moser, Rolf Niedermeier. Iterative compression for exactly solving NP-hard minimization problems // Algorithmics of Large and Complex Networks. — Springer, 2009. — Т. 5515. — С. 65–80. — (Lecture Notes in Computer Science). — ISBN 978-3-642-02093-3. — doi:10.1007/978-3-642-02094-0_4.
- Fedor Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Saket Saurabh. Iterative compression and exact algorithms // Theoretical Computer Science. — 2010. — Т. 411, вып. 7. — С. 1045–1053. — doi:10.1016/j.tcs.2009.11.012.
- Daniel Lokshtanov, Saket Saurabh, Somnath Sikdar. Simpler parameterized algorithm for OCT // 20th International Workshop on Combinatorial Algorithms, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28–July 2, 2009, Revised Selected Papers. — Springer, 2009. — Т. 5874. — С. 380–384. — (Lecture Notes in Computer Science). — ISBN 978-3-642-10216-5. — doi:10.1007/978-3-642-10217-2_37.
Для улучшения этой статьи желательно:
|