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.

Yorumlar

  1. attila

    merhaba şadi bey problemlerin en kısa yoldan çözümünü bulmak için mühendisler “Hesaplamalı Geometri” kullanıyormuş.size rica etsem bu konu hakkında bilmeyenleri tatmin edecek bilgi verir misiniz? Saygılarımla

  2. Şadi Evren ŞEKER Article Author

    bu bilgi yanlış. Yani geometrik problemlerin çözümü şeklinde düzeltirsek daha doğru olabilir. Örneğin 3 boyutlu çizim veya coğrafi bilgi sistemleri gibi problemlerde işe yararlar.
    Bu konu ile ilgili detaylı bir yazı yazar, yorumunuzuda buradan oraya taşırım (yorumun bu yazıyla ilgisi bulunmuyor).

    ilginiz için teşekkürler

  3. Emre

    hocam yaptığım algoritmada kuzey güney doğu batı kontrolu yapıyorum ama geldiği yöne geri gitmeme durumunu yapamadım…nasıl bir yol izlemem gerekir? yardımcı olursanız çok sevinirim=)

  4. Duygu

    Hocam gerçekten size çok teşekkür etmek istiyorum .Ben İstanbul Üniversitesindenim keşke gitmeyip kalsaydınız siz ve sizin gibi hocalara çok ihtiyacımız oluyor.Ve keşke her hoca sizin gibi Türkçe herkesin anlayabileceği şekilde paylaşımlar yapıp biraz faydalı olmaya ezberci olmamaya çalışsaydı.Gerçekten sizi takdir ediyor ve örnek alıyorum.Çalışmalarınızda başarılar dilerim.

Şadi Evren ŞEKER için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir