Geri İzleme Algoritması

Backtracking Algoritması Nedir?

Geri izleme, çözmek için olası kombinasyonları arayan bir algoritmadır hesaplama problemleri. Adayları kademeli olarak oluşturur ve verilen kısıtlamaları karşılamayanları kaldırır. Bu teknik, birden fazla olası sonuç arasından uygulanabilir bir çözüm seçmeniz gereken durumlarda çok faydalıdır.

Bu algoritma, Brute Force yaklaşımından daha iyi ve daha verimli olarak kabul edilir. Tüm olası çözümleri deneyen Brute Force'un aksine, Backtracking, verilen sonuca göre yalnızca bir nihai çözüm bulmaya odaklanır. kısıtlamalarıAyrıca son adımı geri alarak (geri izleme) ve çıkmaza ulaştıktan sonra başka bir seçeneği deneyerek zamandan ve bellekten tasarruf sağlar. Ek olarak, geçerli bir çözüm bulunur bulunmaz durur.

Geri izleme, karmaşık sorunları kapsamlı kaynak tüketimi olmadan çözebildiği için yaygın olarak kullanılan bir tekniktir. Sudoku, n kraliçe problemi ve zamanlama gibi çok sayıda kısıtlamanın karşılanması gereken sorunlar için özellikle yararlıdır. Geri izleme, olası çözümler arasında akıllıca gezinerek tüm koşulları karşılayan bir cevap bulabilir. Bu, hem hassasiyet hem de verimlilik gerektiren görevler için paha biçilmez hale getirir.

Geri İzleme Algoritması Nasıl Çalışır?

Geri izleme algoritmaları, adım adım geçerli çözümler bulmayı içeren bir problem çözme tekniğidir. Bir adımın kısıtlamaları belirli koşulları karşılamıyorsa, algoritma önceki adıma geri döner.

Daha sonra verilen kısıtlamaları karşılayan diğer olası kombinasyonlarla devam eder. Çok sayıda olası kombinasyon bulunduğundan, en tatmin edici seçeneklerden birini seçer ve sorunu sırayla çözer. Bu algoritmik teknik, bir veya daha fazla olası seçeneği çözmeniz gerektiğinde faydalıdır. Geri çekilme, geçerli bir çözüm üretmeyen bir durum ortaya çıktığında seçiminizi iptal etmek anlamına gelir.

Geri izleme algoritması bir problemi çözmek için genel olarak şu adımları izler:

Adım 1) Başlatma: Başlangıçta boş/kısmi bir çözümle başlayın.

Adım 2) Seçim: Belirli kriterlere ve kısıtlamalara bağlı olarak mevcut çözümü genişletmek için bir seçenek belirleyin.

Adım 3) Keşif: Seçilen adayı göz önünde bulundurarak ve problem çözme sürecinde ilerleyerek tekrarlı bir şekilde çözüme ulaşın.

Adım 4) Kısıtlama Kontrolü: Mevcut kısmi çözümün her adımda herhangi bir kısıtlamayı ihlal edip etmediğini kontrol edin. Eğer ihlal ediyorsa, önceki adıma geri dönün ve farklı bir aday deneyin.

Adım 5) Fesih:Geri izleme süreci geçerli bir çözüm bulunduğunda veya tüm kombinasyonlar tüketildiğinde durur.

Adım 6) Geriye Dönüş: Mevcut seçenek verilen sorunu çözmezse, önceki duruma döner. Daha sonra verilen sorunu çözmek için yeni seçeneği değerlendirir.

Adım 7) Tekrarla: Sorun çözülene veya tüm seçenekler denenene kadar bu adımlarla devam edin.

Geri İzleme Algoritmasının Tekrarlayan Yapısı

Geri izleme algoritmaları doğası gereği yinelemelidir. Bu, algoritmanın bir çözüm bulana veya tüm olasılıkları test edene kadar kendisini farklı parametrelerle çağırdığı anlamına gelir:

def find_solutions(n, other_params):
    if found_a_solution():
        increment_solutions_found()
        display_solution()
        if solutions_found >= solution_target:
            exit_program()
        return	

    for val in range(first, last+1):
        if is_valid(val, n):
            apply_value(val, n)
            find_solutions(n + 1, other_params)
            remove_value(val, n)

Geri İzleme Sorunlarıyla İlgili Genel Terimler

Backtracking tekniği ile ilgili bazı temel terimler şunlardır:

Çözüm Vektörü: Çözümleri (X1, X2, …, Xn) gibi n-li gruplar halinde gösterir.
Kısıtlamalar: X değerlerini sınırlayan kurallar, örtük ve açık.
Çözüm Alanı: Açık kısıtlamaları sağlayan tüm geçerli X değerleri.
Durum Uzay Ağacı: Çözüm alanını bir ağaç şeklinde gösterir.
Durum Uzayı: Durum uzay ağacındaki yolları tanımlar.
Sorun Durumu:Kısmi çözümleri temsil eden arama ağacındaki düğümler.
Çözüm Durumları: S'de geçerli çözüm ikilileri oluşturan durumlar.
Cevap Durumları: Kapalı kısıtlamaları karşılayın ve istenilen çözümleri elde edin.
Umut vadeden düğüm: İstenilen çözümlere ulaştırır ve uygulanabilirliğini korur.
Umut Vermeyen Düğüm: Daha fazla araştırılmayan, uygulanamaz durumlara yol açar.
Canlı Düğüm: Keşfedilmemiş çocuklarla oluşturuldu.
E-Düğüm: Devam eden çocuk üretimine sahip canlı düğüm.
Ölü Düğüm: Oluşturulan tüm çocukların daha fazla genişletilmesi söz konusu değildir.
Derinlik Öncelikli Düğüm Oluşturma: En son canlı düğümü bir sonraki E-düğüm olarak kullanır.
Sınırlayıcı Fonksiyon: Optimizasyon için B(x1, x2, …, Xa) değerini maksimize eder veya minimize eder.
Statik Ağaçlar: Sorun örneğinden bağımsız ağaç formülasyonu.
Dinamik Ağaçlar: Ağaç formülasyonu problem örneğine göre değişir.

Geri İzleme Algoritması Ne Zaman Kullanılır?

Karmaşık bir problemi çözmek için Geri İzleme tekniğini şu durumlarda seçebiliriz:

Birçok seçenek mevcut: Problem çözme sürecinin her adımında birçok seçenek varsa geri izleme uygundur. Bu seçenekler öğelerin ve hareketlerin seçimiyle ilgili olabilir.
Net bir en iyi seçim yok:Mevcut seçenekler arasından en iyi seçeneği belirlemek için yeterli bilgi olmadığında, Geri İzleme algoritmasından yararlanılabilir.
Karar daha fazla seçeneğe yol açar: Seçebilirsiniz Seçimleri sistematik olarak gözden geçirmek için geriye dönük izleme tekniği.
Tüm olası çözümleri keşfetmeniz gerekiyor: Geriye dönük izleme, birbirinin üzerine inşa edilmiş bir dizi karar alarak tüm çözümleri sistematik bir şekilde araştırır.

Geri İzleme Sorunlarının Türleri

Geri izleme algoritmalarında üç tip problem vardır: karar problemleri, optimizasyon problemleri ve numaralandırma problemleri. Aşağıda bunları öğrenelim.

Karar Problemi: Bu tür problemlerde amaç, uygulanabilir bir çözümün var olup olmadığını belirlemektir. "Evet" ve "hayır" yanıtlarını kontrol ederiz. Örneğin, n-kraliçe problemi. Birbirlerine saldırmadan n × n satranç tahtasına n tane kraliçe yerleştirme olasılığını inceleyen bir karar problemidir.
Optimizasyon Sorunu: Optimizasyon problemlerinde amaç, birçok seçenek arasından mümkün olan en iyi çözümü bulmaktır. Bu, belirli bir fonksiyon veya değişkenin maksimum ve minimum değerlerini belirlemeyi içerebilir. Örneğin, çantadaki eşyaların toplam değerini, ağırlık sınırına bağlı kalarak maksimize etmek olan sırt çantası problemini ele alalım.
Sayım Problemi: Amacı, verilen bir probleme olası tüm çözümleri bulmaktır. Herhangi bir eksiklik olmadan geçerli tüm seçenekleri listeliyoruz. Bir örnek, verilen bir karakter kümesinden olası tüm harf kombinasyonlarını üretmek olabilir.

Geri İzlemenin Uygulamaları ve Örnekler

Backtracking'in çeşitli uygulamaları vardır. Bunlardan bazıları aşağıda pseudo kodları ile açıklanmıştır.

Sudoku Solver: Bu problem, yinelenen sayılara sahip 3×3'lük bir alt ızgara içerir. Geri izleme tekniği, çözümün false döndürdüğünü gösterecek ve farklı bir sayı yerleşimine ihtiyaç olduğunu gösterecektir.

