Изменения
Нет описания правки
'''for''' <tex> i \in \mathtt{Involved}</tex>
'''if''' <tex>\mathtt{Count}[i] <</tex> '''size of''' <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]} = </tex> '''size of''' <tex>\mathtt{P}</tex> <font color=darkgreen> //Запишем в <tex>\mathtt{Twin[i]}</tex> индекс нового класса</font>
'''for''' <tex>q \in C</tex> '''and''' <tex>r \in \mathtt{Inv}[q][a]</tex>
<tex>i = \mathtt{Class}[r]</tex>
}}
=== Альтернативная реализация ===
Вообще, алгоритм можно реализовать и с меньшим количеством используемых структур (что делает код на порядок читабельнее).
'''insert''' <tex>\langle F,\ c \rangle</tex>, <tex>\langle Q \setminus F,\ c \rangle</tex> '''into''' <tex> \mathtt{Queue}</tex>
'''while''' <tex>\mathtt{Queue} \ne \varnothing</tex>
<tex>\langle C,\ a \rangle</tex> <tex>\leftarrow</tex> '''take any from''' <tex>\mathtt{Queue}</tex> <font color=darkgreen> //Взять любую пару из <tex>\mathtt{Queue}</tex>, не удаляя (!)</font>
<tex>\mathtt{Involved} \leftarrow \varnothing</tex>
'''for''' <tex>q \in C</tex> '''and''' <tex>r \in \mathtt{Inv}[q][a]</tex>
<tex>\mathtt{Involved}[i] = \{\}</tex>
'''add''' <tex>r</tex> '''to''' <tex>\mathtt{Involved}[i]</tex>
'''for''' <tex> i \in \mathtt{Involved}</tex> <font color=darkgreen> //Перебираем ключи <tex>\mathtt{Involved}</tex></font>
'''if''' '''size of''' <tex>\mathtt{Involved}[i] <</tex> '''size of''' <tex>\mathtt{P}[i]</tex>
'''insert''' <tex>\{\}</tex> '''into''' <tex>\mathtt{P}</tex> <font color=darkgreen> //Создадим пустой класс в разбиении <tex>\mathtt{P}</tex></font> <tex>j = </tex> '''size of''' <tex>\mathtt{P}</tex> <font color=darkgreen> //Запишем в <tex>j</tex> индекс нового класса</font>
'''for''' <tex>r</tex> '''in''' <tex>\mathtt{Involved}[i]</tex>
'''remove''' <tex>r</tex> '''from''' <tex>\mathtt{P}[i]</tex>
<tex>cnt1 \leftarrow </tex> '''size of''' <tex>\mathtt{P}[R_1]</tex>
<tex>cnt2 \leftarrow </tex> '''size of''' <tex>\mathtt{P}[R_2]</tex>
'''if''' <tex>\lnot(<tex>\langle R_1, c \rangle</tex> '''in''' <tex>\mathtt{Queue})</tex>) '''and''' <tex> cnt1 \leqslant cnt2 </tex>
'''insert''' <tex>\langle R_1, c \rangle</tex> '''into''' <tex>\mathtt{Queue}</tex>
'''else'''
'''insert''' <tex>\langle R_2, c \rangle</tex> '''into''' <tex>\mathtt{Queue}</tex>
=== Сравнение с алгоритмом из оригинальной статьи Хопкрофта ===
В оригинальной статье <ref>[http://i.stanford.edu/pub/cstr/reports/cs/tr/71/190/CS-TR-71-190.pdf ''John Hopcroft'' An O(nlogn) algorithm for minimizing states in a finite automation]</ref> использовалась дополнительная структура, которую мы обозначим, как <tex>\mathtt{ClassInv}</tex>, в <tex>\mathtt{ClassInv}[C][a]</tex> будем хранить множество состояний, из которых есть ребро по символу <tex>a</tex> в состояние <tex>C</tex> (аналогично <tex>Inv</tex>, только для классов).
<tex>\mathtt{pushSetsToQueue}(\mathtt{Queue},\ R_1,\ R_2,\ c)</tex>:
<tex>cnt1 \leftarrow \mathtt{ClassInv}[R_1][c]</tex>
<tex>cnt2 \leftarrow \mathtt{ClassInv}[R_2][c]</tex> <font color=darkgreen>//Рассмотреть случаи, <tex> cnt1 == 0 </tex>, <tex> cnt2 == 0 </tex></font>
'''if''' <tex> \mathtt{InQueue}[R_1][c] ==</tex> ''false'' '''and''' <tex> cnt1 \leqslant cnt2 </tex>
'''push''' <tex>\langle R_1, c \rangle</tex> '''to''' <tex>\mathtt{Queue}</tex>
