Эвристический алгоритм уменьшения множества допустимых корней в задаче о нахождении минимального языка

Computing Classification System 1998: E.4Mathematics Subject Classification 2010: 68P30

Теоретическая основа алгоритма заключается в следующем: согласно [1], для каждого «хорошего» корня v в дополненном префиксном коде найдётся слово vⁿ .

С учётом этого, а также механизма формирования максимальных префиксных кодов, в дополненном префиксном коде, в случае если n ≠ 1, найдутся так же слова с префиксом v^{n - 1}, кроме самого слова vⁿ . Количество данных слов (с префиксом v^{n - 1} , но заканчивающихся не на v ) будет не меньше m -1, где m – длина минимального языка. Общая формула для этого числа mk + r -1, где m – длина минимального языка, k – число итераций, прошедших на этой ветви максимального префиксного кода, а r – число добавившихся на этой ветви случайных слов.

Более того, это повторяется рекурсивно при дальнейшем уменьшении степеней n .

Всё это касается лишь «хороших» корней. «Плохие» корни могут обладать подобными свойствами лишь случайно. Опишем этот алгоритм:

Алгоритм исследования свойств корней

Шаг 1. i =1;

Шаг 2. Рассмотрим i -й корень множества F ;

Шаг 3. n := степени F [ i ];

Шаг 4. Если n =1, то перейти на шаг 8. j =1;

Шаг 5. Определим число слов в MP(+), обладающих префиксом F [ i ] в степени n -1. Запишем его как m j ;

Шаг 6. n := n -1, j := j +1; если n >1, то перейти на шаг 4;

Шаг 7. m i =min( m j );

Шаг 8. Перейти к следующему корню, i := i +1. Если следующего корня нет, то закончить выполнение алгоритма.

Кроме того, опираясь на вышеприведённые формулы, мы можем оценить максимальное возможное m для минимального языка, включавшего бы этот корень. В ряде случаев этого уже достаточно, чтобы корень можно было исключить. Для этого мы предлагаем такой метод:

Алгоритм исключения

Шаг 1 . Каждому корню сопоставляется число P , обозначающее количество слов в максимальном префиксном коде, для которых он является префиксом.

Шаг 2 . Множество корней сортируется по возрастанию этого показателя.

Шаг 3 . Рассматриваем некий корень, максимально возможная длина минимального языка при включении которого составляет N . Если сумма P этого корня и N -1 корней с самым большим P меньше общей длины нашего дополненного максимального префиксного кода, то этот корень заведомо является «плохим» и может быть удалён из множества корней.

Возможно, есть и более эффективные методы

Данный алгоритм не даёт нам никакой информации о корнях первой степени, для их просева необходимо использовать дополнительный алгоритм.

Данный алгоритм является эвристическим и не гарантирует, что ни один «плохой» корень не попадёт в просеянное множество (но гарантирует, что его не покинет ни один «хороший»), однако он достаточно эффективен в удалении из множества плохих корень со степенью больше 1.

Опираясь на этот алгоритм, мы можем наложить серьёзные ограничения на полный перебор вариантов.

Во-первых, мы можем определить, пользуясь описанным выше способом максимальную и минимальную возможные длины минимального языка. В самом деле, если взять q корней с самым большим P и сложить их P , то, если полученное число оказалось меньше числа слов в MP(+), значит, минимальная длина минимального языка больше, чем q . И наоборот, есть взять s корней с самым маленьким P и сумма их P больше числа слов в MP(+), значит максимальная длина минимального языка меньше, чем s . Таким образом, мы можем определить промежуток, в котором находится длина минимального языка | L |.

Во-вторых, для каждой возможной длины минимального языка l мы можем рассматривать лишь те из них, у которых показатель m_i ≥ l . Более того, если число таких корней меньше, чем l , то мы можем заключить, что | L | не равно рассматриваемому l .

Всё это накладывает серьёзные ограничения на алгоритм полного перебора. Сложность получаемого алгоритм нуждается в дополнительном исследовании.