Bu eğitimde, geri izleme algoritmasının ne olduğunu öğreneceksiniz. Ayrıca, bir geri izleme yaklaşımı örneği bulacaksınız.
Geriye dönük izleme algoritması, istenen çıktıyı bulmak için kaba kuvvet yaklaşımı kullanan bir problem çözme algoritmasıdır .
Brute force yaklaşımı tüm olası çözümleri dener ve istenen / en iyi çözümleri seçer.
Geriye dönük izleme terimi, mevcut çözüm uygun değilse geri dönüp diğer çözümleri denemeyi önerir. Bu nedenle, bu yaklaşımda özyineleme kullanılır.
Bu yaklaşım, birden çok çözümü olan sorunları çözmek için kullanılır. Optimal bir çözüm istiyorsanız, dinamik programlamaya gitmelisiniz.
Devlet Uzay Ağacı
Bir uzay durum ağacı, bir başlangıç durumu olarak kökten uç durum olarak yaprağa kadar sorunun tüm olası durumlarını (çözüm veya çözümsüzlük) temsil eden bir ağaçtır.
Devlet Uzay Ağacı
Geri İzleme Algoritması
Backtrack (x) x bir çözüm değilse, x yeni bir çözümse false değerini döndürür, çözüm listesine ekleyin geri izleme (x'i genişletin)
Örnek Geriye Dönük Yaklaşım
Sorun: 2 erkek ve 1 kızı 3 bankta düzenlemenin tüm olası yollarını bulmak istiyorsunuz. Kısıtlama: Kız orta bankta olmamalıdır.
Çözüm: Toplam 3 tane var! = 6 olasılık. Tüm olasılıkları deneyip olası çözümleri alacağız. Tüm olasılıkları yinelemeli olarak deniyoruz.
Tüm olasılıklar:
Tüm olasılıklar
Aşağıdaki durum uzay ağacı olası çözümleri gösterir.
Tüm çözümleri içeren durum ağacı
Geriye Dönük Algoritma Uygulamaları
- Bir grafikte bulunan tüm Hamilton Yollarını bulmak için.
- N Queen sorununu çözmek için.
- Labirent çözme sorunu.
- Knight'ın tur sorunu.
