Уточнение разбиения

При разработке алгоритмов уточнение разбиения — это метод представления разбиения множества в виде структуры данных, которая позволяет разбивать его множества на большее количество меньших множеств. В этом смысле уточнение разбиения двойственно системе непересекающихся множеств, которая также поддерживает разбиение на непересекающиеся множества, но в которой операции объединяют пары наборов. В некоторых приложениях уточнения разбиения, таких как лексикографический поиск в ширину, структура данных поддерживает также порядок наборов в разделе.

Уточнение разбиения является ключевым компонентом нескольких эффективных алгоритмов на графах и конечных автоматах, включая минимизацию ДКА, алгоритм Коффмана – Грэма для параллельного планирования и лексикографический поиск в ширину.<ref>Шаблон:Citation.</ref><ref>Шаблон:Citation.</ref><ref>Шаблон:Citation.</ref>

Структура данных

Алгоритм уточнения разбиения поддерживает семейство непересекающихся множеств Шаблон:Math . В начале алгоритма это семейство содержит единственное множество всех элементов в структуре данных. На каждом шаге алгоритм получает множество Шаблон:Mvar, и каждое множество Шаблон:Math в семействе, содержащем элементы Шаблон:Mvar, разбивается на два множества: пересечение Шаблон:Math и разность Шаблон:Math

Этот алгоритм может быть эффективно реализован с помощью структур данных, представляющих следующую информацию:<ref>Шаблон:Citation Шаблон:Wayback</ref><ref>Шаблон:Citation</ref>

• Упорядоченная последовательность множеств Шаблон:Math в семействе в такой форме, как двусвязный список, который позволяет вставлять новые наборы в середину последовательности.
• Соответствующая каждому множеству Шаблон:Math коллекция его элементов, организованная как двусвязный список или массив, чтобы обеспечить возможность быстрого удаления отдельных элементов из коллекции. Альтернативно этот компонент структуры данных может быть представлен путем хранения всех элементов всех множеств в одном массиве, отсортированном по идентификатору множества каждого элемента, или путем представления коллекции элементов в любом множестве Шаблон:Math по его начальной и конечной позициям в этом массиве.
• С каждым элементом связан набор, к которому он принадлежит.

Чтобы выполнить операцию уточнения, алгоритм перебирает элементы данного множества Шаблон:Mvar. Для каждого такого элемента Шаблон:Mvar он находит множество Шаблон:Math которое содержит Шаблон:Mvar, и проверяет, произведено ли пересечение Шаблон:Math. Если нет, он создает второе множество и добавляет Шаблон:Math в список Шаблон:Mvar множеств, разделенных операцией. Затем, независимо от того, было ли сформировано новое множество, алгоритм удаляет Шаблон:Mvar из Шаблон:Math и добавляет его к Шаблон:Math В представлении, в котором все элементы хранятся в одном массиве, перемещение Шаблон:Mvar из одного множества в другое может выполняться путем обмена Шаблон:Mvar местами c последним элементом Шаблон:Math а затем уменьшения концевого индекса Шаблон:Math и начального индекса нового множества. Наконец, после того, как все элементы Шаблон:Mvar были обработаны таким образом, алгоритм проходит через Шаблон:Mvar, разделяя каждое текущее множество Шаблон:Math на два, рассматривая оба этих множества как сформированные в результате операции уточнения.

Оценка времени для выполнения одной операции уточнения таким образом составляет Шаблон:Math, независимо от количества элементов в семействе множеств, а также независимо от общего количества множеств в структуре данных. Поэтому время исполнения последовательности уточнений пропорционально общему размеру множеств, заданных алгоритму на каждом этапе уточнения.

Применение

Одно из первых применений уточнение разбиения нашло в алгоритме Хопкрофта для минимизации ДКА<ref name=":0" />. В этой задаче на входе задается детерминированный конечный автомат, и он должен найти эквивалентный автомат с как можно меньшим количеством состояний. Алгоритм Хопкрофта поддерживает разделение состояний входного автомата на подмножества с тем свойством, что любые два состояния в разных подмножествах должны отображаться в разные состояния выходного автомата. Изначально существует два подмножества, одно из которых содержит все принимающие состояния автомата, а другое — остальные. На каждом шаге выбираются одно подмножество Шаблон:Math и один из входных символов Шаблон:Mvar автомата, и подмножества состояний уточняются до состояний, для которых переход, помеченный Шаблон:Mvar, приведет в Шаблон:Math, и состояний, для которых Шаблон:Mvar приведет в другое место. Когда выбранное множество Шаблон:Math разделяется уточнением, только одно из двух результирующих множеств (меньшее из двух) нужно рассмотреть снова; таким образом, каждое состояние участвует в множествах Шаблон:Mvar в течение Шаблон:Math шагов уточнения, а общая оценка времени алгоритма составляет Шаблон:Math, где Шаблон:Mvar — количество начальных состояний, а Шаблон:Mvar — размер алфавита.<ref name=":0">Шаблон:Citation.</ref>

Уточнение разделения было применено Sethi<ref>Шаблон:Статья</ref> в эффективной реализации алгоритма Коффмана — Грэма для параллельного планирования. Сетхи показал, что его можно использовать для построения лексикографически упорядоченной топологической сортировки заданного ориентированного ациклического графа за линейное время; такое лексикографическое топологическое упорядочение является одним из ключевых шагов алгоритма Коффмана — Грэма. В этом приложении элементы непересекающихся множеств являются вершинами входного графа, а множества Шаблон:Mvar используемые для уточнения разбиения, являются множествами соседей вершин. Поскольку общее количество соседей всех вершин — это просто количество ребер в графе, алгоритм требует времени, линейного по количеству ребер.

Уточнение разбиения также является ключевым этапом в лексикографическом поиске в ширину, алгоритме поиска по графу с приложениями для распознавания хордовых графов и некоторых других важных классов графов. В этих случаях элементы непересекающихся множеств являются вершинами, а множество Шаблон:Mvar представляет собой множества точек окрестности, поэтому алгоритм занимает линейное время.<ref>Шаблон:Citation.</ref><ref>Шаблон:Citation.</ref>

См. также

• Уточнение (сигма-алгебра)