19
правок
Изменения
sta
=== Реализация ===
*<tex>\mathtt{Q}</tex> {{---}} множество состояний ДКА,
'''if''' <tex> R_1 \ne \varnothing </tex> '''and''' <tex> R_2 \ne \varnothing </tex>
'''replace''' <tex>R</tex> '''in''' <tex>\mathtt{P}</tex> '''with''' <tex>R_1</tex> '''and''' <tex>R_2</tex>
'''if''' <tex>\langle R,\ c \rangle</tex> '''in''' <tex> \mathtt{S}</tex>
'''remove''' <tex>\langle R, c \rangle</tex> '''from''' <tex>\mathtt{S}</tex>
'''push''' <tex>\langle R_2, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex>
'''else'''
'''if''' <tex> |\mathrmmathtt{cnt1P} [R_1]| \leqslant |\mathrmmathtt{cnt2P} [R_2]| </tex>
'''push''' <tex>\langle R_1, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex>
'''else'''
'''push''' <tex>\langle R_2, c \rangle</tex> '''into''' <tex>\mathtt{S}</tex>
'''return''' <tex>\mathtt{P}</tex>
Понятно, что нам нет никакой необходимости просматривать все классы в разбиении. Вполне достаточно рассмотреть лишь те классы, из состояний которых есть хотя бы одно ребро в состояния сплиттера. Обозначим множество таких классов за <tex>T'</tex> (его нужно будет эффективно находить для каждой пары <tex>\langle C,\ a \rangle</tex>).
'''if''' <tex> R_1 \ne \varnothing </tex> '''and''' <tex> R_2 \ne \varnothing </tex>
'''replace''' <tex>R</tex> '''in''' <tex>\mathtt{P}</tex> '''with''' <tex>R_1</tex> '''and''' <tex>R_2</tex>
'''if''' <tex>\langle R,\ c \rangle</tex> '''in''' <tex>\mathtt{pushSetsToQueueS}(</tex> '''remove''' <tex>\langle R, c \rangle</tex> '''from''' <tex>\mathtt{S}</tex> '''push''' <tex>\langle R_1,c \rangle</tex> '''into''' <tex>\ Rmathtt{S}</tex> '''push''' <tex>\langle R_2,c \rangle</tex> '''into''' <tex>\mathtt{S}</tex> '''else''' '''if''' <tex> |\mathtt{P}[R_1]| \leqslant |\mathtt{P}[R_2]| </tex> '''push''' <tex>\ langle R_1,c \ rangle</tex> '''into''' <tex>\mathtt{S}</tex> '''else''' '''push''' <tex>\langle R_2), c \rangle</tex> '''into''' <tex>\mathtt{S}</tex>
'''return''' <tex>\mathtt{P}</tex>
*<tex>\mathtt{Involved}</tex> {{---}} список из номеров классов, содержащихся во множестве <tex>T'</tex>,
*<tex>\mathtt{Count}</tex> {{---}} целочисленный массив, где <tex>\mathtt{Count}[i]</tex> хранит количество состояний из класса <tex>i</tex>, которые содержатся в <tex>\mathtt{Inverse}</tex>,
*<tex>\mathtt{Reversed}</tex> {{---}} массив булеан, <tex>\mathtt{Reversed}[i] == </tex> ''true'', если требуется добавлять состояния из <tex>\mathtt{Inverse}</tex> в исходный класс <tex>i</tex>, а не в новый класс (<tex>\mathtt{Twin}[i]</tex>),*<tex>\mathtt{Twin}</tex> {{---}} массив, хранящий в <tex>\mathtt{Twin}[i]</tex> номер нового класса, образовавшегося при разбиении класса <tex>i</tex>.,*<tex>\mathtt{Used}</tex> {{---}} массив булеан, <tex>\mathtt{Used}[r] == </tex> ''true'', если состояние <tex>r</tex> попало в <tex>\mathtt{Inverse}</tex>
<tex>\mathtt{findEquivalenceClasses}(Q,\ F,\ \delta)</tex>:
'''insert''' <tex>i</tex> '''in''' <tex>\mathtt{Involved}</tex>
<tex>\mathtt{Count}[i]++</tex>
<tex>\mathtt{Used}[r] = </tex> ''true''
'''for''' <tex> i \in \mathtt{Involved}</tex>
'''if''' <tex>\mathtt{Count}[i] <</tex> <tex>|\mathtt{P}[i]|</tex>
'''insert''' <tex>\{\}</tex> '''into''' <tex>\mathtt{P}</tex> <font color=darkgreen>//Создадим пустой класс в разбиении <tex>\mathtt{P}</tex></font>
<tex>\mathtt{Twin[i]} = |\mathtt{P}|</tex> <font color=darkgreen>//Запишем в <tex>\mathtt{Twin[i]}</tex> индекс нового класса</font>
'''if''' <tex>\mathtt{Count}[i] > |\mathtt{P}[i]|/2</tex>
<tex>\mathtt{Reversed}[i] = </tex> ''true''
'''for''' <tex>q \in C</tex> '''and''' <tex>r \in \mathtt{Inv}[q][a]</tex>
<tex>i = \mathtt{Class}[r]</tex>
'''if''' <tex>\mathtt{Twin}[i] \neq 0</tex>
'''removeif''' <tex>\lnot \mathtt{Reversed}[i]</tex> <tex>\mathtt{move}(r,\ i,\ \mathtt{Twin}[i])</tex> <tex>\mathtt{Used}[r] = </tex> ''false'from' '''for''' <tex> i \in \mathtt{Involved}</tex> '''if''' <tex>\mathtt{PTwin}[i]\neq 0 </tex> '''addif''' <tex>r\mathtt{Reversed}[i]</tex> '''tofor''' <tex>r \in \mathtt{P}[i] </tex> '''if''' <tex>\lnot \mathtt{TwinUsed}[i]r]</tex> <tex>\mathtt{Classmove}[(r] = ,\ i,\ \mathtt{Twin}[i])</tex> <tex>\mathtt{Used}[r] = </tex>''false'' '''for''' <tex> j c \in \mathtt{Involved}Sigma</tex> '''ifpush''' <tex> \langle \mathtt{Twin}[ji] , c \neq 0 rangle</tex> '''to''' <tex>\mathtt{pushSetsToQueue}(\mathtt{Queue},\ j,\ </tex> <tex>\mathtt{TwinCount}[ji])= 0</tex> <tex>\mathtt{CountReversed}[ji] = 0</tex>''false'' <tex>\mathtt{Twin}[ji] = 0</tex>
'''return''' <tex>\mathtt{P}</tex>
Стоит пояснитьотметить, зачем требуется менять содержимое множеств (что массивы <tex>\mathtt{swapClassesCount}(R_1,\ R_2)</tex>). Почему нельзя просто проверить <tex> \mathrmmathtt{cnt1Twin} ,\leqslant \mathrmmathtt{cnt2Used} </tex>, и на основе этого добавить либо первое, либо второе? Ответ кроется в том, что де-факто мы создаем только один новый класс, старый класс (<tex>R_1</tex>) мы только меняем в размерах. Потому если <tex>\langle R_1, c \ranglemathtt{Reversed}</tex> уже есть в очереди, у нас не остается иного выбора, кроме как добавить <tex>\langle R_2, c \rangle</tex>. Однако, может случится, что <tex>|R_2| > |R_1| </tex>, что как аллоцируются ровно один раз и может потенциально дать квадратичную ассимптотику (логарифмическая достигается как раз за счет того, что добавляемый в очередь подкласс - меньший)при инициализации алгоритма.
===Время работы===
<tex>j = |\mathtt{P}|</tex> <font color=darkgreen>//Запишем в <tex>j</tex> индекс нового класса</font>
'''for''' <tex>r</tex> '''in''' <tex>\mathtt{Involved}[i]</tex>
'''removeif''' <tex>r|\mathtt{Involved}[i]| \leqslant |\mathtt{P}[i]|/2</tex> '''from''' <tex>\mathtt{Pmove}[(r,\ i],\ j)</tex> '''addelse''' <tex>\mathtt{move}(r,\ j,\ i)</tex> '''tofor''' <tex>c \mathtt{P}[j]in \Sigma</tex> '''push''' <tex>\mathtt{Class}[r] = langle j, c \rangle</tex> '''into''' <tex>\mathtt{pushSetsToQueue}(\mathtt{Queue},\ i,\ j)</tex>
'''remove''' <tex>\langle C,\ a \rangle</tex> '''from''' <tex> \mathtt{Queue}</tex>
'''return''' <tex>\mathtt{P}</tex>
== См. также ==
