Tam seçmə və onun mürəkkəbliyi

7.1 Tam axtarış.

Tərif: Tam axtarış (brute force) — bu, bütün mümkün həllərin yoxlanılması və ən yaxşısının seçilməsi üsuludur. Bu, optimal həllin tapılmasına zəmanət verir, lakin çox vaxt yüksək hesablama mürəkkəbliyi səbəbindən səmərəsizdir.

Nümunə: Kommi Voyajer məsələsini (Travelling Salesman Problem, TSP) nəzərdən keçirək. Burada bütün şəhərlərdən keçən və başlanğıc şəhərə qayıdan ən qısa yolu tapmaq tələb olunur. Tam axtarış bütün mümkün marşrutların permutasiyalarını yoxlamaqdan ibarətdir, bu isə faktorial vaxt mürəkkəbliyinə malikdir O(n!).

Üstünlüklər:

• Reallaşdırmanın sadəliyi.
• Optimal həllin tapılmasına zəmanət.

Çatışmazlıqlar:

• Yüksək hesablama mürəkkəbliyi.
• Böyük ölçülü məsələlər üçün qeyri-praktiklik, yoxlamaların eksponensial artımı səbəbindən.

TSP üçün Python nümunəsi:

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
            
# İstifadə nümunəsi
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"Ən yaxşı yol: {best_path} minimal məsafə ilə: {min_distance}")
        

7.2 NP sinfinə aid məsələlər

NP sinfi (nədənsiz polinomial) məsələləri əhatə edir, bunların həllini polinomial vaxtda yoxlamaq mümkündür. Amma həllin tapılması eksponensial vaxt tələb edə bilər.

İnsan dilində desək: NP-məsələlər — elə məsələlərdir ki, ən yaxşı həll yolunu yalnız bütün variantları tam yoxladıqdan sonra tapmaq olar (eksponensial vaxt). Amma tapılmış həllin ən yaxşı olduğunu daha sürətli yoxlamaq mümkündür (eksponensial vaxt tələb etmir).

Əsas xüsusiyyətlər:

• Həllin yoxlanması: Əgər məsələyə mümkün həll verilirsə, onun düzgünlüyünü polinomial vaxtda yoxlamaq olar.
• NP-dolğun məsələlər: NP sinfinin alt sinfi olan bu məsələlər NP-də ən çətin məsələlərdir. Əgər bir NP-dolğun məsələni həll etmək üçün polinomial algoritm mövcuddursa, onda NP sinfinə aid bütün məsələləri polinomial vaxtda həll etmək olar.
• NP-çətin məsələlər: Çətinliyi NP sinfinə aid hər hansı məsələnin çətinliyindən az olmayan məsələlərdir.

NP-dolğun məsələlərin nümunələri:

• Səyyah-satıcı məsələsi (Travelling Salesman Problem, TSP): Bütün şəhərlərdən keçən ən qısa yolu tapmaq.
• Çantanın məsələsi (Knapsack Problem): Məlum çəkisi keçmədən maksimum dəyər gətirən əşyalar dəstini tapmaq.
• Təpələri örtmə məsələsi (Vertex Cover): Bütün qraf kənarlarını örtən minimal təpələr çoxluğunu tapmaq.
• Boolean formulların ödənilməsi məsələsi (Boolean Satisfiability Problem, SAT): Boolean formulu təmin edən dəyişənlər dəstinin olub-olmadığını müəyyən etmək.

7.3 Çətin məsələlərin həllinə yanaşma tövsiyələri

Daha yaxşı həll üçün qeyri-adekvat vaxt tələb olunursa, adekvat vaxtda kifayət qədər yaxşı həll tapmaq tam mümkün ola bilər.

Yaxınlaşdırıcı alqoritmlər:

• Yaxınlaşdırıcı alqoritmlərdən istifadə edin. Bu alqoritmlər həmişə optimal olmasa da, məqbul vaxtda yaxşı nəticələr verə bilər.
• Nümunə: Fraqmentik əşyalar üçün riyazı yolun greedy alqoritmi.

Evristiklər:

• Çətin məsələlərin yaxınlaşdırıcı həllərini tapmaq üçün qarışqa koloniyalarına əsaslanan alqoritmlər, genetik alqoritmlər və süni intellekt alqoritmləri kimi evristiklərdən istifadə edin.

Məsələlərin bölünməsi üsulları:

• Məsələləri daha kiçik alt problemlərə bölün və onları ayrıca həll edin.
• Nümunə: Dinamik proqramlaşdırma ilə riyazı yol məsələsi.

Polynomial alqoritmlərin istifadə edilməsi:

• Mümkündürsə, alt problemlərin həlli və ya qismən həllər üçün polynomial alqoritmlər istifadə edin.
• Nümunə: Qrafda ən qısa yolu tapmaq üçün Dijkstra alqoritmi.

Tam axtarış və NP sinfi məsələləri alqoritm və hesablama mürəkkəbliyi nəzəriyyəsində vacib konsepsiyalardır. Tam axtarış optimal həll təmin etsə də, böyük məsələlər üçün tez-tez qeyri-praktikdir. NP sinfi məsələlərinə adekvat vaxtda yalnız evristiklər və yaxınlaşdırıcı metodlar vasitəsilə həll tapıla bilən bir çox vacib məsələlər daxildir.