47654 (Моделі і методи прийняття рішень)

20

Моделі і методи прийняття рішень

(реферат)

1. Планування цілеспрямованих дій і прийняття рішень

1.1 Оптимізаційні задачі

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

Широкий клас завдань у рамках прийняття рішення можна сформулювати у вигляді класичної оптимізаційної задачі: знайти рішення, за яким цільова функція досягає максимуму при заданих обмеження. Оптимізацій ні задачі є предметом науки „дослідження операцій”.

Формально оптимізацій на задача описується у вигляді:

знайти рішення х=(х₁, ...х_n), для якого цільова функція f(x) досягає максимуму (або мінімуму) і задовольняються обмеження g_i(x)>=0.

Приклад. Мандрівник збирається у дорогу. Він може взяти в рюкзак певну кількість x_i предметів різних типів. Нехай є n типів предметів, наявна кількість і-го предмета становить r_і. Кожний предмет має власну цінність c_i та вагу q_i. Потрібно зібрати рюкзак таким чином, щоб сумарна цінність узятих предметів була максимальною, але щоб сумарна вага не перевищувала межі u.

Математично задача про рюкзак формулюється так: знайти х=(х₁, ...х_n), для якого та задовольняються обмеження , де x_i - цілі числа, x_i>=0; x_i<=r_i.

Будь-який елемент х, що задовольняє обмеженням g_i(x)>=0, називається допустимим рішенням задачі. Якщо умова максимізації не висувається, то йдеться про задачу пошуку допустимих рішень. Якщо обмежень немає, то йдеться про безумовну оптимізацію.

Якщо потрібно вирішити задачу мінімізації, то вона переводиться до задачі максимізації зміною знаку в цільовій функції.

Залежно від вигляду цільової функції та обмежень розрізняють:

1. лінійне програмування – цільова функція і обмеження лінійні;

2. нелінійне програмування - цільова функція і обмеження нелінійні;

3. дискретне програмування – всі х_і є цілими числами (як у задачі про рюкзак).

Розглянемо основні методи вирішення оптимізацій них задач

1.2 Метод перебору

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

Недолік перебору – для практичних задач кількість варіантів надто велика.

Іноді можна пожертвувати точністю розв’язку і знайти субоптимальне рішення за рахунок значного зменшення часу розрахунку. В цьому полягає суть евристичних алгоритмів.

2. Евристичний пошук

Евристичний пошук – процедура систематизованого перебору варіантів. Загальна схема методу така:

1. Вибрати певну дію з області можливих дій

2. Здійснити дію, що приведе до зміни ситуації.

3. Оцінити нову ситуацію.

4. Якщо досягнуто успіху – кінець, інакше повернутися на крок 1.

Здійснити дію можна реально (стратегія спроб і помилок) або уявно (планування).

Одним з важливих варіантів евристичного пошуку є метод послідовних поліпшень.

2.1 Експоненційна складність евристичного пошуку

Розглянемо складність рішення оптимізацій них задач на прикладі задачі про виконуваність булевого виразу, яка формулюється так: для будь-якого виразу від n змінних знайти хоча б один набір значень (x₁, … x_n), для якого вираз приймає значення 1.

Найпростіша схема евристичного пошуку така: надаємо одне з можливих значень (0/1) першій, другій і т.д. змінним. Після встановлення значень всіх змінних перевіряється значення виразу: 1 – задача вирішена, не 1 – повернутися на початок.

Таку задачу можна розглядати як задачу пошуку на певному дереві перебору. Кожна вершина цього дерева відповідає певному набору встановлених значень x₁, …x_k. Ми можемо встановити змінну x_k+1 в 0 або в 1, тобто маємо вибір з двох дій. Тоді кожній з цих дій відповідає одна з двох дуг, які йдуть від цієї вершини. Тобто вершина (x₁, …x_k) має двох нащадків (x₁, …x_k, 0) і (x₁, …x_k, 1).

При n=3 дерево перебору /можливостей/ матиме вигляд (рис.1).

Рис.1. Дерево перебору (вершини – значення змінних, дуги – рішення), зафарбовані вершини відповідають виразу (х₁х₂) = х₃

З рис.1 видно, що вирішення задачі зводиться до перебору листів (гілок) дерева з пошуком набору, що відповідає умові задачі. Для виразу (х₁х₂) = х₃ такими наборами будуть 000, 010, 100, 111.

