Kod KâşifiMERAK ET. DENE. KEŞFET.Bir şey öğren

Yayıncı: Kod Kâşifi · Düzeltme bildir

Labirentte en kısa yolu bulmak

Bir labirentte çıkışı bulmakla çıkışa en kısa yoldan gitmek aynı şey değildir. Bilgisayar, yolları küçük parçalara ayırarak seçenekleri karşılaştırabilir.

Bahçe labirentindeki taşlı yollar, çıkışa giden farklı uzunlukları gösteriyor.
Yolları parçalara ayırıp uzunluklarını karşılaştırarak kısa rotayı bulabilirsin. Kod Kâşifi için üretilen yapay zekâ illüstrasyonu.

Çıkışı görmek, ona ulaşmak değildir

Bir labirent oyununda çıkış sağ üst köşede parlıyor. Sen de her fırsatta sağa ve yukarı gidiyorsun; hedefe yaklaşmış gibi görünüyorsun. Birkaç dönüş sonra karşına duvar çıkıyor. Oysa başlangıçta sola ayrılan yol, kısa bir dolambaçtan sonra çıkışa ulaşıyor olabilir. Mesafenin gözümüze nasıl göründüğü ile gerçekten yürünebilen yol aynı şey değildir. Bilgisayara rota buldurmak için önce labirentin geçitlerini açıkça anlatmamız gerekir.

Bir yol bulmak ile en kısa yolu bulmak arasında da fark vardır. Çıkışa ulaştığında oyun tamamlanabilir, ama arkadaşın aynı labirenti daha az adımla geçmiş olabilir. Bunu incelemek için yalnızca ilk başarılı denemeyi değil, başka yolların olasılığını da düşünmelisin. İşte algoritmalar burada yardımcı olur: Belirli kurallarla seçenekleri araştırır ve hangi koşullarda kısa yol bulduklarını açıklamamızı sağlarlar.

Labirentin küçük bir haritasını çıkar

Kavşakları noktalarla, aralarındaki açık geçitleri çizgilerle gösterebilirsin. Bu tür bir modele çizge denir. Noktaların kâğıtta tam olarak nerede durduğu şart değildir; hangi noktaların birbirine bağlı olduğu önemlidir. Bir oyun haritasını küçültüp yalnızca geçişleri gösterdiğinde, uzun koridorların süsleri kaybolur ama rota seçmek için gereken bağlantılar kalır. Böylece karmaşık görünen yer daha kolay incelenebilir hâle gelir.

Kareli kâğıtta farklı bir model de kullanabiliriz. Duvar olmayan her kare bir nokta, yukarı, aşağı, sağa veya sola komşu açık kareler de birer bağlantı olsun. Çapraz geçişe bu çalışmada izin vermiyoruz. Her geçiş bir adım sürüyor. Kuralları baştan yazmak önemlidir; çapraz hareketi sonradan serbest bırakırsan artık başka bir haritada başka bir soruyu çözmüş olursun.

Yakındaki seçenekleri önce araştır

Her geçişin eşit maliyette olduğu böyle bir haritada, genişlik öncelikli arama adı verilen yöntem kullanılabilir. İngilizce adının kısaltması BFS'dir. Başlangıçtan önce bir adım uzaklıktaki noktaları, sonra iki adım uzaklıktakileri, ardından üç adım uzaklıktakileri inceler. Bunu suya bırakılan bir taşın çevresinde genişleyen halkalara benzetebilirsin. Aynı uzaklık katmanındaki noktalar araştırılırken, henüz daha uzak katmana atlanmaz.

Sırayı tutmak için bir kuyruk kullanırız. İlk eklenen nokta, işlenme sırası geldiğinde önce çıkar; yeni bulunan noktalar kuyruğun sonuna eklenir. Ayrıca bir noktayı ilk bulduğumuzda işaretleriz. Böylece başka bir geçit bizi aynı noktaya getirse bile onu tekrar tekrar kuyruğa koymayız. İşaretlemek çıkmazları yok etmez; yalnızca zaten bildiğimiz noktaları gereksiz yere yeniden araştırmayı engeller.

