4430
правок
Сортировка при помощи транспозиций и обращений (коэффициент аппроксимации 1,5): различия между версиями
Материал из WEGA
Сортировка при помощи транспозиций и обращений (коэффициент аппроксимации 1,5) (посмотреть исходный код)
Версия от 14:26, 14 марта 2019
, 14 марта 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 41: | Строка 41: | ||
'''Конфигурации циклов''' | '''Конфигурации циклов''' | ||
Две пары черных ребер называются пересекающимися, если они чередуются в порядке их появления в круге. Пара черных ребер пересекается с циклом C, если она пересекается в парой черных ребер, принадлежащих к C. Циклы C и D пересекаются, если существует пара черных ребер в C, которая пересекается с D (см. рис. 2e). Два пересекающихся цикла называются перемежающимися, если их пары черных чередуются в порядке их появления в круге (см. рис. 2f). Очевидно, что два цикла могут находиться друг с другом в одном из следующих отношений: (1) непересекающиеся, (2) пересекающиеся, но не перемежающиеся, (3) перемежающиеся. Пара черных ребер называется связанной, если эти ребра соединены серым ребром и если при чтении ребер вдоль цикла они читаются в одном и том же направлении. К примеру, на рис. 2a все пары черных ребер являются связанными. Гу и др. [ ] показали, что для пары связанных черных ребер (b1, b2) существует цикл С, пересекающийся с (b1, b2). 1-скрученной парой является пара 1-скрученных циклов, повороты которых являются последовательными на круге в конфигурации, состоящей только из этих двух циклов. 1-скрученный цикл называется закрытым в конфигурации, если два его связанных ребра пересекаются с некоторым другим циклом конфигурации. Конфигурация называется закрытой, если по крайней мере один из ее 1-скрученных циклов является закрытым; в противном случае она называется открытой. | |||
'''Алгоритм''' | |||
Базовая идея алгоритма 1,5-аппроксимации Хартмана и Шарана для решения задачи сортировки при помощи транспозиций, транспозиций-обращений и двойных обращений заключается в следующем. Авторы свели задачу к сортировке циклической 3-перестановки при помощи транспозиций, транспозиций-обращений и затем сосредоточились на преобразовании 3-циклов в 1-циклы в графе разрывов для этой 3-перестановки. По оопределению, ориентированный (т.е. 2- или 3-скрученный) 3-цикл позволяет выполнять 2-операцию; поэтому авторы продолжили рассмотрение только неориентированных (т. е. 0- или 1-скрученных) 3-циклов. Поскольку конфигурации, включающие только 0-скрученные 3-циклы, в работе [7] обрабатывались при помощи (0, 2, 2)-последовательностей, Хартман и Шаран ограничили рассмотрение конфигурациями, состоящими из 0- и 1-скрученных 3-циклов. Они показали, что все эти конфигурации являются закрытыми и что они могут быть отсортированы при помощи (0, 2, 2)-последовательности операций для каждой из следующих пяти возможных закрытых конфигураций: (1) закрытая конфигурация с двумя неориентированными перемежающимися 3-циклами, не формирующими 1-скрученную пару; (2) закрытая конфигурация с двумя пересекающимися, 0-скрученными 3-циклами; (3) a закрытая конфигурация с двумя пересекающимися, 1-скрученными 3-циклами; (4) закрытая конфигурация с 0-скрученными 3-циклами, пересекающаяся со связанными ребрами 1-скрученного 3-цикла; (5) закрытая конфигурация, содержащая k > 2 взаимно перемежающихся 1-скрученных 3-циклов, таких, что их повороты являются последовательными на круге, а k – максимальное число, обладающее этим свойством. В результате последовательность операций, использованных Хартманом и Шараном в их алгоритме, содержит только 2-операции и (0, 2, 2)-последовательности. Поскольку каждая последовательность из трех операций увеличивает количество нечетных циклов минимум на 4 из возможных 6 за 3 шага, коэффициент этого алгоритма аппроксимации составляет 1,5. Кроме того, Хартман и Шаран показали, что их алгоритм можно реализовать за время <math>O(n^{3/2} \sqrt{log \; n})</math> с использованием структуры данных Каплана и Вербина [10], где n – число элементов в перестановке. | |||
Теорема 1. Задача сортировки линейных перестановок при помощи транспозиций, транспозиций-обращений и двойных обращений является линейно эквивалентной задаче сортировки циклических перестановок при помощи транспозиций, транспозиций-обращений и двойных обращений. | |||
Теорема 2. Существует алгоритм 1,5-аппроксимации для сортировки при помощи транспозиций, транспозиций-обращений и двойных обращений, выполняющийся за время <math>O(n^{3/2} \sqrt{log \; n})</math>. | |||
== Применение == | |||
