УДК 681.3.06
ТЕОРЕТИЧЕСКИЕ ВОПРОСЫ ПРОГРАММИРОВАНИЯ
АВТОМАТНОЕ РАСПОЗНАВАНИЕ ДВУСВЯЗНЫХ ЛАБИРИНТОВ С КОНЕЧНЫМ ЦИКЛИЧЕСКИМ ДИАМЕТРОМ
© 2010 г. Б. Стаматович
Факультет информационных систем и технологий Университет Доня Горица Черногория E-mail: biljas@cg.ac.me Поступила в редакцию 19.05.2009 г.
Изучается проблема существования распознающего автомата для подкласса бесконечного класса шахматных лабиринтов (этот класс будем обозначать Со). В работе [1] доказано, что для С0 не существует распознающего автомата. В работе [2] доказано, что существует распознающий коллектив типа (1,1) (коллектив из автомата и камня). Мы доказываем, что существует распознающий автомат для некоторого подкласса класса шахматных лабиринтов с конечным циклическим диаметром.
1. ОПРЕДЕЛЕНИЯ И ОСНОВНЫЕ РЕЗУЛЬТАТЫ
Основные обозначения и понятия из теории автоматов, используемые в работе, взяты из [1-5].
Пусть Ха, а € I, - некоторое множество. Тогда через ра обозначим проекцию произведения
П на а-ый сомножитель Ха. ве I
Пусть Ь = (V, Е) - некоторый диграф (ориентированный граф), где V - множество вершин, Е С V х V - множество дуг. Если задана некоторая функция / : Е ^ У, то пара (Ь, /) называется нагруженным графом, множество У -множеством отметок, а / - разметкой (дуг) графа Ь. Элемент /(и) € У, где и € Е, называется отметкой дуги и в нагруженном диграфе (Ь, /).
Пусть В = {е, п, з}, где е и п, соответственно, есть г и j, где г и ] - базисные единичные векторы 2-мерного Евклидова пространства, а векторы ' и з равны, соответственно, векторам —г и -/.
Полагаем, что в нагруженном диграфе (Ь, /) для каждой дуги (х, у) € Е имеет место (у, х) € € Е. Мы также предполагаем, что диграф связен и не имеет петель. Диграф (Ь, /) называется
2-лабиринтом, или в последующем просто лабиринтом, если:
1) IV\> 2 и У = В;
2) для любого и,у € Е, и = V, если р\(и) = = р^), то /(и) = /(V);
3) для любых х,у € V, если (х, у) € Е, то
/((х, у)) = - /((у, х)).
Кроме того, мы предполагаем, что нагрузка / лабиринта (Ь, /) задана, поэтому будем обозначать лабиринт просто Ь. Часто вместо Ь будем писать (Ь; х) или Ьх, где х € V , если в Ь отмечена одна вершина х, которая называется входом или началом лабиринта Ь; в этом случае лабиринт Ь является инициальным.
Обозначим через \и\ь отметку дуги и в лабиринте Ь. Тогда для вершины х € V множество отметок [х]ь есть {\и\ь \ и € Ех}, где Ех = {и € Е \ р1 (и) = х}.
Пусть М и N, М = N, - некоторые точки плоскости, и М-! = аг + вj. Будем говорить, что вектор м! идет в направлении:
1) е, если а > 0 и в = 0;
2) п, если а = 0 и в > 0;
1 0 0 1 1 0 0 1 0
Рис. 1. Пример входной конфигурации с допустимыми выходами р4 и р7.
3) ш, если а < 0 и в = 0;
4) в, если а = 0 и в < 0.
Множество Т отрезков на плоскости называется конфигурацией, если любые два разных отрезка из этого множества могут иметь не больше одной общей точки, причем, если она у них есть, то она обязательно является концевой для обоих отрезков.
Лабиринт Ь = (У,Е), где V С К2 (К - множество реальных чисел), называем прямоугольным лабиринтом, если для любых х,у € V из (х,у) € Е следует, что отрезок хУ идет в направлении \(х,у)\, а множество отрезков Т = = {ху \ (х, у) € Е} является конфигурацией.
Фигура Ь = и ху в К2 называется реа-
(ху)еЕ(Ь)
лизацией прямоугольного лабиринта Ь.
Пусть 12 - целочисленная решетка на плоскости. Введем функцию расстояния d в 12 следующим образом. Для любых двух точек п,у € 12 положим d(u,v) = ((р1(и) — Р1(^))2 + (р2(и) — —Р2^))2)2. Для любого конечного множества V С 12 обозначим diam(V) = тах и, V) \ и^ € € V}.
Пусть а = (а1, а2) и Ь = (Ь1, Ь2) - произвольные элементы множества 12. Говорим, что а и Ь (слабо) соседние, если а, Ь) < 2) d(a, Ь) = 1. Последовательность а = ро,р1,... ,рт = Ь в 12 называется (слабой) цепью, связывающей точку а и точку Ь, если точки р—1 и р^ (слабо) соседние для любого ^ 1 < i < т. Множество V С 12 называется (слабо) связным, если для любых а,Ь € V существует (слабая) цепь в V, связывающая их. Компонентом (слабой) связности множества V называется любое максимальное (слабое) связное подмножество множества V.
Проведем через вершины 12 все возможные прямые, параллельные осям координат. Полученная фигура является реализацией прямоугольного лабиринта, который обозначим через 12. Под мозаичным лабиринтом будем понимать
любую связную часть (нагруженную) лабиринта Z2. Под шахматным лабиринтом будем понимать любой связный подграф (нагруженный) лабиринта Z2, в котором для любых соседних точек a,b Е Z2 сушествуют дуги (a, b) и (b, a).
Из введенных определений следует, что шахматный лабиринт может быть задан функцией с : Z2 ^ E2, E2 = {0,1}, где Vc = с"1({1}) -связное множество. Шахматный лабиринт L бесконечен (конечен), если множество Vc бесконечно (конечно). Далее предполагаем, что все шахматные лабиринты конечны.
Дырой лабиринта L называется произвольная компонента слабой связности множества Z2\ \Vc. Граница дыры А есть подграф с множеством вершин [А] = {x Е Vc \3у Е А,у — слабо соседняя сx}. Если A(L) - множество конечных дыр лабиринта L, то число cdiamL = = max{diamA\A Е A(L)} называем циклическим диаметром лабиринта L.
Пусть V = ((1, —1), (1, 0), (1,1), (0, —1), (0,1), (—1, —1), (—1, 0), (—1,1)) = (pi,p2,...,Ps) - упорядоченный набор элементов из Z2. Набор V определяет для каждого z Е Z2 набор V(z) = = (z,z + pi,z + p2,...,z + ps). Набор V(z) называем окретностью точки z Е Z2.
Пусть Aq0 = (A,Q,B,^,^,q0) - автомат, где A - входной алфавит, B - выходной алфавит, Q - множество состояний, ф : Q х A ^ Q -функция изменения состояния, ф : Q х A ^ -функция выхода, qo - началное состояние. Автомат Aq0 является допустимым, если A = (E2)9, B = D U 0 С {0,pi,p2,... ,ps} и для всех q Е Q и a = (1,a2,a3,a4,a5,a6,a7,as,ag) Е A ai+i = 1 при ^(q, a) = pi, считая, что p0 = 0 = (0, 0) -нулевой вектор. В дальнейшем предполагаем, что все автоматы являются допустимыми. На рис. 1 допустимыми выходами автомата являются p4, p7. Набор V называем полем зрения автомата A.
Поведением автомата в лабиринте называем последовательность n(Aq0, V, с, v0) = (z0, q0,a0, bo), (zi,qi,ai,bi), (z2,q2,a2,b2),..., где z0 = V0, zi+i = zi + bi, qi+i = <p(qi,ai), ai = (c(zi),c(zi+
+pi), C(zi + P2), C(zi + P3),c(zi + P4),c(zi +P5),c(zi + +Рб), c(zi + P7),c(zi + ps)) и bi = ^(qi,ai). Ясно, что если автомат допустимый, то zt Е Vc для каждого t, t = 0,1, 2 ... Пусть Int(Aq0 ,Lv0) =
= и {г%}. Если Ш(Ад0,ЬЩ) = V(Ь^о), то гово-
г=1
рим, что автомат обходит лабиринт.
Пусть фр = {дРо ,дР1} и фр С ф. Будем говорить, что автомат распознает лабиринт ЬЩ), если при запуске этого автомата в лабиринт ЬУо в итоге происходит переход в заключительное состояние др1, а при запуске в лабиринт Ь1 = ЬУо происходит переход в заключительное состояние др0. Пусть С - класс инициальных лабиринтов. Говорим, что автомат распознает класс С, если при запуске этого автомата в любой лабиринт ЬЩ) происходит переход в заключительное состояние др1 только тогда, когда ЬУо € С, и для любого лабиринта Ь'п € С происходит переход в заключительное состояние др0.
Пусть V = {К С Ъ2 \К - связное конечное множество такое, что множество Ъ2\К связное}.
Если К € V, то границей К будем называть множество дК = {г € К\ существует точка г' € Ъ2\К такая, что г и г' - слабо соседние}. Вокруг каждой точки г = (г1, г2) € дК рассмотрим квадрат со стороной длины 1. Его стороны обозначим через а, в, 7, 6 (рис. 2).
Самая нижняя и самая правая точка (НП-точ-ка) множества К есть точка г = (г1,г2) € К, такая, что для каждого а = (а1,а2) € К, а = г, г2 < а2 или, если г2 = а2, то г1 > а1. Аналогично, НЛ, ВП, ВЛ точка множества К есть, соответственно, самая нижняя и самая левая, самая верхняя и самая правая, самая верхняя и самая левая точка множества К.
Пусть - множество сторон квадрата , для которых сторона находится между точками множества К и множества Ъ2 \ К. Фигура
Гк = и зЬг представляет собой прямоуголь-
гедК
ный многоугольник.
Пусть Б1-1 = {{1,-1}к\ к > 4} - конечное множество {1, —1} наборов. Пусть (5)* - множество всех слов з = з(1)з(2)... з(к), к > 4, над алфавитом 5 = {1, —1}. Определим отображение / : V —^ (5)* следующим образом. Пусть К € V. Обходя многоугольник Гк в положительном направлении, начиная от самой нижней и самой правой точки, сопоставим вершине Г к
1 п значение —1, если угол в вершине равен —, и
1 —п
значение 1, если угол в вершине равен .
а
7
в
х = (х1, х2) € Я \г! — - <
1 1'
< х! < г! + 2, х2 = г2 + 2
в = { х = (х1, х2) € Я2 \ г! — 1 <
1 1
< х! < г! + 2, х2 = г2 — ^
х = (х1, х2) € Я2 \ х! = г! — 1, 1 1 ' г2 — 2 < х2 < г2 + ^,
6 = ^ х = (х1, х2) € Я2 ! х! = г! + 2,
1 1 '
г2 — 2 < х2 < г2 + 2
Рис. 2. Квадрат для точки г.
Определим следующие семейства множеств (рис. 3):
Ф1 = {Р € V\ \Р\ > 2, /(Р) = ( — 1, ( — 1,1)™, —1,
—1, (1, —1)к, —1),к,п > 0},
Ф2 = {Р € V\ \Р\ > 2, /(Р) = (—1, (1, —1)™, —1,
—1, (1, —1)к, —1),к,п > 0},
Фз = {Р € V\ \Р\ > 2, /(Р) = (—1, (—1,1)™, —1,
—1, (—1,1)к, —1),к,п > 0},
Ф4 = {Р € V\ \Р\ > 2, /(Р) = (—1, (1, —1)™, —1,
—1, (—1,1)к, —1),к,п > 0},
где (а, Ь)™ - это последовательность, состоящая из пары (а, Ь), повторенной п раз.
Если гj = (х^,yj) € Ъ2, j = 1,2,3,4, обладают свойством у2 = у3, у1 = у4, у1 < < у2, введем обозначение: Аф,'г2'гз'г4 = {К € € Фг\г1,г2,г3,г4 являются НП, ВП, ВЛ, НЛ точками К, соответственно}, г € {1,2,3, 4}.
Определим класс Со.
Пусть гг = (хг, уг) € Ъ2, г = 1,..., 16, обладают свойством 0) (рис. 4).
6
(-1, (-1,1)4, -1, -1, (1, -1)3, -1) (-1, (1, -1)2, -1, -1, (1, -1)3, -1)
¿8
Свойство 0):
уд = у1б = уи = У2,
х9 < х1а < х11 — 1, х11 < х2,
у4 >у3 > у2, у7 = у14 = у13 = У4, х7 < х14 < х13 — 1, х13 < х4, „ у7 > уз > уд.
Пусть к^1--16 = {К\К = КО и К2О и К3ои иК0 и К0 и К0}, причем К00 € Лф1'*2'*9'*10, КО €
^ Лг2,г'з,х12,^11 КО £ Л*3'*4'*13,*12 К^О £ Л*4
К € Л*5'*14'*7'38, К°% Л^6'*16'^9; если х1 = = хю, то ¿1 + (1,1) € КО и ¿1 + (—1,1) € КО; если ¿з + (0,1) € КО и ¿з + (0, —1) € КО, то ¿3+ +(—1,1) € КО и ¿3 + (—1,1) € КО; если х5 = ха, то г5 + (1, —1) € КО и г5 + (—1, —1) € КО; након
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.