Geri İzleme Algoritmaları
Geri izleme (backtracking), bir problem için olası tüm çözümleri adım adım keşfeden ve geçersiz çözüm yollarını eleme yöntemiyle ilerleyen bir algoritma stratejisidir.
N-Queens Problem
N adet veziri, birbirlerini tehdit etmeyecek şekilde N×N boyutundaki satranç tahtasına yerleştirme problemi.
Subset Sum Problem
Bir dizi içerisindeki sayıların alt kümelerinin toplamının belirli bir değere eşit olup olmadığını bulan algoritma.
Geri İzleme Algoritmaları Hakkında
Geri izleme, bir araştırma ağacını derinlemesine dolaşarak çözüm arayan bir problem çözme tekniğidir. Algoritma, her adımda bir seçim yapar ve bu seçimin sonuçlarını inceler. Eğer seçim kısıtlamaları ihlal ediyorsa, algoritma geri döner (backtrack) ve başka bir seçim yapar.
Bu yaklaşım, kombinatoryal problemlerde özellikle etkilidir. Örneğin; permütasyonlar, kombinasyonlar, bulmacalar ve oyunlar gibi çözüm uzayının büyük olduğu durumlarda kullanışlıdır.
Geri izleme algoritmaları genellikle rekürsif yapıdadır ve "kaba kuvvet" yaklaşımına göre daha verimlidir, çünkü geçersiz çözüm yollarını erken aşamada tespit edip elemek mümkündür.
Yaygın geri izleme kullanım alanları:
- Bulmacalar (Sudoku, Satranç, N-Queens, vb.)
- Kombinatoryal problemler (Subset Sum, Kombinasyon, Permütasyon)
- Labirent çözme
- Graf boyama ve diğer graf problemleri