Повний перебір і його складність

7.1 Повний перебір

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

Приклад: Розглянемо задачу комівояжера (Travelling Salesman Problem, TSP). Тут потрібно знайти найкоротший шлях, що проходить через усі міста і повертається в початкове місто. Повний перебір включає перевірку всіх можливих перестановок маршрутів, що має факторіальну часову складність O(n!).

Переваги:

• Простота реалізації.
• Гарантія знаходження оптимального рішення.

Недоліки:

• Висока обчислювальна складність.
• Непрактичність для задач великого розміру через експоненційне зростання кількості перевірок.

Приклад на Python для TSP:

import itertools

def calculate_distance(path, distance_matrix):
    return sum(distance_matrix[path[i - 1]][path[i]] for i in range(len(path)))
            
def tsp_brute_force(distance_matrix):
    n = len(distance_matrix)
    all_permutations = itertools.permutations(range(n))
    min_distance = float('inf')
    best_path = None
            
    for perm in all_permutations:
        current_distance = calculate_distance(perm, distance_matrix)
        if current_distance < min_distance:
            min_distance = current_distance
            best_path = perm
            
    return best_path, min_distance
            
# Приклад використання
distance_matrix = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]
best_path, min_distance = tsp_brute_force(distance_matrix)
print(f"Найкращий шлях: {best_path} з мінімальною відстанню: {min_distance}")
        

7.2 Задачі класу NP

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

Простими словами: NP-задачі — це такі задачі, краще розв'язання яких знаходиться тільки повним перебором всіх варіантів (експоненційний час). Але перевірити, що знайдене розв'язання найкраще, можна швидше (не експоненційний час).

Основні характеристики:

• Перевірка розв'язання: Якщо дано можливе розв'язання задачі, його коректність можна перевірити за поліноміальний час.
• NP-повні задачі: Підмножина задач класу NP, які є найбільш складними в NP. Якщо існує поліноміальний алгоритм для розв'язання хоча б однієї NP-повної задачі, то всі задачі з класу NP можуть бути розв'язані за поліноміальний час.
• NP-важкі задачі: Задачі, складність яких не менша складності будь-якої задачі з класу NP.

Приклади NP-повних задач:

• Задача комівояжера (Travelling Salesman Problem, TSP): Знайти найкоротший шлях, що проходить через усі міста.
• Задача про рюкзак (Knapsack Problem): Знайти набір предметів, максимізуючи цінність, не перевищуючи задану вагу.
• Задача про покриття вершин (Vertex Cover): Знайти мінімальну множину вершин, що покриває всі ребра графа.
• Задача про задоволення булевих формул (Boolean Satisfiability Problem, SAT): Визначити, чи існує набір змінних, що задовольняє булеву формулу.

7.3 Рекомендації щодо підходів до розв'язання складних задач

Якщо на краще рішення потрібен неадекватний час, цілком можливо за адекватний час знайти достатньо хороше рішення.

Алгоритми наближень:

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

Евристики:

• Використовуйте евристики, такі як алгоритми на основі мурашиної колонії, генетичні алгоритми та алгоритми штучного інтелекту, для знаходження наближених рішень складних задач.

Методи розбиття задач:

• Розбивайте задачі на менші підзадачі та розв'язуйте їх окремо.
• Приклад: Динамічне програмування для задачі про рюкзак.

Використання поліноміальних алгоритмів:

• Якщо можливо, використовуйте поліноміальні алгоритми для розв'язання підзадач або знаходження часткових рішень.
• Приклад: Дейкстра для знаходження найкоротшого шляху в графі.

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