Планування в просторі станів

1. Основні поняття теорії графів

Прийняття рішень на основі плану­вання в просторі станів передбачає побудову формалізованої моделі пред­метної області у вигляді графу станів, вершини якого відповідають мож­ливим ситуаціям (станам), а дуги – операціям, які дозволяють переходити від одного стану до іншого. Також очевидно, що вирішення багатьох інте­лектуальних задач пов'язане з діями над графами: орієнтованими і не-орієнтованими, циклічними і ациклічними, навантаженими і ненавантаженими. Часто такі маніпуляції вимагають знаходження вершини (вузла) або множини вершин, ребра або множини ребер, які задовольняють якійсь пев­ній умові. Наприклад, такими умовами можуть бути: знайти множину ребер графу, значення ваг яких менше за задану величину; знайти остове дерево графу; знайти остове дерево мінімальної вартості; знайти компоненти дво-зв'язності графу і т. п.

Визначити такі множини можна лише шляхом систематичної перевір­ки всіх вершин або ребер заданого графу. Фактично задача зводиться до пошуку в графі. Тому важливою компонентою багатьох алгоритмів на гра­фах є алгоритм пошуку обходу графу. Для будь-яких операцій з графом потрібно початкове його задання в пам'яті ЕОМ. Основними способами задання графу є: матриця інцидентності, матриця суміжності та списки су­міжності.

Однією зі структур даних, що найчастіше використовується в пpoгpaмуванні, є лінійні списки. Вони можуть бути задані за допомогою методів; послідовного або зв'язного зберігання. При виборі способу зберігання в конкретному випадку слід враховувати, які операції і в якій кількості вико­нуватимуться над лінійними списками.

Лінійний список – це скінченна послідовність однотипних елементів. Кількість елементів послідовності називають довжиною списку.

Списки залежно від організації зв'язку між елементами бувають однозвязаними (лінійними), двозв'язними (лінійними), двозв'язними (циклічними) іт.п.

Лінійний список L, що складається з елементів l₁,, l₂,..., l_n записувати­мемо у вигляді L = <l₁,, l₂,..., l_n> і зображатимемо графічно, як показано на рис.1.

Рис. 1. Графічне зображення списку

При роботі зі списками найчастіше використовуються такі операції: знайти елемент в списку із заданою характеристикою, вилучити певний елемент зі списку, внести елемент у спеціально визначене місце списку, виконати певні дії над елементами списку. В більшості мов програмування, за винятком мов, подібних до Ліспу або Прологу, не існує стандартних механізмів для задання лінійних списків.

Можна виокремити два основні методи задання лінійних списків: по­слідовне і зв'язне зберігання. Перше в більшості випадків реалізується за допомогою масивів, а друге – за допомогою динамічних змінних. При ви­борі засобів зберігання списку слід враховувати, які операції і з якою по­слідовністю виконуватимуться над ними. При використанні списку як ба­зової структури для побудови складніших структур даних, а також для економії пам'яті, використовується зв'язне зберігання лінійних списків з використанням динамічних змінних. Якщо ми організовуємо видалення та вставку елементів у список спеціальним чином, то отримуємо загально­прийняті в програмуванні структури даних типу стек, черга і т. п.

Стеком називається спеціально організований список, в якому занесен­ня і видалення елементів можна проводити тільки через один почат­ковий елемент, який називають вершиною стека.

Стек працює за принципом "останній зайшов — перший вийшов" (Last In First Out). Тому стек ще називають списком типу LIFO.

Чергою називають список, в якому всі вставки здійснюються в кінець списку (позначатимемо змінною rear), а всі видалення відбуваються з "голови" (початку) списку (позначатимемо змінною front).

Ці операції виконуються за принципом "перший зайшов — перший ви­йшов" (First In First Out), тому чергу ще називають списком типу FIFO.

При вирішенні конкретних задач можуть виникати й інші різновиди зв'язного зберігання.

Поняття граф вперше ввів до розгляду знаменитий математик Ейдер в 1736р. Граф G містить дві множини G = (V, Е), де V - множина вершин, Е — множина ребер. V є скінченною непустою множиною вер­шин (іноді їх називають вузлами), традиційно пронумерованою 1, 2, ..,_; n Е – скінченна множина пар вершин. Кожна пара із Е є ребром у G. Коди пари впорядковані, тоді графи називаються орієнтованими, в іншому ви­падку – неорієнтованими. Впорядковане ребро позначатимемо < i,j> а невпорядковане – (i,j).

У більшості випадків застосувань з множиною ребер графу пов'язують множину дійсних чисел, які називають вагами. Такий граф називають зваженим.

У неорієнтованому графі говоримо, що вершина i суміжна вершині j, коли існує ребро (i,j). Ступенем вершини назвемо число суміжних їй вер­шин. В орієнтованому графі виділяють півстепінь входу (число вхідних) та півстепінь виходу (число вихідних ребер з вершини).

Шляхом з вершини v_p до вершини v_q є послідовність вершин v_p, v_i1, v_i2,..., v_in, v_q, така що (v_p, v_i1), (­v_i1, v_i2),…, (v_in, v_q) є ребрами в Е (G). Довжиною шляху називають число ребер, які належать шляху. Простим шляхом називають шлях, в якому всі вершини, за винятком першої та останньої, є різними.

Циклом називають простий шлях, в якому перша та остання верши­ни збігаються. На рис.2 маємо орієнтований і неорієнтований графи з 6 вершинами і 6 ребрами.

Неорієнтований граф називають зв'язним, коли для довільної пари вер­шин існує шлях між ними.

Рис. 2. Зображення графу: а) орієнтованого; б) неорієнтованого