Harfli haritada adım adım ilerleyelim

Altı noktadan oluşan bir harita kuralım: başlangıç S, çıkış T olsun; arada A, B, C ve D bulunsun. Açık geçitler S ile A, S ile B, A ile C, B ile D, C ile D ve D ile T arasında olsun. Geçitleri iki yönde de kullanabiliyoruz. Haritayı kâğıda çizerken bunun dışında çizgi ekleme; birazdan anlatılan kuyruk adımlarını bu bağlantılarla izleyeceğiz.

Başlangıçta kuyrukta yalnızca S var. S'yi çıkarıp A ve B'yi ilk kez buluyoruz; ikisini işaretleyip kuyruğa ekliyoruz. Kuyruk A, B oluyor. A'yı çıkarınca C bulunuyor ve sonuna ekleniyor; kuyruk B, C. B'den D'yi bulduğumuzda kuyruk C, D oluyor. A ve B başlangıçtan bir adım, C ve D ise iki adım uzaklıkta keşfedilmiş durumda.

Bulunan yolu geri sar

C'yi işlerken komşusu D'yi görüyoruz, fakat D zaten işaretli. Kuyruğa ikinci kez eklemiyoruz. Sonra D'yi çıkarınca T bulunuyor. Her yeni noktanın yanında, onu ilk hangi noktadan bulduğumuzu yazmıştık: A'nın yanında S, B'nin yanında S, C'nin yanında A, D'nin yanında B, T'nin yanında D var. Çıkışa varınca bu küçük notlar bize dönüş zincirini gösteriyor.

T'den geriye doğru T, D, B, S zincirini izler, sonra ters sırada okuruz: S, B, D, T. Bu rota üç geçişten oluşuyor. S, A, C, D, T yolu da çıkışa ulaşıyor, ama dört geçiş gerekiyor. Yöntem, çıkışı daha uzak katmana geçmeden keşfettiği için bu örnekte üç geçişlik kısa yolu bulur. Haritada aynı uzunlukta başka bir rota bulunması da mümkündür.

İlk bulunan yol her yöntemde en kısa olmaz

Bir başka yöntem, bir kolu mümkün olduğunca ileri takip edip sonra geri döner. Buna derinlik öncelikli arama, kısaca DFS denir. Haritamızda önce A koluna girerse S, A, C, D, T rotasını bulabilir. Bu bir çözümdür, fakat üç geçişlik yolu kaçırmış olur. İlk varılan çıkışı en kısa yol saymak bu nedenle doğru değildir; aramanın hangi kurallarla ilerlediğine bakmak gerekir.

Bu, derinlik öncelikli aramanın işe yaramadığı anlamına gelmez. Bağlantıları araştırmak gibi başka amaçlar için yararlıdır. Hangi yöntemi seçtiğimiz, çözmek istediğimiz soruya bağlıdır. Oyun için yalnızca ulaşılabilir bir çıkış arıyorsak farklı seçenekler kabul edilebilir; en az adımı istiyorsak bunun güvencesini sağlayan yönteme ihtiyacımız vardır. Algoritmanın adından çok, neyi garanti ettiğini ve hangi şartları kullandığını anlamak önemlidir.

Her adım aynı süreyi almıyorsa

Şimdi D ile T arasındaki geçidin çamurlu olduğunu ve beş dakika sürdüğünü düşün. Diğer geçitlerin hepsi bir dakika olsun. Artık yalnızca geçişleri saymak, yolculuk süresini karşılaştırmaya yetmez. Bir rota daha az geçit içerirken daha uzun sürebilir. Haritaya her geçidin süresini eklediğimizde, sorumuzun ölçütü değişir: En az adımı değil, en az toplam süreyi arıyoruz.

Benzer biçimde en az dönüş, en az enerji veya en az tehlikeli bölge farklı tercihler doğurabilir. Kareli kâğıtta “en kısa” dediğinde hangi değeri küçülttüğünü açıkça yaz. Eşit maliyet koşulu bozulduğunda BFS'nin adım sayısına göre bulduğu yolun süre açısından da en iyi olduğunu varsayma. Farklı maliyetlere uygun yöntemler vardır; ama önce doğru soruyu ve doğru maliyetleri kurmak gerekir.

