Мультиэвристический подход к звёздно-высотной минимизации недетерминированных конечных автоматов тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Баумгертнер, Светлана Викторовна

• Баумгертнер, Светлана Викторовна
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Баумгертнер, Светлана Викторовна

Глава 1. Введение.

1.1. Подходы к решению задач дискретной оптимизации.

1.2. Основные вопросы и результаты, связанные с проблемой звёздной высоты.

1.3. Актуальность темы.

Глава 2. Фундаментальные понятия предметной области.

2.1. Формальные языки и конечные автоматы.

2.2. Регулярные выражения.

2.3. Звёздная высота регулярных выражений.

2.4. Метод ветвей и границ.

Глава 3. Эквивалентность конечных автоматов и регулярных выражений. Специальное доказательство теоремы Клини.

3.1. Построение конечного автомата, эквивалентного заданному регулярному выражению.

3.2. Построение регулярного выражения, эквивалентного заданному конечному автомату. Теорема Клини.

Глава 4. Преобразование конечного автомата к регулярному выражению. Точный алгоритм построения оптимального регулярного выражения по заданному конечному автомату.

4.1. Метод последовательного удаления вершин.

4.2. Задача звёздно-высотной минимизации недетерминированного конечного автомата в терминах дискретного программирования.

4.3. Метод оптимизированного полного перебора.

Глава 5. Эвристические алгоритмы для приближённого решения задачи поиска псевдооптимального регулярного выражения по конечному автомату.

Глава 6. Методы усреднения эвристик. Динамические оценки состояний автомата.

Глава 7. Апуйте-алгоритм. звёздно-высотной минимизации недетерминированного конечного автомата.

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

7.2 Пошаговое описание апу1лте-алгоритма.

Глава 8. Обобщённые конечные автоматы и обобщённые регулярные выражения. Алгоритм построения обобщённого регулярного выражения для заданного обобщённого конечного автомата.

8.1. Основные определения.

8.2. Алгоритм построения обобщённого регулярного выражения, эквивалентного обобщённому конечному автомату.

Глава 9. Описание вычислительных экспериментов и их результатов.

9.1. Алгоритм генерации случайного конечного автомата.

9.2. Результаты вычислительных экспериментов.

Глава 10. Описание программной реализации разработанных алгоритмов.

Введение диссертации (часть автореферата) на тему «Мультиэвристический подход к звёздно-высотной минимизации недетерминированных конечных автоматов»

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

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

В третьей главе приводится вариант доказательства эквивалентности конечных автоматов и регулярных выражений, необходимый для описания алгоритмов. Для этого рассматривается специальное доказательство теоремы Клини [84].

Четвёртая глава посвящена описанию точного алгоритма решения рассматриваемой задачи. Приведён алгоритм последовательной элиминации вершин для получения регулярного выражения по конечному автомату, который может рассматриваться как альтернатива алгоритму из доказательства теоремы Клини. Удаляя вершины автомата в разном порядке, можно получать различные регулярные выражения, эквивалентные заданному автомату.

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

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

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

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

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

Эвристика 4. Оценка состояния является произведением значений эвристик 1 и 3.

Приводятся результаты вычислительных экспериментов, позволяющие оценить эффективность разработанных эвристик.

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

Т.к. данная ситуация близка к ситуации выбора стратегии в недетерминированных играх, рассматривается применение в нашей задаче игровых эвристик.

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

С помощью данного метода мы получаем апу^те-алгоритм, позволяющий получить лучшее решение задачи, найденное за определённый пользователем промежуток времени. Приводится пошаговое описание апуйте-алгоритма, алгоритмы вычисления границ и ветвления.

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

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

В десятой главе описывается реализация разработанных алгоритмов. Приводится описание наиболее важных функций, классов и структур данных.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Баумгертнер, Светлана Викторовна

Основные результаты диссертационной работы заключаются в следующем:

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

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

3. Предложен апу^те-алгоритм построения псевдо-оптимального регулярного выражения по заданному конечному автомату, основанный на мультиэвристическом подходе. Данный алгоритм предназначен для поиска псевдо-оптимального решения с заданным ограничением по времени, а также для точного решения рассматриваемой задачи. Время поиска точного решения увеличивается в зависимости от размерности задачи гораздо медленнее, чем время решения переборными методами. За достаточно короткие промежутки времени алгоритм позволяет получить решение, близкое к оптимальному.

