|
|
| Строка 1: |
Строка 1: |
| При разработке [[алгоритм]]ов '''уточнение разбиения''' — это метод представления [[Разбиение множества|разбиения множества]] в виде [[Структура данных|структуры данных,]] которая позволяет разбивать его множества на большее количество меньших множеств. В этом смысле уточнение разбиения двойственно [[Система непересекающихся множеств|системе непересекающихся множеств]], которая также поддерживает разбиение на [[Непересекающиеся множества|непересекающиеся множества,]] но в которой операции объединяют пары наборов. В некоторых приложениях уточнения разбиения, таких как [[лексикографический поиск в ширину]], структура данных поддерживает также порядок наборов в разделе. | | При разработке [[алгоритм]]ов '''уточнение разбиения''' — это метод представления [[Разбиение множества|разбиения множества]] в виде [[Структура данных|структуры данных,]] которая позволяет разбивать его множества на большее количество меньших множеств. В этом смысле уточнение разбиения двойственно [[Система непересекающихся множеств|системе непересекающихся множеств]], которая также поддерживает разбиение на [[Непересекающиеся множества|непересекающиеся множества,]] но в которой операции объединяют пары наборов. В некоторых приложениях уточнения разбиения, таких как [[лексикографический поиск в ширину]], структура данных поддерживает также порядок наборов в разделе. |
|
| |
|
| Уточнение разбиения является ключевым компонентом нескольких эффективных алгоритмов на [[Теория графов|графах]] и [[Конечный автомат|конечных автоматах]], включая [[Минимизация ДКА|минимизацию ДКА]], [[алгоритм Коффмана – Грэма]] для параллельного планирования и [[лексикографический поиск в ширину]].<ref>{{Citation|last1=Paige|first1=Robert|last2=Tarjan|first2=Robert E.|author2-link=Robert Tarjan|doi=10.1137/0216062|issue=6|journal=[[SIAM Journal on Computing]]|pages=973–989|title=Three partition refinement algorithms|volume=16|year=1987}}.</ref><ref>{{Citation|last1=Habib|first1=Michel|last2=Paul|first2=Christophe|doi=10.1142/S0129054199000125|issue=2|journal=[[International Journal of Foundations of Computer Science]]|pages=147–170|title=Partition refinement techniques: an interesting algorithmic tool kit|volume=10|year=1999}}.</ref><ref>{{Citation|last1=Habib|first1=Michel|last2=Paul|first2=Christophe|doi=10.1007/BFb0028546|pages=25–38|title=STACS 98: 15th Annual Symposium on Theoretical Aspects of Computer Science Paris, France, February 25–27, 1998, Proceedings|volume=1373|year=1998}}.</ref>
| |
|
| |
| == Структура данных ==
| |
| Алгоритм уточнения разбиения поддерживает семейство непересекающихся множеств {{Math|''S''<sub>''i''</sub>}} . В начале алгоритма это семейство содержит единственное множество всех элементов в структуре данных. На каждом шаге алгоритм получает множество {{Mvar|X}}, и каждое множество {{Math|''S''<sub>''i''</sub>}} в семействе, содержащем элементы {{Mvar|X}}, разбивается на два множества: [[Пересечение множеств|пересечение]] {{Math|''S''<sub>''i''</sub> ∩ ''X''}} и [[Разность множеств|разность]] {{Math|''S''<sub>''i''</sub> \ ''X''}}
| |
|
| |
| Этот алгоритм может быть эффективно реализован с помощью [[Структура данных|структур данных,]] представляющих следующую информацию:<ref>{{Citation|first1=Antti|volume=1|url=http://drops.dagstuhl.de/opus/volltexte/2008/1328|location=Dagstuhl, Germany|publisher=Schloss Dagstuhl: Leibniz-Zentrum fuer Informatik|editor2-last=Weil|editor2-first=Pascal|editor1-link=Susanne Albers|editor1-last=Albers|editor1-first=Susanne|year=2008|last1=Valmari|isbn=978-3-939897-06-4|series=Leibniz International Proceedings in Informatics (LIPIcs)|pages=645–656|title=25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008)|journal=<!-- WORK AROUND CITATION BOT BUG. THIS IS NOT A JOURNAL PAPER. PLEASE DO NOT ADD A JOURNAL HERE. -->|chapter=Efficient minimization of DFAs with partial transition functions|last2=Lehtinen|first2=Petri|doi=10.4230/LIPIcs.STACS.2008.1328}} {{Wayback|url=http://drops.dagstuhl.de/opus/volltexte/2008/1328 |date=20210718160752 }}</ref><ref>{{Citation|last1=Knuutila|first1=Timo|doi=10.1016/S0304-3975(99)00150-4|title=Re-describing an algorithm by Hopcroft|journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]|volume=250|year=2001|pages=333–363}}</ref>
| |
|
| |
|
| * Упорядоченная последовательность множеств {{Math|''S''<sub>''i''</sub>}} в семействе в такой форме, как [[Связный список#Двусвязный список (двунаправленный связный список)|двусвязный список]], который позволяет вставлять новые наборы в середину последовательности. | | * Упорядоченная последовательность множеств {{Math|''S''<sub>''i''</sub>}} в семействе в такой форме, как [[Связный список#Двусвязный список (двунаправленный связный список)|двусвязный список]], который позволяет вставлять новые наборы в середину последовательности. |
| Строка 12: |
Строка 6: |
| * С каждым элементом связан набор, к которому он принадлежит. | | * С каждым элементом связан набор, к которому он принадлежит. |
|
| |
|
| Чтобы выполнить операцию уточнения, алгоритм перебирает элементы данного множества {{Mvar|X}}. Для каждого такого элемента {{Mvar|x}} он находит множество {{Math|''S''<sub>''i''</sub>}} которое содержит {{Mvar|x}}, и проверяет, произведено ли пересечение {{Math|''S''<sub>''i''</sub> ∩ ''X''}}. Если нет, он создает второе множество и добавляет {{Math|''S''<sub>''i''</sub>}} в список {{Mvar|L}} множеств, разделенных операцией. Затем, независимо от того, было ли сформировано новое множество, алгоритм удаляет {{Mvar|x}} из {{Math|''S''<sub>''i''</sub>}} и добавляет его к {{Math|''S''<sub>''i''</sub> ∩ ''X''}} В представлении, в котором все элементы хранятся в одном массиве, перемещение {{Mvar|x}} из одного множества в другое может выполняться путем обмена {{Mvar|x}} местами c последним элементом {{Math|''S''<sub>''i''</sub>}} а затем уменьшения концевого индекса {{Math|''S''<sub>''i''</sub>}} и начального индекса нового множества. Наконец, после того, как все элементы {{Mvar|X}} были обработаны таким образом, алгоритм проходит через {{Mvar|L}}, разделяя каждое текущее множество {{Math|''S''<sub>''i''</sub>}} на два, рассматривая оба этих множества как сформированные в результате операции уточнения.
| | Уточнение разбиения также является ключевым этапом в [[Лексикографический поиск в ширину|лексикографическом поиске]] |
| | |
| Оценка времени для выполнения одной операции уточнения таким образом составляет {{Math|''O''({{pipe}}''X''{{pipe}})}}, независимо от количества элементов в семействе множеств, а также независимо от общего количества множеств в структуре данных. Поэтому время исполнения последовательности уточнений пропорционально общему размеру множеств, заданных алгоритму на каждом этапе уточнения.
| |
| | |
| == Применение ==
| |
| Одно из первых применений уточнение разбиения нашло в алгоритме Хопкрофта для [[Минимизация ДКА|минимизации ДКА]]<ref name=":0" />. В этой задаче на входе задается [[детерминированный конечный автомат]], и он должен найти эквивалентный автомат с как можно меньшим количеством состояний. Алгоритм Хопкрофта поддерживает разделение состояний входного автомата на подмножества с тем свойством, что любые два состояния в разных подмножествах должны отображаться в разные состояния выходного автомата. Изначально существует два подмножества, одно из которых содержит все принимающие состояния автомата, а другое — остальные. На каждом шаге выбираются одно подмножество {{Math|''S<sub>i</sub>''}} и один из входных символов {{Mvar|x}} автомата, и подмножества состояний уточняются до состояний, для которых переход, помеченный {{Mvar|x}}, приведет в {{Math|''S<sub>i</sub>''}}, и состояний, для которых {{Mvar|x}} приведет в другое место. Когда выбранное множество {{Math|''S<sub>i</sub>''}} разделяется уточнением, только одно из двух результирующих множеств (меньшее из двух) нужно рассмотреть снова; таким образом, каждое состояние участвует в множествах {{Mvar|X}} в течение {{Math|''O''(''s'' log ''n'')}} шагов уточнения, а общая оценка времени алгоритма составляет {{Math|''O''(''ns'' log ''n'')}}, где {{Mvar|n}} — количество начальных состояний, а {{Mvar|s}} — размер алфавита.<ref name=":0">{{Citation|last=Hopcroft|first=John|author-link=John Hopcroft|contribution=An {{math|''n'' log ''n''}} algorithm for minimizing states in a finite automaton|location=New York|pages=189–196|publisher=Academic Press|title=Theory of machines and computations (Proc. Internat. Sympos., Technion, Haifa, 1971)|year=1971}}.</ref>
| |
| | |
| Уточнение разделения было применено Sethi<ref>{{Статья|ссылка=http://epubs.siam.org/doi/10.1137/0205005|автор=Ravi Sethi|заглавие=Scheduling Graphs on Two Processors|год=1976-03|язык=en|издание=SIAM Journal on Computing|том=5|выпуск=1|страницы=73–82|issn=0097-5397, 1095-7111|doi=10.1137/0205005|archivedate=2021-11-04|archiveurl=https://web.archive.org/web/20211104003751/https://epubs.siam.org/doi/10.1137/0205005}}</ref> в эффективной реализации [[Алгоритм Коффмана – Грэма|алгоритма Коффмана — Грэма]] для параллельного планирования. Сетхи показал, что его можно использовать для построения [[Лексикографический порядок|лексикографически упорядоченной]] [[Топологическая сортировка|топологической сортировки]] заданного [[Ориентированный ациклический граф|ориентированного ациклического графа]] за линейное время; такое лексикографическое топологическое упорядочение является одним из ключевых шагов алгоритма Коффмана — Грэма. В этом приложении элементы непересекающихся множеств являются вершинами входного графа, а множества {{Mvar|X}} используемые для уточнения разбиения, являются множествами соседей вершин. Поскольку общее количество соседей всех вершин — это просто количество ребер в графе, алгоритм требует времени, линейного по количеству ребер.
| |
| | |
| Уточнение разбиения также является ключевым этапом в [[Лексикографический поиск в ширину|лексикографическом поиске]] в ширину, алгоритме поиска по графу с приложениями для распознавания [[Хордальный граф|хордовых графов]] и некоторых других важных классов графов. В этих случаях элементы непересекающихся множеств являются вершинами, а множество {{Mvar|X}} представляет собой [[Окрестность (теория графов)|множества точек окрестности]], поэтому алгоритм занимает линейное время.<ref>{{Citation|first1=D. J.|last1=Rose|first2=R. E.|last2=Tarjan|author2-link=Robert Tarjan|first3=G. S.|last3=Lueker|year=1976|title=Algorithmic aspects of vertex elimination on graphs|journal=[[SIAM Journal on Computing]]|volume=5|pages=266–283|issue=2|doi=10.1137/0205021}}.</ref><ref>{{Citation|first1=Derek G.|last1=Corneil|title=Graph-Theoretic Methods in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers|volume=3353|year=2004|pages=1–19|doi=10.1007/978-3-540-30559-0_1}}.</ref> | |
| | |
| == См. также ==
| |
| * [[Сигма-алгебра|Уточнение (сигма-алгебра)]]
| |
| | |
| == Примечания ==
| |
| {{примечания}}
| |
| | |
| == Литература ==
| |
|
| |
| [[Категория:Структуры данных]] | | [[Категория:Структуры данных]] |