Kendi labirentinin araştırmacısı ol

Kareli kâğıda küçük bir labirent çizip başlangıç ve çıkışı işaretle. Açık karelere, başlangıçtan ulaşılabilecek en az adım sayısını katman katman yazmayı dene. Önce başlangıç sıfır olsun; doğrudan komşuları bir, onların henüz işaretlenmemiş komşuları iki olsun. Duvarın üzerinden atlama ve aynı kareye farklı sayılar yazma. Böylece yalnızca bir rota çizmek yerine araştırmanın nasıl yayıldığını görürsün.

Bir arkadaşın kuyruk kartlarını tutsun, sen yeni bulunan kareleri işaretle. Her kart işlendiğinde kuyruğun önünden çıkarın; yeni kartları sona koyun. Çıkışa ulaşamıyorsanız açık bir yol gerçekten bulunmayabilir. Kuyruk boşaldığında araştırılabilecek bütün erişilebilir kareler bitmiştir. Bu da bir sonuçtur: Her labirentin mutlaka çözülebilir olduğunu düşünmek yerine, çizdiğiniz bağlantıları kontrol edebilirsiniz.

Son olarak duvarlardan birini değiştirip yeniden deneyin. Kısa yolunuz aynı mı kaldı, yoksa başka bir rota mı ortaya çıktı? Bir oyun tasarımcısı bazen oyuncunun kristalleri toplaması veya güzel bir bölgeyi keşfetmesi için uzun rotayı çekici kılabilir. Bilgisayarın bulduğu en az adımlı yol ile oyuncunun seçmek istediği yol farklı olabilir. Harita hakkında ne istediğini söylediğinde, algoritmanın cevabı da daha anlamlı hâle gelir.

Kaynaklar ve ileri okuma

KEŞFE DEVAM

Bir sonraki merakın ne?

Ortadaki kart seçilince aramanın gereksiz yarısı silikleşip geride kalıyor.
7 dk okumaYeni keşif

Sıralı kartlarda aramayı yarıya indir

Bir deste numaralı kart küçükten büyüğe dizilmişse, aradığın sayıyı bulmak için baştan tek tek bakman gerekmez. Ortadaki kart sana hangi yarıya yönelmen gerektiğini söyler.

Yazıyı oku
Lacivert arka planda koyu bir komut istemi penceresi; içinde yeşil ve mavi renkli komut satırları ve yanıp sönen bir imleç.
11 dk okumaYeni keşif

Windows CMD rehberi: siyah pencereyle neler yapabilirsin?

Filmlerde hacker’ların yeşil yazılı siyah pencerelere hızla bir şeyler yazdığını görmüşsündür. Gerçekte bu pencere, Windows’ta herkesin bilgisayarında hazır bekleyen Komut İstemi’dir, yani CMD. Onunla klasörlerde gezinebilir, internet bağlantını test edebilir, bilgisayarını tanıyabilir, hatta küçük oyunlar ve otomatik yedekleme araçları yazabilirsin. Bu rehberde basit komutlardan orta seviye betiklere kadar adım adım ilerleyeceğiz.

Yazıyı oku
Turuncu tonlu arka planda koyu bir terminal penceresi; içinde yeşil bir dolar işaretiyle başlayan komut satırları ve küçük bir parsa benzeyen benek desenleri.
10 dk okumaYeni keşif

Pardus terminal rehberi: Linux komutlarıyla ilk adımdan ilk betiğe

Linux dünyasında terminal bir yedek araç değil, işletim sisteminin kalbine açılan bir kapıdır. Pardus’ta terminali açtığında, dünyanın en büyük sunucularını, süper bilgisayarlarını ve Android telefonların temelini oluşturan aynı komut geleneğiyle konuşmaya başlarsın. Bu rehberde basit gezinme komutlarından paket kurmaya, borulardan ilk bash betiğine kadar Pardus terminalini adım adım keşfedeceğiz.

Yazıyı oku