Дополнительные эвристики в задаче звёздно-высотной минимизации недетерминированного конечного автомата

Размещено на http://www.allbest.ru/

УДК 519.688

Тольяттинский государственный университет, Тольятти (Россия)

Дополнительные эвристики в задаче звёздно-высотной минимизации недетерминированного конечного автомата

С.В. Баумгертнер, аспирантка.

Аннотация

автомат эвристика динамический звездный

Рассматривается задача построения регулярного выражения с минимальной звёздной высотой для заданного недетерминированного конечного автомата. Предлагается anytime-алгоритм, основанный на применении нескольких эвристик.

Ключевые слова: проблема звёздной высоты; недетерминированный конечный автомат; регулярное выражение; мультиэвристический подход.

Annotation

Complementary heuristics for the star-height miniization problem of a non-deterministic finite automaton

S.V.Baumgertner, postgraduate student.

Togliatti State University, Togliatti (Russia)

In this paper we consider the problem of searching regular expression with minimum star height by a non-deterministic finite automaton. We formulate an anytime-algorithm, which is based on a using of several heuristics.

Keywords: the star-height problem; non-deterministic finite automaton; regular expression; multi-heuristic approach.

Звёздная высота регулярного выражения (обозначим её sh(r)) определяется по индукции следующим образом [6]:

1. sh(Ш)=sh(Ш*)=sh(a)=0 для всех a Є ?.

2. Пусть r и s - произвольные регулярные выражения. Тогда

sh((r+s))=sh((r·s))=max(sh(r),sh(s)).

3. Для любого регулярного выражения r (кроме Ш): sh((r*))=sh(r)+1.

Звёздной высотой регулярного языка называется минимальная из звёздных высот всех регулярных выражений, определяющих этот язык.

Проблема звёздной высоты - проблема построения регулярного выражения, определяющего заданный регулярный язык и имеющего минимальную звёздную высоту. Хашигучи в 1988 опубликовал алгоритм поиска звёздной высоты любого регулярного языка [7]. Однако этот алгоритм совершенно неприменим на практике. Намного эффективнее оказался алгоритм, разработанный Кирстеном в 2005 [8]. На основе этого алгоритма может быть вычислено значение звёздной высоты языка, определяемого заданным автоматом. Но объёмы ресурсов, необходимые для этого алгоритма по-прежнему огромны.

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

Оптимизированный метод полного перебора за разумное время может вычислять звёздную высоту для конечных автоматов с размерностью не более 12-13. Мультиэвристический подход с применением функций риска позволяет поднять эту планку до 18-20. Однако для автоматов с большой размерностью получить точное решение остается проблематичным.

В связи с этим актуальной является задача построения эвристических алгоритмов реального времени (т.н. anytime-алгоритмов, [1]) - для поиска псевдо-оптимального регулярного выражения для регулярного языка, заданного с помощью недетерминированного конечного автомата. В каждый определённый момент работы таких алгоритмов можно получить лучшее (на данный момент) решение, а последовательность таких решений в пределе даёт оптимальное решение. В данной статье будет рассмотрен такой алгоритм, он основан на применении нескольких эвристик.

Методика проведения исследований

1. Алгоритм построения регулярного выражения по НКА

Один из способов построения регулярного выражения по заданному конечному автомату - метод последовательного удаления вершин. В этом методе на каждом шаге из автомата удаляется одна вершина, а все данные о связанных с ней переходах добавляются в новые переходы между оставшимися вершинами автомата. Чтобы получить регулярное выражение с наименьшей звёздной высотой, необходимо перебрать все n! (n - количество вершин) перестановок вершин конечного автомата, найти для них регулярные выражения и выбрать то, которое имеет наименьшую звёздную высоту. Но на практике алгоритм полного перебора неприемлем даже для автоматов с довольно небольшим количеством вершин.

2. Описание применяемых эвристик

Нужно определить порядок удаления вершин таким образом, чтобы пометки новых дуг после удаления следующей вершины имели как можно меньшую звёздную высоту. Неформально описываемые далее эвристики можно объяснить следующим образом: чем больше циклов проходит через данное состояние q, тем больше существует путей на графе переходов автомата, через которые проходят эти циклы. То есть при удалении вершины q ранее других мы с большей вероятностью получаем новые дуги, помеченные регулярными выражениями с большей звёздной высотой.

Эвристика 1. Состояния упорядочиваются в порядке возрастания количества проходящих через них циклов.

Чем больше количество вершин, которые соединяет между собой вершина q, тем больше будет новых пометок дуг с увеличенной звёздной высотой при её удалении.

Эвристика 2. Состояния упорядочиваются в порядке возрастания суммарного количества вершин во всех циклах, проходящих через них.

Эвристика 3. Состояния упорядочиваются в порядке возрастания суммарного количества вершин во всех циклах, проходящих через них, но при этом каждое состояние учитывается только один раз.

Эвристика 4. Оценка состояния получается умножением количества циклов, проходящих через это состояние, на значение эвристики 3.

