Оптимізація додатків
У цій статті розглядаються два алгоритми, які дають хоч і наближене, але досить точне рішення задачі. Алгоритм, який при пошуку максимального значення деякої функції f(x) повертає результат, що є добутком фактичного значення (знайти яке може виявитися найскладнішим завданням) на деякий коефіцієнт "c" називається алгоритмом c-апроксимації (c-approximation algorithm).
Апроксимацію особливо зручно використовувати для вирішення NP-повних завдань, для яких відсутні відомі поліноміальні алгоритми рішення. У деяких випадках апроксимація використовується, щоб прискорити розв'язання задачі, коли деяка неточність цілком допустима, а для обчислення точного рішення потрібен значний час. Наприклад, алгоритм апроксимації зі складністю O(log n) може виявитися набагато кращим при великій кількості вихідних даних, ніж точний алгоритм, що має складність O(n 3 ).
Завдання комівояжера
Щоб виконати формальний аналіз, необхідно формалізувати завдання комівояжера. Нехай є граф з ваговою функцією w, яка надає ребрам графа позитивних значень - роль такої функції, наприклад, може грати відстань між містами. Вагова функція задовольняє правилу нерівності трикутника, яка залишається справедливою, якщо вважати, що шляхи між містами лежать на Евклідовій поверхні:
Завдання полягає в тому, щоб відвідати кожну вершину в графі (кожне місто на карті комівояжера) лише один раз і повернутися до початкової вершини (штаб-квартири компанії), щоб сума ваг ребер, що становлять маршрут руху, була мінімальною. Позначимо цю мінімальну суму як wOPT. (Як ми вже знаємо, точне розв'язання задачі є NP-повним.)
Алгоритм апроксимаціїдіє, як описано далі. Спочатку для графа будується мінімальне сполучне дерево (Minimal Spanning Tree, MST) із загальною вагою wMST. (Мінімальне сполучне дерево - це подграф, що включає всі вершини, що не утворює цикли і має мінімальну загальну вагу ребер з усіх можливих дерев.)
Чи можна сміливо стверджувати, що wMST = degA(v)? інакше алгоритм перейде до кроку 2. Підсумовуючи всі вершини, отримуємо: e(A, B) > degB(v1) + . + degB(vk) > degA(v1) + . + degA(vk) > 2e(A), тому що кожне ребро праворуч було підраховано двічі. Аналогічно, e(A, B) > 2e(B) і, відповідно, 2e(A, B) > 2e(A) + 2e(B). Звідси отримуємо 2e(A, B) > e(A, B) + e(A) + e(B), але справа знаходиться загальна кількість ребер у графі. Таким чином, кількість ребер, що перетинають кордон двох підмножин, буде не менше половини всіх ребер у графі. Кількість ребер, що перетинають кордон, не може бути більшою за загальну кількість ребер у графі, тому ми отримали 2-апроксимацію.
На закінчення слід зазначити, що алгоритм виконує кількість кроків, прямо пропорційне кількості ребер у графі. Щоразу, коли повторюється крок 2, кількість ребер, що перетинають кордон, збільшується як мінімум на 1. Оскільки кількість ребер, що перетинають кордон, обмежена загальною кількістю ребер, загальна кількість кроків також обмежена цим числом.