|
Уточнение разбиенияПри разработке алгоритмов уточнение разбиения — это метод представления разбиения множества в виде структуры данных, которая позволяет разбивать его множества на большее количество меньших множеств. В этом смысле уточнение разбиения двойственно системе непересекающихся множеств, которая также поддерживает разбиение на непересекающиеся множества, но в которой операции объединяют пары наборов. В некоторых приложениях уточнения разбиения, таких как лексикографический поиск в ширину, структура данных поддерживает также порядок наборов в разделе. Уточнение разбиения является ключевым компонентом нескольких эффективных алгоритмов на графах и конечных автоматах, включая минимизацию ДКА, алгоритм Коффмана – Грэма для параллельного планирования и лексикографический поиск в ширину.[1][2][3] Структура данныхАлгоритм уточнения разбиения поддерживает семейство непересекающихся множеств Si . В начале алгоритма это семейство содержит единственное множество всех элементов в структуре данных. На каждом шаге алгоритм получает множество X, и каждое множество Si в семействе, содержащем элементы X, разбивается на два множества: пересечение Si ∩ X и разность Si \ X Этот алгоритм может быть эффективно реализован с помощью структур данных, представляющих следующую информацию:[4][5]
Чтобы выполнить операцию уточнения, алгоритм перебирает элементы данного множества X. Для каждого такого элемента x он находит множество Si которое содержит x, и проверяет, произведено ли пересечение Si ∩ X. Если нет, он создает второе множество и добавляет Si в список L множеств, разделенных операцией. Затем, независимо от того, было ли сформировано новое множество, алгоритм удаляет x из Si и добавляет его к Si ∩ X В представлении, в котором все элементы хранятся в одном массиве, перемещение x из одного множества в другое может выполняться путем обмена x местами c последним элементом Si а затем уменьшения концевого индекса Si и начального индекса нового множества. Наконец, после того, как все элементы X были обработаны таким образом, алгоритм проходит через L, разделяя каждое текущее множество Si на два, рассматривая оба этих множества как сформированные в результате операции уточнения. Оценка времени для выполнения одной операции уточнения таким образом составляет O(|X|), независимо от количества элементов в семействе множеств, а также независимо от общего количества множеств в структуре данных. Поэтому время исполнения последовательности уточнений пропорционально общему размеру множеств, заданных алгоритму на каждом этапе уточнения. ПрименениеОдно из первых применений уточнение разбиения нашло в алгоритме Хопкрофта для минимизации ДКА[6]. В этой задаче на входе задается детерминированный конечный автомат, и он должен найти эквивалентный автомат с как можно меньшим количеством состояний. Алгоритм Хопкрофта поддерживает разделение состояний входного автомата на подмножества с тем свойством, что любые два состояния в разных подмножествах должны отображаться в разные состояния выходного автомата. Изначально существует два подмножества, одно из которых содержит все принимающие состояния автомата, а другое — остальные. На каждом шаге выбираются одно подмножество Si и один из входных символов x автомата, и подмножества состояний уточняются до состояний, для которых переход, помеченный x, приведет в Si, и состояний, для которых x приведет в другое место. Когда выбранное множество Si разделяется уточнением, только одно из двух результирующих множеств (меньшее из двух) нужно рассмотреть снова; таким образом, каждое состояние участвует в множествах X в течение O(s log n) шагов уточнения, а общая оценка времени алгоритма составляет O(ns log n), где n — количество начальных состояний, а s — размер алфавита.[6] Уточнение разделения было применено Sethi[7] в эффективной реализации алгоритма Коффмана — Грэма для параллельного планирования. Сетхи показал, что его можно использовать для построения лексикографически упорядоченной топологической сортировки заданного ориентированного ациклического графа за линейное время; такое лексикографическое топологическое упорядочение является одним из ключевых шагов алгоритма Коффмана — Грэма. В этом приложении элементы непересекающихся множеств являются вершинами входного графа, а множества X используемые для уточнения разбиения, являются множествами соседей вершин. Поскольку общее количество соседей всех вершин — это просто количество ребер в графе, алгоритм требует времени, линейного по количеству ребер. Уточнение разбиения также является ключевым этапом в лексикографическом поиске в ширину, алгоритме поиска по графу с приложениями для распознавания хордовых графов и некоторых других важных классов графов. В этих случаях элементы непересекающихся множеств являются вершинами, а множество X представляет собой множества точек окрестности, поэтому алгоритм занимает линейное время.[8][9] См. такжеПримечания
Литература |