Итеративное сжатие: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Добавлены ссылки на другие статьи Вики
оформление, стилевые правки, орфография, пунктуация, источники, дополнение, уточнение, исправление, обновление
Строка 1: Строка 1:
'''Итеративное сжатие''' — это [[алгоритм]]ическая техника разработки {{не переведено 5|Параметрическая сложность|фиксированно-параметрически разрешимых алгоритмов||parameterized complexity}}, в которой один элемент (такой как [[Вершина (теория графов)|вершина графа]]) добавляется в [[Задача|задачу]] на каждом шаге и используется небольшое решение задачи перед добавлением элемента, чтобы найти небольшое решение задачи после добавления.
'''Итеративное сжатие''' — это [[алгоритм]]ическая техника разработки {{не переведено 5|Параметрическая сложность|фиксированно-параметрически разрешимых алгоритмов||parameterized complexity}}. В данной технике на каждом шаге в [[Задача|задачу]] добавляется один элемент (такой как [[Вершина (теория графов)|вершина графа]]), а перед его добавлением находится небольшое решение задачи.

== История==
== История==
Технику разработали Рид, Смит и Ветта{{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|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}}.


==Техника==
==Техника==
Строка 12: Строка 13:
#Пока <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'' &cup; {x}}} для {{mvar|S}} сжатm до решения с {{mvar|k}} вершинами.
#*Проверяем, можно ли решение с {{math|(''k'' + 1)}} вершинами {{mvar|1=''Y''=''X'' &cup; {x}}} для {{mvar|S}} сжать до решения с {{mvar|k}} вершинами.
#*Если решение не может быть сжато, прерываем алгоритм — входной граф не имеет решения с {{mvar|k}} вершинами.
#*Если решение не может быть сжато, прерываем алгоритм — входной граф не имеет решения с {{mvar|k}} вершинами.
#*В противном случае, полагаем {{mvar|X}} новым сжатым решением и возвращаем к началу цикла.
#*В противном случае, полагаем {{mvar|X}} новым сжатым решением и возвращаем к началу цикла.


Этот алгоритм вызывает подпрограмму сжатия линейное число раз. Поэтому, если вариант сжимающей процедуры работает за фиксированно-параметрически разрешимое время, то есть, <math>f(k) \cdot n^c</math> для некоторой константы ''c'', тогда процедура итеративного сжатия для решения полной задачи работает за время <math>f(k) \cdot n^{c+1}</math>.
Этот алгоритм вызывает подпрограмму сжатия линейное число раз. Поэтому, если вариант сжимающей процедуры работает за фиксированно-параметрически разрешимое время, то есть, <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}}, с поиском на каждом шаге, основываясь на том же алгоритме итеративного сжатия.


Строка 23: Строка 24:
Чтобы сжать удаляемое множество {{mvar|Y}} размера {{math|''k'' + 1}} до множества {{mvar|X}} размера {{mvar|k}} их алгоритм проверяет все <math>3^{k+1}</math> разбиения множества {{mvar|Y}} на три подмножества — подмножество множества {{mvar|Y}}, которое принадлежит новому удаляемому множеству, и два подмножества множества {{mvar|Y}}, которые принадлежат двум долям двудольного графа, остающегося после удаления множества {{mvar|X}}. Когда эти три множества выбраны, оставшиеся вершины удаляемого множества {{mvar|X}} (если таковое существует) могут быть найдены из них, применяя алгоритм [[Теорема Форда — Фалкерсона|Форда — Фалкерсона]].
Чтобы сжать удаляемое множество {{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> для покрытия вершин.
[[Задача о вершинном покрытии|Вершинное покрытие]] — это другой пример, для которого может быть применено итеративное сжатие. В задаче вершинного покрытия в качестве входных данных даётся граф <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> для покрытия вершин.


==См. также==
==См. также==

Версия от 12:48, 19 января 2021

Итеративное сжатие — это алгоритмическая техника разработки фиксированно-параметрически разрешимых алгоритмов[англ.]. В данной технике на каждом шаге в задачу добавляется один элемент (такой как вершина графа), а перед его добавлением находится небольшое решение задачи.

История

Технику разработали Рид, Смит и Ветта[1], чтобы показать, что задача об удалении нечётных циклов[англ.] разрешима за время для графов с n вершинами, m рёбрами и числом удаляемых вершин k. Задача об удалении нечётных циклов — это задача поиска наименьшего набора вершин, который включает по меньшей мере по одной вершине из любого нечётного цикла. Параметрическая сложность этой задачи долгое время оставалась открытой[2][3]. Позже, эта техника стала очень полезна для доказательства результатов по фиксированно-параметрической разрешимости[англ.]. Сейчас эту технику принято считать одной из фундаментальных в области параметризованных алгоритмов.

Итеративное сжатие успешно использовалось во многих задачах, например для удаления нечётных циклов (см. ниже) и удаления рёбер для получения двудольности, нахождения разрезающих циклов вершин, удаления кластерных вершин и нахождения разрезающих ориентированных циклов вершин[4]. Метод также успешно использовался для точных алгоритмов экспоненциального времени для нахождения независимого множества[5].

Техника

Итеративное сжатие применимо, например, для параметризованных задач на графах, входом которых является граф G=(V,E) и натуральное число k, а задача ставится как проверка существования решения (набора вершин) размера . Предположим, что задача замкнута относительно порождённых подграфов (если решение существует для для данного графа, то решение этого размера или меньшего существует для любого порождённого подграфа) и что существует эффективная процедура, которая определяет, может ли решение Y размера быть сжато до меньшего решения размера k.

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

  1. Начинаем с подграфа, порождённого набором вершин S размера k и решения X, которое равно самому S.
  2. Пока осуществляем следующие шаги:
    • Пусть 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 инцидентные ребру, которое становится непокрытым при этом удалении. Использование такой подпрограммы в алгоритме итеративного сжатия даёт простой алгоритм со временем работы для покрытия вершин.

См. также

Примечания

  1. ↑ Reed, Smith, Vetta, 2004, с. 299–301.
  2. ↑ Niedermeier, 2006, с. 184.
  3. ↑ Cygan, Fomin, Kowalik и др., 2015, с. 555.
  4. ↑ Guo, Moser, Niedermeier, 2009, с. 65–80.
  5. ↑ Fomin, Gaspers, Kratsch и др., 2010, с. 1045–1053.
  6. ↑ 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. — ISBN 978-3-642-10216-5. — doi:10.1007/978-3-642-10217-2_37.
Источник — https://ru.wikipedia.org/ruwiki/w/index.php?title=Итеративное_сжатие&oldid=111825953