Минимизация недетерминированных конечных автоматов по

on

ВВЕДЕНИЕ Основная задача дискретного программирования состоит в выборе наилучшего варианта из конечного, возможно очень большого их числа. Общую постановку, согласно , можно сформулировать следующим образом: под задачей дискретной оптимизации понимается задача математического программирования f (x0)=min f(x), xG, множество допустимых решений которой конечно, т.е 0?|G|=N . Обычно трудность решения задачи заключается в том, что множество G имеет столь большое число элементов, что практически невозможно эффективно сгенерировать все допустимые решения для выбора лучшего из них, такой перебор невыполним на компьютерах любой мощности. Итак, описание любой оптимизационной задачи включает описание • множества входов; • ограничений для любого входа и допустимых решений • функции стоимости; • цели (max или min). Во многих задачах к условиям дискретности добавляются условия и другого вида, тогда с ростом числа переменных объем вычислительной работы резко возрастает. В выделены следующие особенности задач дискретной оптимизации (ЗДО): • Нерегулярность. ЗДО характеризуются тем, что область допустимых решений невыпуклая и несвязна, поэтому для их решения неприменимы стандартные методы, с помощью которых решают регулярные задачи математического программирования (задачи линейного и выпуклого программирования). • Трудности при определении окрестности в ЗДО. Близость двух допустимых решений x1 и x2 может быть оценена только по значениям функции стоимости f(x1) и f(x2). В качестве примера можно привести понятие окрестности в задаче коммивояжера, где решение представляется последовательностью вершин гамильтонового цикла. Под окрестностью некоторого решения x можно понимать все решения, получаемые из x перестановкой двух вершин. Легко построить примеры задач (матриц стоимости), для которых такая перестановка может привести к значительному изменению стоимости решения. • Невозможность выполнения большого перебора на компьютере. Многие методы решения ЗДО основаны на идее полного перебора допустимых решений. Объем вычислений в таких алгоритмах резко возрастает с ростом размера входных данных. МИНИМИЗАЦИЯ НЕДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ ПО РАЗЛИЧНЫМ КРИТЕРИЯМ Рассмотрим задачу минимизации конечных автоматов. Рис. 1 Рис. 2 Итак, кратко рассмотрим недетерминированные конечные автоматы — автоматы Рабина-Скотта (Медведева). Формальные определения можно найти, например, в , а здесь предлагается неформальное описание. Автомат можно представить в виде ориентированного графа, каждой дуге которого приписана буква некоторого конечного алфавита. Для удобства работы с автоматом вершины графа обычно тоже помечают (но это необязательно). Некоторые вершины графа дополнительно помечены входящими стрeлками, они представляют собой входы автомата. Вершины, помеченные выходящими стрeлками, соответствуют выходам автомата. При этом одна и та же вершина может быть одновременно и входом, и выходом. Пример такого автомата приведен на рис.1. Список его вершин — {1,2,3}, список входов — {1}, список выходов — {2,3}. В автомате возможны дуги-петли. В приведенном примере таких петель три: дуга, ведущая из вершины 3 в нее же, и две дуги-петли с пометками a и b, соответствующие вершине 2. Двигаясь по дугам от какого-нибудь входа автомата к какому-нибудь его выходу и выписывая пометки дуг подряд, слева направо, можно получить последовательность букв. Построенную таким и только таким способом последовательность букв называют словом автомата. Множество всех слов автомата образуют язык автомата. Если в автомате есть вершина, являющаяся одновременно входом и выходом, то язык такого автомата содержит т.н. пустое слово, часто обозначаемое ?. В представленном на рис.1 автомате, словом автомата является, например, abbbba; это слово можно получить, обходя вершины в следующем порядке: 1333122 либо 1331222. Несложно доказать, что если некоторый язык может быть задан (хоть одним) конечным автоматом — то он может быть задан бесконечным числом автоматов. Такие автоматы применяются для определения того, принадлежит ли некоторое слово языку, заданному автомату. Для каждого автомата можно легко построить т.н. зеркальный, изменив направление всех его стрелок (дуг, входов и выходов) на противоположное. Зеркальный автомат задает зеркальный язык, в котором каждое слово исходного языка читается справа налево. На рис.2 приведен пример зеркального автомата, построенного для автомата, изображенного на рис.1. Если автомат обладает одним из следующих свойств: • имеется более одного входа, • имеется (хоть одна) вершина, из которой выходят 2 (или более) дуги с одинаковыми пометками, то такой автомат называется (собственно) недетерминированным. В рассматриваемом примере оба автомата (и исходный, и зеркальный) являются недетерминированными. Например, у автомата на рис.1 из вершины 3 выходят две дуги, помеченные одной и той же буквой b. Однако для каждого автомата существует эквивалентный ему детерминированный автомат, который не обладает ни одним из двух сформулированных свойств. Для рассматриваемых задач важно только, что в процессе детерминизации некоторые вершины исходного автомата могут объединиться в одну вершину автомата нового. В полученном детерминированном автомате как единое целое будут рассматриваться все вершины исходного автомата, в которых он может находиться после прочтения префикса принимаемого слова. Рассмотрим еще один пример. Пусть исходный автомат изображен на рис.7, а эквивалентный ему детерминированный — на рис.4. Точнее, на рис.4 приведен т.н. канонический автомат — полученный из детерминированного объединением всех эквивалентных вершин. Рис. 3 Рис. 4 Рис. 5 Рис.6 В процессе детерминизации легко устанавливается соответствие между вершинами автоматов: вершине 1 соответствуют две вершины — A и B, вершине 2 — только B, а вершине 3 — только C. Например, соответствие между вершиной 1 и вершиной B устанавливается следующим образом: существует слово, прочтя которое первый автомат может находиться в 1, а второй — в B. Таким словом может быть, например, слово из одной буквы a, и это не единственный возможный вариант. Важно отметить, что для построения такого соответствия для заданного автомата существует конечный алгоритм. Теперь рассмотрим зеркальный (для исходного) автомат (рис.5). В данном примере зеркальный автомат фактически совпал с исходным, поскольку может быть получен из него переименованием вершин. Но в общем случае этот факт неверен. Детерминированный (канонический) автомат для зеркального изображен на рис.6; он совпадает с автоматом, приведенным на рис.4, но в общем случае такой факт тоже неверен. Для зеркальных автоматов и языков получается следующее соответствие: вершине 1 соответствуют вершины X и Y, вершине 2 — вершина Z, а вершине 3 — вершина Y. Рис. 7 Тем самым можно установить соответствие между вершиной B (на рис.4) и вершиной Z (на рис.6) «через» вершину 2 (на рис.3 и 5); аналогично вершина C соответствует вершине Y, а каждая из вершин A и B («через» вершину 1) — каждой из вершин X и Y. Таким образом, получается таблица соответствия вершин автоматов, являющихся каноническими для исходного и зеркального автоматов (приведенных на рис.4 и рис.6). Таблица соответствия приведена на рис.7. При этом важно отметить, что каждая такая таблица соответствует даже не автомату, а задаваемому им языку. Более того, можно доказать, что любая прямоугольная таблица, заполненная 0 и 1 и имеющая специальные свойства: • нет одинаковых строк, • нет одинаковых столбцов, • нет ни строк, ни столбцов, содержащих только 0, является таблицей соответствия вершин некоторого автомата. Итак, задачу вершинной минимизации недетерминированных конечных автоматов можно свести к одной (но важнейшей) из возникающих в ней вспомогательных подзадач. Ее можно сформулировать следующим образом. Задана прямоугольная матрица, заполненная элементами 0 или 1. Некоторую пару подмножеств строк и столбцов назовем блоком, если • на их пересечениях стоят только 1; • множество нельзя пополнить ни строкой, ни столбцом, не нарушив первого свойства. Допустимым решением является множество блоков, покрывающих все элементы 1 заданной матрицы. Функций стоимости представляет собой количество содержащихся в решении блоков. Цель — выбрать допустимое решение, содержащее минимальное число блоков. Таблица 1 XYZU A0011 B1001 C1111 D1111 Таблица.1 представляет простой пример к этой задаче. В нем имеются следующие 5 блоков — ?={A,B,C,D}?{U}, ?={A,C,D}?{Z,U} (элементы этого блока выделены курсивом), ?={B,C,D}?{X,U}, ?={C,D}?{X,Z,U} и ?={D}?{X,Y,Z,U}. Для покрытия всех значений 1 заданной матрицы достаточно использовать 3 из этих 5 блоков — ?, ? и ?. ЗАКЛЮЧЕНИЕ В заключении отметим, что конечные автоматы используются в различных областях, в частности, в синтаксических анализаторах, лексических анализаторах, тестировании программного обеспечения на основе моделей и т.п. Для более эффективного использования конечных автоматов в различных областях, необходимо, чтобы проблема минимизации конечных автоматов решалась за реальное время. То есть, алгоритм минимизации должен выполняться за реальное время с разным количеством переменных. Для этого необходимо использовать эвристики и применять разработанные нами эвристические алгоритмы для решения задач дискретной оптимизации. Сигал И., Иванова А. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. — М.: ФИЗМАТЛИТ, 2003 Карпов Ю. Теория автоматов. — СПб.: Питер, 2002 , , Репрезентативность случайно сгенерированных недетерминированных конечных автоматов с точки зрения соответствующих базисных автоматов/ // Стохастическая оптимизация в информатике. Том 6. Санкт-Петербургский государственный университет НИИ информационных технологий. Изд-во: Санкт-Петербургского государственного университета. 2010