function solveSudoku(board):
    if no empty cells:
        return true  # Sudoku is solved
    for each empty cell (row, col):
        for num from 1 to 9:
            if num is valid in (row, col):
                place num in (row, col)
                if solveSudoku(board):
                    return true
                remove num from (row, col)
    return false  # No valid solution

N-Kraliçe Problemi:Geri izleme yaklaşımı, vezirlerin N × N boyutundaki bir satranç tahtasında birbirlerini tehdit etmeyecek şekilde nasıl sunulacağını belirler.

function solveNQueens(board, col):
    if col >= N:
        return true  # All queens are placed
    for each row in the column col:
        if isSafe(board, row, col):
            place queen at (row, col)
            if solveNQueens(board, col + 1):
                return true
            remove queen from (row, col)
    return false  # No valid solution in this branch

Alt Küme Toplamı Problemi: Belirli bir kümeden belirli bir hedef toplama ulaşan sayı alt kümesini bulmak için kullanılır.

function subsetSum(nums, target, index, currentSubset):
    if target == 0:
        print(currentSubset)  # Subset with the target sum found
        return
    if index >= len(nums) or target < 0:
        return
   currentSubset.add(nums[index])
   subsetSum(nums, target - nums[index], index + 1, currentSubset)
   currentSubset.remove(nums[index])
   subsetSum(nums, target, index + 1, currentSubset)

Hamilton Döngüsü Problemi:Geri izleme, her köşeyi tam olarak bir kez ziyaret eden bir grafikteki kapalı bir turu bulmak için uygulanabilir.
Labirentteki Sıçan Problemi:Geri izleme tekniği, bir sıçanın labirentin başlangıç noktasından çıkışa kadar izlediği yolu bulmak için kullanılır.

Geri İzleme Algoritmasının Avantajları ve Dezavantajları

Geri İzleme Algoritmasının Avantajları

Geri izleme teknikleri karmaşık sorunları çözmek için kullanılır. Birçok avantajı vardır:

Geri izleme tekniği kısıtlamaları ele almak için etkilidir.
Bu yöntem optimizasyon problemlerini çözmek için iyidir.
Bu teknik çeşitli tipteki problemlerde işe yarıyor.
Bu prosedür tüm olası çözümlerin gözden geçirilmesine yardımcı olabilir.
Geriye doğru gittiği için Bruteforce tekniğine göre daha fazla hafıza tasarrufu sağlar.

Geri İzleme Algoritmasının Dezavantajları

Geri izleme tekniklerinin de zaman karmaşıklığı gibi bazı sınırlamaları vardır. Bu tekniğin şu dezavantajları vardır:

Garantili bir çözüm yoktur.
Birçok kombinasyondan dolayı daha yavaştır.
Çok sayıda olasılık içermesi nedeniyle zaman karmaşıklığı yüksektir.
Gerçek zamanlı kısıtlamalar için uygun değildir, çünkü en iyi çözümü bulmak uzun zaman alabilir.
Verimlilik, problemin karmaşıklık düzeyine bağlıdır.

Geri İzleme ve Özyineleme Arasındaki Fark

Özyineleme	Geri İzleme
Temel duruma ulaşılana kadar kendini çağırır.	En iyi uygulanabilir sonuç bulunana kadar tüm olasılıkları gözden geçirmek için yinelemeyi kullanır.
Aşağıdan yukarıya yaklaşım.	Yukarıdan aşağıya yaklaşım.
Hiçbir değer atılmaz.	Uygulanamaz çözümler reddedilir.

Sonuç

Geri izleme, uygulanabilir çözümleri sistematik olarak araştırarak ve gerektiğinde geri izleme yaparak karmaşık sorunları çözmek için kullanışlı bir algoritmik stratejidir. Geri izleme tekniklerinin hesaplama gücü ve algoritmik verimlilikteki gelişmelerle gelişmesini bekleyebiliriz. Bu gelişmeler, daha büyük ve daha karmaşık sorunları verimli bir şekilde ele almalarına olanak tanıyacaktır.

Ayrıca, makine öğrenimi modelleri daha önce öğrenilen kalıplara dayanarak geriye dönük kararlara rehberlik edebilir.

Tüm bu teknolojik yenilikler, geri izleme algoritmalarını kökten değiştirecek ve onları çeşitli alanlardaki karmaşık sorunları ele almak için güçlü ve çok yönlü bir araç haline getirecek.