Geri İzleme
- İngilizcesi
- Backtracking
- Okunuşu
- bektreking
Günlük kullanımda iki ad da yaygın.
Kısaca
Geri izleme, çözümü her seferinde bir seçimle kuran ve çıkmaza girdiğinde son seçimi geri alarak başka bir seçenek deneyen bir arama tekniğidir.
Geri izleme (backtracking) nedir?
Geri izleme, bir problemin olası çözümlerini her kombinasyonu körü körüne denemeden arama yöntemidir. Aday çözümü adım adım, her seferinde bir karar vererek kurar ve her adımdan sonra kısmi çözümün hâlâ geçerli bir cevaba çıkıp çıkamayacağını kontrol eder. Çıkamıyorsa algoritma son kararı geri alır, bir adım geriye döner ve bir sonraki seçeneği dener.
Geri izleme genellikle seç, keşfet, seçimi geri al (choose, explore, unchoose) kalıbını izleyen özyinelemeli bir fonksiyon olarak yazılır: bir seçim yapın, problemin geri kalanını çözmek için özyineleyin, sonra bir sonrakini denemeden önce seçimi tersine çevirin. Olası tüm karar dizileri bir ağaç oluşturur ve geri izleme bu ağacı derinlik öncelikli gezer. Gücünü budamadan (pruning) alır: kısmi bir çözümü erken reddederek onun devamında gelecek seçimlerin tüm alt ağacını atlar. En kötü durum yine de üsteldir, ancak iyi bir budama gerçek problemleri çoğu zaman yeterince hızlı yapar.
Her zaman ilk açık dönüşü seçerek ve duvara çarptığınızda son kavşağa geri yürüyerek bir labirenti çözmek, geri izlemenin en saf halidir. Sudoku, bulmaca ve N-vezir problemi gibi kısıt bulmacaları, permütasyon ve kombinasyon üretme ve her seçimin bir kural listesine uyması gereken zamanlama problemleri için standart tekniktir. Birçok düzenli ifade (regular expression) motoru da eşleşmenin alternatif yollarını denemek için geri izleme kullanır; bu yüzden kötü yazılmış bir desen bazı girdilerde üstel sürebilir ve bu açık ReDoS (regular expression denial of service) olarak bilinir.
Geri izleme derinlik öncelikli aramayla yakından ilişkilidir ve ikisi sıklıkla karıştırılır. DFS zaten var olan bir çizgeyi gezmenin genel bir yoludur; geri izleme ise anında ürettiği bir seçimler ağacını keşfeder ve kuralları bozan her dalı terk eder. Ayrıca tekrarlanan alt problemleri sonuçlarını saklayarak yeniden çözmekten kaçınan dinamik programlamadan ve bir seçimi asla geri almayan açgözlü algoritmadan da farklıdır.
Önemli noktalar
- Geri izleme çözümü adım adım kurar ve çıkmaza götüren seçimleri geri alır.
- Genellikle özyinelemelidir ve seç, keşfet, seçimi geri al kalıbını izler.
- Geçersiz kısmi çözümleri erken budamak onu pratik kılan şeydir.
- En kötü durum üsteldir, ancak gerçek problemler çoğu zaman çok daha hızlıdır.
- Sudoku çözücüleri, N-vezir, permütasyon üreteçleri ve birçok regex motoru geri izleme kullanır.
Örnek
def solve_queens(n, placed):
# placed[r] is the column of the queen already placed in row r
row = len(placed)
if row == n:
return 1 # a queen in every row: one complete solution
count = 0
for col in range(n):
# Prune: skip columns and diagonals attacked by an earlier queen
if any(c == col or abs(c - col) == row - r for r, c in enumerate(placed)):
continue
placed.append(col) # choose
count += solve_queens(n, placed) # explore
placed.pop() # unchoose, then try the next column
return count
print(solve_queens(8, [])) # 92 solutions on a standard chessboardSık sorulan sorular
Geri izleme ile derinlik öncelikli arama arasındaki fark nedir?
Derinlik öncelikli arama, var olan bir çizge ya da ağacın düğümlerini gezer. Geri izleme aynı derinlik öncelikli sırayı ilerledikçe ürettiği bir seçimler ağacına uygular ve kısmi çözüm bir kuralı bozar bozmaz o dalı terk eder.
Geri izlemenin zaman karmaşıklığı nedir?
En kötü durumda üsteldir, hatta faktöriyeldir, çünkü seçimlerin her kombinasyonunu keşfedebilir. Budama pratikte işi çarpıcı biçimde azaltır, ancak en kötü durum sınırı genellikle üstel kalır.
Geri izleme hangi problemleri çözer?
Tipik örnekler sudoku ve diğer kısıt bulmacaları, N-vezir problemi, tüm permütasyonları ya da kombinasyonları üretme, bir labirentte yol bulma ve çok sayıda kural içeren zamanlama problemleridir.
İlgili sayfalar
- ÖzyinelemeProgramlamanın Temelleri, s. 42Özyineleme, bir fonksiyonun sorunu, basit bir temel duruma ulaşana dek aynı sorunun daha küçük sürümleri için kendisini çağırarak çözdüğü tekniktir.
- Derinlik Öncelikli AramaVeri Yapıları, s. 11Derinlik öncelikli arama, bir yolu gidebildiği kadar izleyip sonra geri dönerek sıradaki ziyaret edilmemiş dalı keşfeden bir çizge gezinme algoritmasıdır.
- Dinamik ProgramlamaVeri Yapıları, s. 13Dinamik programlama, bir problemi çakışan alt problemlere bölüp her cevabı saklayarak hiçbirini iki kez çözmeden problemi çözme tekniğidir.
- Açgözlü AlgoritmaVeri Yapıları, s. 1Açgözlü algoritma, önceki kararları yeniden düşünmeden her adımda o an en iyi görünen seçimi yaparak çözümü adım adım kuran bir algoritmadır.
- Düzenli ifadeProgramlamanın Temelleri, s. 17Düzenli ifade (regex), dizeler içinde aranacak, doğrulanacak, çıkarılacak veya değiştirilecek metni tarif eden, kompakt sözdizimli bir desendir.
- AğaçVeri Yapıları, s. 2Ağaç, kenarlarla bağlı düğümlerden oluşan hiyerarşik bir veri yapısıdır; en üstte tek bir kök düğüm ve altında dallanan çocuk düğümler bulunur.
Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin