Евристичні методи розробки алгоритмів

Метод повного перебору

Рішення зворотної задачі

Іноді зворотне завдання, т. е. завдання, що відповідає функції f, - 1(Y)=X, вирішується значно простіше, ніж початкове завдання. Тоді наявний алгоритм рішення зворотної задачі R іноді можна використовувати для побудови алгоритму рішення прямої задачі Р._

Коли говорили про рішення задачі обчислення f(X) шляхом декомпозиції функції f або розбиття початкових даних X на частини, то малося на увазі, що існують математичні результати або інші підстави для таких перетворень. Інакше кажучи, завдання аддитивне - її рішення може бути отримане об'єднанням рішень приватних завдань.

У ряді випадків це не так. Розглянемо, наприклад, завдання про рюкзак.

Дані ціле ненегативне число N і k чисел {n1, n2, n3,..., nk}; знайти підмножину в {n1, n2, n3,..., nk}, сума чисел якого рівна N, якщо така підмножина існує.

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

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

Складність полягає в тому, що зі збільшенням кількості вихідних даних (переході від k до k+1) швидко збільшується необхідне число перевірок. При k = 10 їх буде 1024, а при k = 40 вже більше 1012.

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

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

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

В якості прикладу можна привести завдання розфарбовування вершин графа: розфарбувати вершини графа так, щоб суміжні вершини були розфарбовані в різні кольори, а кількість використаних в графі фарб була мінімальною.

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

Дата добавления: 2014-11-08