Эвристика 5. Состояния автомата упорядочиваются в порядке убывания глубины вложенности циклов, в которых они присутствуют.

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

3. Динамические функции риска

Итак, у нас есть данные, полученные с помощью разных эвристик. При этом информация, данная различными эвристиками, может быть противоречива. Будем определять итоговую перестановку вершин автомата с помощью усреднённых оценок. Такие оценки вычисляются с помощью набора коэффициентов [1-4].

Для каждой вершины автомата вычисляется т.н. динамическая оценка:

;

где и(x_i) - т.н. функция риска. Применим функцию риска, полученную согласно [2]:

Усреднение надо делать с весами тем меньшими, чем более хорошей является оценка, данная эвристикой. Если с помощью эвристики получена очень хорошая оценка, нужно учитывать вероятность неблагоприятного исхода (т.н. риск), т.е. не самые удачные реализации случайных факторов считаем более вероятными, чем хорошие. Если получена низкая оценка, наоборот, учитываем вероятность благоприятного исхода случайных факторов.

4. Незавершённый метод ветвей и границ

Незавершённый метод ветвей и границ получается при внесении некоторых изменений в классический метод. Будем называть правой задачей очередного шага задачу, полученную при уменьшении размерности. Другую альтернативу назовём, соответственно, левой задачей очередного шага. С помощью некоторых эвристик мы добиваемся того, чтобы вероятность наличия оптимального решения была больше для правой задачи, чем для левой, т.к. размерность правой задачи на 1 меньше.

Каждый раз при получении очередной правой задачи мы строим последовательность правых задач. Также строятся (и включаются в список задач для потенциального решения в последующем) и соответствующие левые задачи. При получении тривиальной задачи - запоминаем её решение в качестве текущего на данный момент времени псевдо-оптимального решения. При получении в какой-либо задаче достаточно большой границы исключаем её из последующего решения. [1]

Применяя данный подход в случае нашей задачи, мы получаем следующий алгоритм построения искомого регулярного выражения. Будем по очереди удалять из автомата состояния, пока не останется только стартовая и финальная вершины. При удалении состояния q мы получим правую задачу, её размерность станет на 1 меньше. В левой задаче, наоборот, состояние q не может быть удалено на данном шаге. Чтобы выбрать состояние q, получаем оценки для каждого состояния с помощью динамических функций риска. Состояние с лучшей оценкой выбирается для очередного ветвления.

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

Результаты

С целью проверки эффективности работы алгоритма были проведены следующие эксперименты. С помощью алгоритма генерации случайных недетерминированных конечных автоматов, представленного в [5], получены конечные автоматы с количеством состояний 5, 6, 7, 8, и 9. Для данных автоматов были вычислены:

· приближённое решение с применением динамических функций риска (в таблице указан процент совпадения с точным решением);

· точное решение методом перебора (в таблице приведено время вычислений);

· точное решение anytime-алгоритма (в таблице приведено время вычислений);

· решение anytime-алгоритма за различное время (в таблице указан процент совпадения с точным решением);

Таблица 1. Результаты эксперимента

Выводы

Из приведённых результатов видно, что точное решение anytime-алгоритма получено гораздо быстрее, чем решение методом перебора и является более точным, чем решение, полученное с применением только динамических функций риска.

Таким образом, за приемлемое для нас время мы можем найти более точное решение, чем решение, полученное только с помощью динамической функции риска. Вместе с тем, можем найти и точное решение намного быстрее, чем переборными методами.

Список литературы

1. Б.Мельников. Мультиэвристический подход к задачам дискретной оптимизации. - Кибернетика и системный анализ (НАН Украины), 2006, №3. С. 32-42.

2. Б.Мельников, А.Радионов. О выборе стратегии в недетерминированных антагонистических играх. - Известия РАН. Программирование, 1998, №5, C. 55-62.

3. Б.Мельников, Н.Романов. Ещё раз об эвристиках для задачи коммивояжёра. - В кн.: Теоретические проблемы информатики и ее приложений, вып.4, Саратов, изд-во СГУ, 2001, с.81-92.

4. Б.Мельников. Эвристики в программировании недетерминированных игр. - Известия РАН. Программирование, 2001, №5. С. 63-80.

5. С.Пивнева, О.Рогова: Алгоритм определения репрезентативности недетерминированного конечного автомата. - Электронное научное периодическое изд. «Электроника и информационные технологии» (http://fetmag.mrsu.ru/), 2009, вып.1

6. А. Саломаа. Жемчужины теории формальных языков. - М.: Мир, 1986. - 159 с.

7. K.Hashiguchi. Algorithms for determining relative star height and star height. - Inform. Comput., 78 (1988) 124-169.

8. D.Kirsten. Distance desert automata and the star height problem. - Theoret. Informatics Appl., 39 (2005) 455-509.

9. B.Melnikov, A.Vakhitova. Some more on the finite automata. - The Korean Journal of Computional and Applied Mathematics, Vol.5, №3 (1998) 495-506.

Размещено на Allbest.ru