Geri İzleme Algoritması (BackTracking Algorithm)

Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde bir değerin aranması veya bir hedefe ulaşmak için kullanılan algoritmanın ismidir. Burada bir amaç bulunmalı ve amaca ulaşan çeşitli yollar arasından bir doğru seçim aranıyor olmalıdır.

Örneğin bulmacalarda sorulan klasik iki boyutlu labirentler geri izleme algoritmaları (back tracking algorithms) biçilmiş kaftandır. Bu tip örneklerde labirentin bir ucundan başlanır ve diğer ucuna kadar çeşitli yollar denenerek devam edilir. Şayet çıkmaz bir yola denk gelinirse, en son yol ayrımına kadar geri gelinip farklı bir yol seçilir.

Örneğin yukarıdaki şekilde başlangıçtan hedefe giden iki ayrı yol gösterilmiştir. Kırmızı yolda iki kere çıkmaz yolla karşılaşılmış ve geri dönülmesi gerekmiştir. Benzer şekilde diğer çıkmayan yollar da denenebilirdi ancak şans faktörüyle (ki labirenti dolaşan kişinin labirenti bilmediğini kabul ediyoruz) iki başarısız deneme ile sonuca ulaşılmıştır.

Yeşil yolda ise hiç başarısızlıkla karşılaşılmamış ve sonuca ulaşılmıştır. Tabi yeşil yolda kırmızı yol da hedefe varan en kısa yollar değildir. En kısa yolu bulmak için bütün alternatif yolların denenmesi ve nihayetinde en kısasının seçilmesi gerekir. Burada ne yazık ki bütün yolları denemek dışında en kısa yolu bulan başka bir algoritma hiçbir zaman yüzde yüz oranında başarı vaad etmez. Örneğin sezgisel bir algoritma (heuristic algorithm) kullanılarak belki bütün alternatifler denenmeden sonuç bulunabilir ancak en verimli sonuç olduğu garanti edilemez, her zaman için daha iyi bir yol bulunma ihtimali bulunur.

Bu yazı şadi evren şeker tarafından yazılmış ve bilgisayarkavramlari.com sitesinde yayınlanmıştır. Bu içeriğin kopyalanması veya farklı bir sitede yayınlanması hırsızlıktır ve telif hakları yasası gereği suçtur.

Geri izleme algoritmalarının klasik problemleri arasında bir tahtaya 8 veziri birbirini yiyemeyecek şekilde yerleştirmek, bir satranç tahtasındaki bütün kareleri dolaşan bir at hareketlerinin listelenmesi, sudoku ve benzeri bulmacaların çözümü gibi günlük örnekler sayılabilir. Ayrıca herhangi bir algoritmanın yaptığı denemeler bu çatı altında düşünülebilir. Örneğin doğal dil işleme çalışmalarında (natural language processing) sıkça kullanılan DCG yapısı başlı başına bir geri izlemedir.

JAVA ile basit bir labirent (maze) çözen kod yazmaya çalışalım. Örneğin labirentimiz 1 ve 0’lardan oluşsun ve aşağıdaki şekilde bir dosyada (örneğin maze.dat) bize veriliyor olsun:

1111111
0010010
1000011
1101011
1100000
1111111

Bu labirentte 0 ile işaretlenen yerlerin yol, 1 ile işaretlenen yerlerin duvar olduğunu kabul edelim. Ayrıca her zaman için 1,2 (yani sol üst köşeden) başladığımızı kabul edelim. Bu labirenti basit bir integer dizide (array) tutabiliriz.

int maze[][];

olarak tanımladığımızı düşünelim.

Bu labirent verildiğinde çözümü veren kodu kodlamaya çalışalım.

Öncelikle bu tip bir problemde çözüm olarak kullanacağımız yaklaşımı tasarlayalım. Her adımda 1’er yakındaki komşuları kontrol edebildiğimizi düşünelim. Örneğin 3,3 koordinatlarındaysak 2,3 ; 3,4 ; 3,2 ; 4,3 koordinatları görebildiğimiz koordinatlardır. Çözüm olarak bir sırayla bütün komşuları dolaşalım. Şayet komşulardan birisi gidilebilirse bu komşuya gidelim.

Yukarıdaki çözümde bir açık nokta fasid daire (kısır döngü) ihtimalidir. Bunu aşağıdaki örnek üzerinden düşünelim.

000

Örneğin iki komşu ve gidilebilen koordinat var. En soldakinde başladığımızı düşünelim. Sağa gidilebilir , öyleyse gidelim. Sağa geldiğimizde de sola gidilebilir. Öyleyse gidelim. Böylelikle sürekli bir sola bir sağa gidip dururuz. Bu problemin çözümü olarak ancak çıkmaz bir sapakla karşılaştığımızda geri dönme seçeneğini kullanmayı ve bunun dışında geldiğimiz koordinata geri dönmemeyi önerebiliriz.

Farklı bir problem ise bir yol ayrımına geldiğimizde ve yol ayrımında bir seçim yaptığımızda bu seçimden geri dönüp farklı alternatifleri denerken, denenmiş bir sapağın bir daha denenmemesidir.

Örneğin yukarıdaki şekilde sağdan gelip sola giden kırmızı yolda, yukarı ihtimali denenmiştir. Çıkmaz sapak olduğu anlaşılıp gerdi dönüldükten sonra tekrar yol ayrımına geri gelinir. Bu yol ayrımında artık çıkmaz sapak olduğu anlaşılan bu ihtimalin bir daha denenmemesi gerekir.

Bu durumda geldiğimiz yolu işaretlememiz gerekir. Çözüm olarak geldiğimiz yolu işaretlemek için geçtiğimiz yerlere 2 koyalım. İlk örneğe dönecek olursak şöyle bir manzarayla karşılaşabiliriz:

1111111
2212210
1222211
1101011
1100000
1111111

Yukarıdaki örnekte çıkmaz bir yol olsan sapak denenmiş ve bu durum 2 sayısı ile gösterilmiştir.

Şimdi bu seçim ve yol ayrımında karar durumunu çözmek için 4 ayrı if koşulu yazmamız gerekiyor:

Geldiğim yeri işaretle

if(sola gidilmemişse)

sola git;

else if(sağa gidilmemişse

sağa git;

else if(yukarı gidilmemişse)

yukarı git;

else if (aşağı gidilmemişse)

aşağı git;

Yukarıdaki algoritma başarılı bir şekilde çalışır ve geldiğimiz yöne gitmez çünkü geldiğimiz yolu işaretliyoruz ve artık gidilmemişse seçeneği doğru dönmüyor. Elbette gidilmemişse seçeneği gidilebilirse anlamını da taşımaktadır. Yani duvar olan bir koordinata gidilemeyeceğini kabul ediyoruz.

Diğer bir problem ise bir çıkmaz yol bulunduğunda veya bir yol ayrımına geri dönüldüğünde tam olarak geri nasıl dönüleceğinin belirlenmesidir. Bunun için veri yapılarının bize sunduğu imkanlardan yığın (stack) oldukça elverişlidir. Sebebi son denenen koordinatı şayet yığının tepesine koyarsak, yığından ilk aldığımız koordinat da son denediğimiz koordinat olur. Şayet denemelerimizi sırasıyla yığına koyarsak, geri dönme durumunda sadece yığından veri almamız (pop) yeterli olacaktır.

Yukarıdakiler ışığında bir labirent kodlamasına bu bağlantıdan ulaşılabilir.