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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

FA=<Q, A, b, q₀ , F>

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

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

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