3. Наближений алгоритм
Наближений алгоритм (алгоритм прямого перебору) передбачає в основі використання багаторазового ітераційного процесу побудови всіх можливих варіантів покриваючих дерев, аналіз їх вагових показників і вибір оптимального (з точки зору ваги) варіанту. При цьому в алгоритмі застосовується елемент випадковості (вибір напрямку руху виконується з використанням генератору довільних чисел).
Метод є наближеним, тому що не в змозі гарантувати стовідсоткову оптимальність отриманого результату, але за рахунок багато-ітераційного повторюваного проходження дає змогу перебрати практично всі можливі комбінації і вже на їх основі обрати оптимальне рішення (з максимальною вагою, довжиною, тощо).
Загальну схему алгоритму можна представити наступним чином:
- Побудова покриваючого дерева випадковим чином;
- Підрахунок ваги отриманого покриваючого дерева;
- Порівняння ваги покриваючого дерева з попереднім результатом, якщо вага більша – збереження отриманого дерева;
- Перехід до п.1.
Кількість таких ітерацій визначається певним коефіцієнтом («eps» у програмі) і визначається на етапі розробки алгоритму. Тривалість роботи алгоритму залежить від значення цього коефіцієнту та розміру графу (кількості вершин).
В кінці роботи алгоритму ми отримаємо покриваюче дерево з максимальною вагою.