4. Разработан комплекс программ, реализующих предложенные алгоритмы.

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Баумгертнер, Светлана Викторовна, 2012 год

1. Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты. - М.: Вильяме, 2003. - 768 с.

2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1. М.: Мир, 1987. - 308с.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

4. Баумгертнер С. Дополнительные эвристики в задаче звёздно-высотной минимизации недетерминированного конечного автомата // Вектор науки Тольяттинского Государственного Университета. 2010. - №3 (13). - С. 37-39.

5. Беллман Р., Калаба Р. Динамическое программирование и современная теория управления. М.: Наука, 1969.

6. Биркгоф Г., Барти Т. Современная прикладная алгебра. СПб.: Лань, 2005.

7. Брауэр Э. Введение в теорию конечных автоматов. М.: Радио и связь, 1987.

8. Бур донов И., Косачев А., Кулямин В. Использование конечных автоматов для тестирования программ // Программирование. -2000.-№2.-С. 12-28.

9. Васильев Ф. Численные методы решения экстремальных задач. -М.: Наука, 1988.

10. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.:1. Мир, 1985.

11. Грунский И. Анализ поведения конечных автоматов. Луганск: Изд-во ЛНПУ, 2003. - 318 с.

12. Грунский И., Козловский В. Синтез и иденификация автоматов. -Киев: Наукова думка, 2004. 246 с.

13. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов.-М.: Мир, 1981.-368 с.

14. Гэри М., Джонсон Д. Вычислительные машины и труднорешае-мые задачи. -М.: Мир, 1982.

15. Ефимов Е. Решатели интеллектуальных задач. М: Наука, 1982.

16. Карлин С. Математические методы в теории игр, программировании и экономике. М., 1964.

17. Карманов В. Математическое программирование. М.: Наука, 1975.

18. Карпов Ю. Теория автоматов. СПб.: Питер, 2002.

19. Кини Р., Райфа X. Принятие решений при многих критериях: предпочтения и замещения. М.: Радио и связь, 1981.

20. Ковалев М. Дискретная оптимизация (целочисленное программирование). М.: УРСС, 2003.

21. Колмогоров А. Теория информации и теория алгоритмов. М.: Наука, 1987.

22. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы построение и анализ. - М.: МЦНМО, 2004.

23. Липпман С. Весь С++. От азов до совершенства. СПб.: Невскийдиалект, 2007.

24. Липский В. Комбинаторика для программистов. М.: Мир, 1988.

25. Люгер Д. Искусственный интеллект стратегии и методы решения сложных проблем. -М.-СПб-Киев: Вильяме, 2003.

26. Маккарти Дж., Хейес Р. Некоторые философские проблемы в задаче построения искусственного интеллекта. Кибернетические проблемы бионики. - М.: Мир, 1972.

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

28. Мельников Б. Недетерминированные конечные автоматы. -Тольятти, 2001.

29. Мельников Б. Недетерминированные конечные автоматы. ТГУ Тольятти, 2009. - №3. - С.32-42.

30. Мельников Б. Важный пример к задачам минимизации недетерминированных конечных автоматов // Тезисы докладов XII международной научной конференции по проблемам теоретической кибернетики.-М.: Изд-воМГУ, 1999. С.153-153.

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

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

33. Мельников Б., Пивнева С., Рогова О. Репрезентативность случайно сгенерированных недетерминированных конечных автоматов с точки зрения соответствующих базисных автоматов // Стохастическая оптимизация в информатике (СПбГУ) . 2010. Том 6. - С. 74-82.

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

35. Минский М. Вычисления и автоматы. М.: Мир, 1971.

36. Мину М. Математическое программирование. Теория и алгоритмы.-М.: Наука, 1990.

37. Нильсон Н. Искусственный интеллект. Методы поиска решений.- М: Мир, 1973.

38. Нильсон Н. Принципы искусственного интеллекта. М: Радио и Связь, 1985.

39. Оллонгрен А. Определение языков программирования интерпретирующими автоматами. М.: Мир, 1977. - 287 с.

40. Ope О. Графы и их применение. - M.: URSS, 2006.

41. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985.

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

43. Полак Э. Численные методы. Единый подход. М.: Мир, 1974.

44. Попов Э., Фридман Г. Алгоритмические основы интеллектуальных роботов и искусственного интеллекта. М: Наука, 1976.

45. Поспелов Д. Данные и знания. Искусственный интеллект. В 3 кн.- М: Радио и связь, 1990.

