Уточнение раздела - Partition refinement

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

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

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

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

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

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

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

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

Приложения

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

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

Уточнение разделов также является ключевым шагом в лексикографический поиск в ширину, алгоритм поиска по графу с приложениями для распознавания хордовые графы и несколько других важных классов графов. Снова непересекающиеся элементы множества - это вершины, а множество Икс представлять наборы соседей, поэтому алгоритм занимает линейное время.[8][9]

Смотрите также

Рекомендации

  1. ^ Пейдж, Роберт; Тарджан, Роберт Э. (1987), "Три алгоритма уточнения раздела", SIAM Журнал по вычислениям, 16 (6): 973–989, Дои:10.1137/0216062, МИСТЕР  0917035.
  2. ^ Хабиб, Мишель; Пол, Кристоф; Виеннот, Лоран (1999), "Методы уточнения разделов: интересный набор алгоритмических инструментов", Международный журнал основ информатики, 10 (2): 147–170, Дои:10.1142 / S0129054199000125, МИСТЕР  1759929.
  3. ^ Хабиб, Мишель; Пол, Кристоф; Виеннот, Лоран (1998), «Синтез по уточнению разбиения: полезная процедура для строк, графов, булевых матриц и автоматов», в Морван, Мишель; Майнель, Кристоф; Кроб, Дэниел (ред.), STACS 98: 15-й ежегодный симпозиум по теоретическим аспектам компьютерных наук Париж, Франция, 25–27 февраля 1998 г., Материалы, Конспект лекций по информатике, 1373, Springer-Verlag, стр. 25–38, Дои:10.1007 / BFb0028546, ISBN  978-3-540-64230-5, МИСТЕР  1650757.
  4. ^ Валмари, Антти; Лехтинен, Петри (2008), Альберс, Сюзанна; Вейль, Паскаль (ред.), Эффективная минимизация DFA с частичными функциями перехода, Международный журнал Лейбница по информатике (LIPIcs), 1, Дагштуль, Германия: Schloss Dagstuhl: Leibniz-Zentrum fuer Informatik, стр. 645–656, Дои:10.4230 / LIPIcs.STACS.2008.1328, ISBN  978-3-939897-06-4, МИСТЕР  2873773
  5. ^ Knuutila, Timo (2001), "Повторное описание алгоритма Хопкрофтом", Теоретическая информатика, 250 (1–2): 333–363, Дои:10.1016 / S0304-3975 (99) 00150-4, ISSN  0304-3975
  6. ^ Хопкрофт, Джон (1971), "An п бревно п алгоритм минимизации состояний в конечном автомате », Теория машин и вычислений (Proc. Internat. Sympos., Technion, Haifa, 1971), Нью-Йорк: Academic Press, стр. 189–196, МИСТЕР  0403320.
  7. ^ Сетхи, Рави (1976), "Планирование графиков на двух процессорах", SIAM Журнал по вычислениям, 5 (1): 73–82, Дои:10.1137/0205005, МИСТЕР  0398156.
  8. ^ Роуз, Д. Дж .; Тарьян, Р.Э.; Люкер, Г. С. (1976), "Алгоритмические аспекты исключения вершин на графах", SIAM Журнал по вычислениям, 5 (2): 266–283, Дои:10.1137/0205021.
  9. ^ Корнейл, Дерек Г. (2004), «Поиск в лексикографическом диапазоне - обзор», в Хромковиче, Юрай; Нагл, Манфред; Вестфехтель, Бернхард (ред.), Теоретико-графические методы в компьютерных науках: 30-й международный семинар, WG 2004, Бад-Хоннеф, Германия, 21-23 июня 2004 г., исправленные статьи, Конспект лекций по информатике, 3353, Springer-Verlag, стр. 1–19, Дои:10.1007/978-3-540-30559-0_1.