Навігація
Головна
 
Головна arrow Інформатика arrow Інформатика
< Попередня   ЗМІСТ   Наступна >

МЕТОД ПОВНОГО ПЕРЕБОРУ

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

Складність полягає в тому, що зі збільшенням кількості вихідних даних (при переході від до ) швидко збільшується необхідне число перевірок. Метод повного перебору застосуємо в тих випадках, коли шукане рішення належить деякій кінцевої області і може бути знайдена проста функція quality (Y) для перевірки правильності (або якості) обраного рішення. Тоді задача Р обчислення функції замінюється багаторазовим рішенням завдання R обчислення функції quality (стільки разів, скільки елементів є в області рішень). Причому в загальному випадку переглянути потрібно всю область, і порядок, в якому проглядаються елементи, не важливий.

ЕВРИСТИЧНІ МЕТОДИ РОЗРОБКИ АЛГОРИТМІВ

Під евристичними розуміються методи, правильність яких не доведена. Вони виглядають правдоподібними, здається, що в більшості випадків вони повинні давати вірне рішення. Іноді не вдається побудувати контрприклад, що демонструє хибність або неуніверсальність методу. Але не вдається довести математичними засобами і правильність методу. Проте практика використання евристичних методів дає позитивні результати.

ДИНАМІЧНЕ ПРОГРАМУВАННЯ

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

Часто не вдається розбити задачу на невелике число подзадач, об'єднане рішення яких дозволяє отримати рішення шуканих завдань. Можна спробувати розділити задачу на стільки завдань, скільки необхідно, потім кожну на ще більш дрібні і т.д. Іноді простіше створити таблицю вирішення всіх підзадач, незалежно від того потрібна вона чи ні. Заповнення таблиць - рішення підзадач для отримання вирішення певної задачі - в теорії алгоритмів отримало назву динамічного програмування. Форми алгоритмів динамічного програмування можуть бути різними, загальними можуть бути лише заповнені таблиці і порядок заповнення її елементів.

 
Якщо Ви помітили помилку в тексті позначте слово та натисніть Shift + Enter
< Попередня   ЗМІСТ   Наступна >
 
Дисципліни
Агропромисловість
Аудит та Бухоблік
Банківська справа
БЖД
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Нерухомість
Менеджмент
Педагогіка
Політологія
Політекономія
Право
Природознавство
Психологія
Релігієзнавство
Риторика
Соціологія
Статистика
Техніка
Страхова справа
Товарознавство
Туризм
Філософія
Фінанси
Пошук