Якщо n=3, дерево має 2³=8 листів. Тобто число варіантів експоненційно залежить від n (2ⁿ=exp(n ln2).

Не кожний перебірний алгоритм є експоненційним (алгоритм пошуку максимального елемента в масиві – лінійний).

Із збільшенням розмірності задачі будь-який поліноміальний алгоритм стає ефективнішим за експоненційний.

2.2 Пошук у глибину і у ширину

Є дві основні стратегії пошуку потрібної вершини на дереві:

1) пошук у ширину;

2) пошук у глибину (перебір з поверненнями, бектрекінг).

Процедура пошуку у ширину передбачає аналіз на кожному кроці нащадків усіх вершин (паралельна перевірка всіх можливих альтернатив).

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

На рис.2 показана послідовність перегляду вершин при пошуку в ширину, на рис.3 – пошуку в глибину.

Рис.2. Процедура пошуку в ширину

Рис.3. Процедура пошуку в глибину

Пошук в глибину (більш поширений) дозволяє зекономити пам’ять, оскільки при його реалізації не потрібно запам’ятовувати все дерево, а лише вершини, що мають відношення до поточної альтернативи.

2.3. Простір задач і простір станів

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

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

Дуги можуть мати мітки, які інтерпретуються як вартість або довжина відповідного переходу. Тоді вирішення задачі являє собою пошук шляху від початкового стану до цільового; при цьому типовою вимогою є оптимізація даного рішення (пошуку найкоротшого шляху).

Класичний приклад планування в просторі станів – задача комівояжера.

Планування в просторі задач передбачає декомпозицію початкової задачі на підзадачі, поки не буде досягнути зведення до задач, для яких вже готові алгоритми рішення. Таку декомпозицію можна уявити у вигляді І/АБО графа.

Існують також комбінації планування у просторі задач істанів.

2.4 Автоматний спосіб задання алгоритму

В комп’ютері вхідна послідовність бітів перетворюється у вихідну за допомогою логічних схем. Логічні схеми поділяються на комбінаційні схеми і схеми з пам’яттю (скінченні автомати).

У комбінаційних схемах значення вихідних змінних залежать лише від стану вхідних і не залежать від поточного стану схеми. Будь-яка комбінаційна схема реалізує булеву (0/1) функцію від своїх вхідних змінних.

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

Найуніверсальнішою моделлю комп’ютерних обчислень є машина Тьюринга.

Автомати мають пам’ять у вигляді стрічки і пристрій для читання з неї. Стрічка розбита на квадрати з символами. Автомат розглядає символи по черзі, виконує обчислення і розв’язує задачі.

Формально скінчений автомат описується так:

FA=0, F>

де Q=(q₁, q₂, …, q_n) - скінченна множина станів керування; A=(a₁, a₂, .., a_m) - вхідний алфавіт; b: Q*A→Q - функція переходів; q₀ - початковий стан; - множина заключних станів керування.

Приклад. Потрібно побудувати скінчений автомат який допускає тільки послідовності 0/1, при цьому в послідовності розпізнавання кількість одиниць повинна бути парною, а нулів – непарною.

Згідно з умовою задачі А складатиметься з символів 0, 1, #, де # позначатиме довільний символ, відмінний від 0 і 1. Тобто, А=.

Множину станів виберемо так:

Q=(q₁, q₂, …, q₅),

де q₀ - початковий стан;

q_{1 -} стан помилки;

q₂ - кількість нулів непарна, а одиниць – парна;

q₃ – кількість нулів і одиниць непарна;

q₄ – кількість нулів і одиниць парна;

q₅ – кількість нулів парна, а одиниць – непарна;

Згідно з умовою задачі F=2>

Функції переходів визначаються так:

Автомати зручно задавати таблично:

Рис.1. Табличне задання автомата

Рядки таблиці позначаються станами множини Q, а стовпці – символами вхідного алфавіту. Символ ← позначає заключні допустимі стани.

Графічний опис автомата полягає у побудові графа, де вершини q_i і q_j з’єднуються дугою a якщо виконується команда q_ia→q_j. Заключні допустимі вершини позначаються подвійним колом.

Рис.2. Графічне задання автомата

Спеціальним типом автомата є машина Тьюринга. Універсальна машина Тьюринга може обчислити будь-який інтуїтивний алгоритм.

3. Складність алгоритмів

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

Машини Тьюринга дозволяють обчислювати тільки рекурсивні функції.

Частково рекурсивні функції – визначена не при всіх значеннях аргумента.

Теза Тьюринга: Клас функцій, частково обчислюваних за Тьюрингом, збігається з класом частково рекурсивних функцій.

Теза Чорча: клас частково рекурсивних функцій збігається з класом частково обчислюваних функцій.

Теза Чорча еквівалентна тезі Тьюринга.

Моделі РАМ і РАСП