МОДЕЛІ и методи Прийняття РІШЕНЬ
(реферат)
1. Планування цілеспрямованіх Дій и Прийняття РІШЕНЬ
1.1 Оптімізаційні задачі
Інтелектуальна система спочатку Аналізує зовнішню сітуацію, потім планує цілеспрямовані Дії и пріймає решение про вибір певної Дії.
Широкий клас Завдання у рамках Прийняття решение можна сформулюваті у вігляді класичної оптімізаційної задачі: Знайте решение, за Яким цільова функція досягає максимуму при завданні обмеження. Оптімізацій ні задачі є предметом науки "Дослідження операцій". p> Формально оптімізацій на завдання опісується у вігляді:
найти решение х = (х 1 , ... х n ), для Якого цільова функція f (x) досягає максимуму (або мінімуму) i задовольняються обмеження g i (x)> = 0.
Приклад. Мандрівник збірається у дорогу. ВІН может взяти в рюкзак ПЄВНЄВ кількість x i предметів різніх тіпів. Нехай є n тіпів предметів, наявна кількість і-го предмета стає r и . Кожний предмет має ВЛАСНА Цінність c i та Вагу q i . Потрібно зібраті рюкзак таким чином, щоб сумарна Цінність узятіх предметів булу максимальна, альо щоб сумарная вага НЕ перевіщувала Межі u.
математичность завдання про рюкзак формулюється так: Знайте х = (х 1 , ... х n ), для Якого та задовольняються обмеження, де x i - цілі числа, x i > = 0; x i <= r i .
Будь-який елемент х, что задовольняє обмеженності g i (x)> = 0, назівається допустимих рішенням задачі. Если Умова максімізації НЕ вісувається, то йдет про задачу поиска допустимих РІШЕНЬ. Если обмежень немає, то йдет про Безумовно оптімізацію.
Если нужно вірішіті завдання мінімізації, то вона переводитися до задачі максімізації зміною знаку в цільовій Функції.
перелогових від вигляд цільової Функції та обмежень розрізняють:
1) Лінійне програмування - цільова функція и обмеження лінійні;
2) нелінійне програмування - цільова функція и обмеження нелінійні;
3) дискретності програмування - ВСІ х и є цілімі числами (як у задачі про рюкзак).
Розглянемо основні методи Вирішення оптімізацій них завдань
1.2 Метод перебору
Метод полного перебору - це Очевидне і універсальний метод Вирішення оптімізаційніх завдань, ЯКЩО множини допустимих РІШЕНЬ М обмеже. Метод є точним, тоб гарантує оптимальний розв'язок.
Недолік перебору - Для практичних завдань кількість варіантів Надто велика. p> Іноді можна пожертвуваті точністю розв'язку и найти субоптимального решение за рахунок значного Зменшення годині розрахунку. У цьом Полягає суть еврістічніх алгорітмів.
2. Еврістічній поиск на
Еврістічній поиск на - Процедура систематизованого перебору варіантів. Загальна схема методу така:
1. Вібрато Певного дію з области можливіть Дій
2. Здійсніті дію, что приведе до Зміни сітуації.
3. Оцініті нову сітуацію.
4. Если досягнутості успіху - Кінець, інакше повернути на крок 1.
Здійсніті дію можна реально (стратегія СПРОБА и помилок) або уявно (планування).
Одним з ВАЖЛИВО варіантів еврістічного поиска є метод послідовніх поліпшень.
2.1 Експоненційна складність еврістічного ПОШУК
Розглянемо складність решение оптімізацій них завдань на прікладі задачі про віконуваність булевого вирази, яка формулюється так: для будь-якого вирази від n змінніх найти хочай б один набор значень (x 1 , ... x n ), для Якого вирази пріймає Значення 1. p> Найпростіша схема еврістічного поиска така: Надаємо Одне з можливіть значення (0/1) першій, Другій и т.д. зміннім. После встановлення значень всех змінніх перевіряється Значення вирази: 1 - завдання вірішена, що не 1 - повернути на качан.
Таку задачу можна розглядаті як завдання поиска на ПЄВНЄВ дереві перебору. Кожна вершина цього дерева відповідає ПЄВНЄВ набору встановленного значень x 1 , ... x k . Ми можемо Встановити змінну x k +1 в 0 або в 1, тоб маємо вибір з двох Дій. Тоді Кожній з ціх Дій відповідає одна з двох дуг, Які Йдут від цієї вершини. Тоб вершина (x 1 , ... x k ) має двох нащадків (x 1 , ... x k , 0 ) і (x 1 , ... x k , 1).
При n = 3 дерево перебору/можливіть/матіме вигляд (рис.1).
Рис.1. Дерево перебору (вершини - значення змінніх, дуги - решение), зафарбовані вершини відповідають вирази (х 1 х 2 ) = х 3
З рис.1 видно, что Вирішення задачі зводіться до перебору листів (гілок) дерева з пошуку набор...
