Доработка раздела

редактировать

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

Уточнение разбиения является ключевым компонентом нескольких эффективных алгоритмов на графах и конечных автоматах, включая минимизацию DFA, алгоритм Коффмана – Грэма для параллельного планирования и лексикографический поиск графов в ширину.

СОДЕРЖАНИЕ
  • 1 Структура данных
  • 2 Приложения
  • 3 См. Также
  • 4 ссылки
Структура данных

Алгоритм уточнения разбиения поддерживает семейство непересекающихся множеств S i. В начале алгоритма это семейство содержит единый набор всех элементов в структуре данных. На каждом шаге алгоритма, набор Х представлен алгоритм, и каждый набор S I в семье, которая содержит членов X разбивается на два множества, то пересечение S я ∩ X и разность S I \ Х.

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

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

Для того, чтобы выполнить операцию уточнения, алгоритм перебирает элементы данного множества X. Для каждого такого элемента x он находит набор S i, который содержит x, и проверяет, был ли уже запущен второй набор для S i ∩ X. Если нет, он создает второй набор и добавляет S i в список L наборов, которые разделяются операцией. Затем, независимо от того, был ли сформирован новый набор, алгоритм удаляет й из S я и добавляет его в S я ∩ X. В представлении, в котором все элементы хранятся в одном массиве, перемещение x из одного набора в другой может быть выполнено путем замены x последним элементом S i, а затем уменьшения конечного индекса S i и начального индекса нового установленный. Наконец, после того, как все элементы X были обработаны таким образом, алгоритм проходит через L, отделяя каждый текущий набор S i от второго набора, который был отделен от него, и сообщает, что оба этих набора были вновь сформированы в результате уточнения. операция.

Время для выполнения одной операции уточнения таким образом составляет O (| X |), независимо от количества элементов в семействе наборов, а также независимо от общего количества наборов в структуре данных. Таким образом, время для последовательности уточнений пропорционально общему размеру наборов, заданных алгоритму на каждом этапе уточнения.

Приложения

Раннее применение уточнения разбиения было в алгоритме Хопкрофта (1971) для минимизации DFA. В этой задаче на входе задается детерминированный конечный автомат, и он должен найти эквивалентный автомат с как можно меньшим количеством состояний. Алгоритм Хопкрофта поддерживает разделение состояний входного автомата на подмножества с тем свойством, что любые два состояния в разных подмножествах должны отображаться в разные состояния выходного автомата. Изначально существует два подмножества, одно из которых содержит все принимающие состояния автомата, а другое - остальные. На каждом шаге выбираются одно из подмножеств S i и один из входных символов x автомата, и подмножества состояний уточняются до состояний, для которых переход, помеченный x, приведет к S i, и состояний, для которых x - переход приведет в другое место. Когда набор S i, который уже был выбран, разделяется уточнением, только один из двух результирующих наборов (меньший из двух) нужно выбрать снова; таким образом, каждое состояние участвует в наборах X для O ( s log n) шагов уточнения, а общий алгоритм занимает время O ( ns log n), где n - количество начальных состояний, а s - размер алфавита.

Уточнение разделения было применено Сетхи (1976) в эффективной реализации алгоритма Коффмана – Грэма для параллельного планирования. Сетхи показал, что его можно использовать для построения лексикографически упорядоченного топологического типа заданного ориентированного ациклического графа за линейное время; такое лексикографическое топологическое упорядочение является одним из ключевых шагов алгоритма Коффмана – Грэма. В этом приложении элементы непересекающихся множеств являются вершинами входного графа, а множества X, используемые для уточнения разбиения, являются множествами соседей вершин. Поскольку общее количество соседей всех вершин - это просто количество ребер в графе, алгоритм требует времени, линейного по количеству ребер, его входному размеру.

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

Смотрите также
использованная литература
Последняя правка сделана 2024-01-08 08:49:40
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте