![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Ієрархічні кольорові сітки Петрі
Перш, ніж визначити ієрархічну кольорову сітку Петрі введемо наступні поняття. Визначення 3.1. Перехід tI у КСП N = (P, T, W, F, H, l, y, m0) називається джерелом, якщо " p Î P: F (p, tI) = 0, тобто у перехід tI не входить ні однієї дуги. Визначення 3.2. Перехід tS у КСП N називається стоком, якщо " p Î P: H (tS, p) = 0, тобто з переходу tS не виходить ні одна дуга. Визначення 3.3. КСП N, що зображується зв’язним графом щонайменше з одним джерелом і з одним стоком, називається блоком. Визначення 3.4. Зв’язувальною сіткою NS щодо блока N називають таку КСП, що утворюється з блока N додаванням до нього позиції p 0, яка називається нульовою позицією, і дуг, що ведуть з p 0 в усі джерела і з усіх стоків в p 0. Таким чином, зв’язуюча сітка NS немає жодного джерела tI і жодного стоку tS. Приклад блока з джерелом t 4, t 6 і стоками t 5, t 7 і відповідна цьому блоку зв’язуюча сітка зображені на рис. 3.11. Визначення 3.5. Нульовим маркуванням зв’язувальної сітки NS блока N називають таке маркування m0(p 0, w), де в нульовій позиції p 0 є по одному маркеру всіх кольорів, а всі інші позиції порожні; відповідне їй маркування блока називають “порожнім”, тобто " p Î N, " w Î W: m(p, w) = 0; " p Î NS, " w Î W $ p 0 Î NS: m(p 0, w) = 1. Визначення 3.6. Блок N називається коректно сформованим, якщо: - його зв’язувальна сітка NS при початковому нульовому маркуванні m0(p 0, w) безпечна в цілому (по всіх кольорах), тобто " p Î NS, " wÎ W: m(p, w) £ 1; - будь-яка послідовність спрацьованих переходів, яка реалізована в блоці з порожнього початкового маркування m0(p 0, w), закінчується порожнім маркуванням тільки за умови, якщо кількість спрацювань переходів tI і tS однакова; - як початкові маркування m поч (p, w) використовуються лише такі, для яких мають місце співвідношення:
а – сітка у вигляді блоку; б – зв’язувальна сітка Звичайно передбачається, що ніякі два переходи в сітці Петрі не можуть спрацьовувати одночасно. На відміну від цього, для деяких переходів не тільки допускається одночасне спрацьовування, але, навпаки, забороняється неодночасне спрацьовування. Такі переходи утворюють перехід-зв’язку. Визначення 3.7. Переходом-зв’язкою називають підмножину переходів Спрацьовування переходу-зв’язки У сітці Петрі переходи-зв’язки завжди можна замінити простими переходами. Приклад сітки Петрі з переходами-зв’язками а) б) Рис. 3.12. Сітка Петрі з переходами-зв’язками (а) і простими переходами (б) За допомогою переходів-зв’язок легко відображати зв’язки між алгоритмами, підалгоритмами та операторами. Використовуючи наведені поняття, дамо визначення ієрархічної кольорової сітки Петрі (ІКСП). Визначення 3.8. Ієрархічною кольоровою сіткою Петрі називається набір Відношення Рис. 3.13. Ієрархічна кольорова сітка Петрі: а – дерево відношення; б – зображення сітки Для будь-яких двох сіток Nи і Nv, що відповідають початковій і кінцевій вершинам дуги дерева відношення сітки N*, присутня особлива позиція dv Í Nи, що називається дублером блока Nv. Позиція-дублер блока Nv в ІКСП зображається подвійним кругом із символом dv. Блок Nv дублюється позицією-дублером dv, що належить тільки сітці Nи. Таким чином, індекси дублера і дублюючого ним блока завжди збігаються. Між вхідними (вихідними) переходами дублера і джерелами (стоками) дублюючого ним блока має місце взаємнооднозначна відповідність. При цьому кожен вхідній (вихідний) перехід дублера і співставлене йому джерело (стік) у дублюючому блоці входять в один перехід-зв’язку. У старшій ІКСП, показаній на рис. 3.13, б, містяться дублери d 1 і d 2 блоків N 1 і N 2, у блоці N 1 – дублери d 1 і d 4 блоків N 3 і N 4, у блоці N 2 – дублер d 5 блока N 5, у блоці N 3 – дублер d 6 блока N 6. У ІКСП існують наступні переходи-зв’язки:
причому вхідному переходу Визначення 3.9. Початкові маркування блоків Ni і старшої сітки N 0 в ІКСП N = { Ni } погоджені наступним чином: - якщо всі позиції дублюючого блока порожні, то в дублері маркер відсутній, тобто
- якщо не всі позиції дублюючого блоку порожні, то в дублері знаходиться маркер того ж кольору, що й у дублюючому блоці і, крім цього,
Для алгоритмів управління ГВС позиції-дублери ІКСП означають наступне: кожному дублеру відповідає підалгоритм, що є алгоритмом, опис якого задається дублюючим блоком. Якщо в дублюючому блоці міститься свій дублер, то йому також відповідає підалгоритм, але вже більш низького рівня складності, і так доти, поки якому-небудь дублеру не буде відповідати оператор. Співвідношення алгоритмів за складністю визначається деревом відношень: рівень складності підалгоритму тим вищий, чим ближче до кореня дерева знаходиться сітка, яка містить дублер, що відповідає цьому підалгоритму. Як підалгоритми алгоритму управління ГВС можна виділити алгоритми управління АТСС, роботом-штабелером, автономним транспортним модулем тощо. Таким чином, ієрархічна сітка Петрі дозволяє у явному вигляді відбивати ієрархію операторів в алгоритмах управління ГВС і використовувати її при описі алгоритмів. З метою модифікації застосуємо до ІКСП дві операції: заміщення дублера блоком і заміщення вузла дублером. Операція заміщення дублера блоком полягає в наступному: сітка з дублером, що заміщається, поєднується з дублюючим блоком шляхом заміни відповідних переходів-зв’язок еквівалентними їм простими переходами; з отриманої сітки віддаляється позиція-дублер разом з інцидентними з нею дугами. Приклад виконання цієї операції наведений на рис. 3.14. Ієрархічна сітка (рис. 3.14, а) після об’єднання сітки, що містить дублер d 1, з дублюючим блоком N 1 перетворюється в сітку, зображену на рис. 3.14, б. Після видалення позиції d 1 та інцидентних їй дуг отримаємо сітку, показану на рис. 3.14, в. В результаті послідовного заміщення дублерів (у довільному порядку) з вихідної ІКСП виходить проста сітка. Зміст операції заміщення дублера полягає в тому, що, маючи множину операторів у підалгоритмах у вигляді окремих блоків і застосовуючи суперпозицію, можна побудувати алгоритм управління ГВС у вигляді простої сітки Петрі. Операція заміщення локалізованого вузла є оберненою до операції заміщення дублера і дозволяє з простої сітки Петрі отримати ієрархічну. а) б) в) Рис. 3.14. Ієрархічна сітка (а) і приклад операцій заміщення дублера (б) і вузла (в)
|