46. Рассел С., Норвиг П. Искусственный интеллект: современный подход. М.-СПб-Киев: Вильяме, 2006.

47. Рейнгольд Э. Комбинаторные алгоритмы М.: Мир, 1980.

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

49. Самарский А., Михайлов А. Математическое моделирование. -М.: ФИЗМАТЛИТ, 2001.

50. Сачков В. Введение в комбинаторные методы дискретной математики. -М.: Наука, 1982.

51. Сигал И., Иванова А. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмыю. М.: ФИЗМАТЛИТ, 2003.

52. Страуструп Б. Язык программирования С++. М: Бином, 1999.

53. Телло Э. Объектно-ориентированное программирование. М: Высшая школа, 1993.

54. Успенский В., Семенов А. Теория алгоритмов: основные открытия и приложения. М.: Наука, 1987.

55. Фридл Дж. Регулярные выражения. СПб.: Питер, 2001. - 352 с.

56. Ху Т., Шинг М. Комбинаторные алгоритмы. Нижний Новгород: Изд-во Нижегородского госуниверситета им. Н.И.Лобачевского, 2004.

57. Шень А. Программирование: теоремы и задачи. М.: Изд-во МЦНМО, 2004. - 285 с.

58. Эккель Б., Эллисон Ч. Философия С++. Практическое программирование. Спб.: Питер, 2004. - 608 с.

59. Эндрю А. Искусственный интеллект. М: Мир, 1985.

60. Яблонский С. Введение в дискретную математику М.: Высшая школа, 2006.

61. Champarnaud J., Hansel G., Paranthoen Т., Ziadi D. Random generation models for NFA's // Journal of Automata, Languages and Combinatorics. No.9 (2004). - pp. 203-216.

62. Dejean F., Schutzenberger M. On a question of Eggan // Information and Control 9(1). 1966. - pp. 23-25.

63. Eggen L. Transition graphs and the star-height of regular events //

64. The Michigan Mathematical Journal. 1963. - pp. 385-397.

65. Hashiguchi K. Algorithms for determining relative star height and star height // Inform. Comput. 78 (1988). - pp. 124-169.

66. Held M., Karp R. The traveling-salesman problem and minimum spanning trees // Operation Research. 18 (1970). - pp. 1138-1162.

67. Hromkovic J. Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer, 2003.

68. Jiang T., Ravikumar B. Minimal NFA Problems are Hard // SIAM J.Comput. V.22 (1993). -pp. 1117-1141.

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

70. Lombardy S., Sakarovitch J. Star Height of Reversible Languages and Universal Automata // 5th Latin American Theoretical Informatics Symposium. LNCS. - Vol. 2286 (2002).

71. Melnikov B. Discrete optimization problems some new heuristic approaches // 8th International Conference on High Performance Computing and Grid in Asia Pacific Region. - IEEE Computer Society Press Ed., Beijing (China) (HPC-Asia-2005). - pp. 73-80.

72. Melnikov B. Extended nondeterministic finite automata // Fundamenta Informaticae. Vol. 104, No. 3 (2010). - pp. 255-265.

73. Melnikov B. On an expansion of nondeterministic finite automata // The Korean Journal of Computational and Applied Mathematics. -Vol.14,No.1-2 (2007).-pp. 155-166.

74. Melnikov B. Once more about the state-minimization of the nondeterministic finite automata // The Korean Journal of Computational and Applied Mathematics. Vo.7, No.3 (2000). - pp. 655-662.

75. Melnikov B. Once more on the edge-minimization of nondeterministic finite automata and the connected problems // Fundamenta Informaticae. Vol. 104, No. 3 (2010). - pp. 267-283.

76. Melnikov B. The star-height problem // Fundamenta Informaticae. -2011, submitted.

77. Melnikov B., Gumayunov V., Radionov A. Some special heuristics for discrete optimization problems // 8th International Conference on Enterprise Information Systems, Paphos (Cyprus) (ICEIS-2006). -pp. 360-364.

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

79. Perrin D. Finite Automata // Handbook of Theoret. Comput. Sci., Vol.A. Elsevier Sci.Publ., 1990.

80. Stanevichene L., Vylitok A. An algorithm for transformation of finite automata to regular expression // Informática. 11 (2000) No. 1. - pp. 49-54.

81. Zijl L.van, Raitt L. Random Generation of Unary DFAs // South African Computer Journal. V.41(2008). - pp. 57-63.