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.

Labirenti düğüm ve yollarla anlat

Bir haritadaki kavşakları noktalar, aralarındaki geçitleri çizgiler olarak düşünebilirsin. Bu gösterime çizge denir. Her geçidin uzunluğu eşitse, en az sayıda geçitten geçmek kısa bir yolun göstergesi olabilir. Bazı haritalarda yolların uzunlukları farklıdır ve her adım eşit değildir.

Önce seçenekleri gör

Bir kavşaktan çıkarken birkaç yol olabilir. Hedefe ulaşmak için her ayrımı takip etmek, çıkmazları fark edip geri dönmek gerekebilir. Basit bir yöntem, daha önce ziyaret edilen kavşakları işaretlemektir. İşaretleme aynı yeri dönüp dönüp gezmeyi azaltır.

Kareli kâğıt örneği

Kareli kâğıda duvarlı küçük bir labirent çiz. Başlangıç ve çıkış karelerini işaretle. Yollar boyunca ok çizip adım sayısını not et; sonra başka bir güzergâh bulup karşılaştır. İki yol da çıkışa varıyorsa, az adımlı olan kare sayısına göre daha kısadır.

En kısa neye göre?

Bir yolun kısa sayılması için ölçüt gerekir. En az kare, en az dönüş veya en az süre farklı cevaplar verebilir. Dar bir geçit yavaş yürütüyorsa daha uzun görünen geniş yol daha çabuk olabilir. Bilgisayarın hangi maliyeti en aza indirmesi gerektiğini açıkça belirtmelisin.

Yanlış bir kısayol

Gözle en yakın görünen yön, duvar yüzünden çıkmaza gidebilir. Her adımda hedefe doğru dönmek de kesinlikle en kısa yolu bulacağı anlamına gelmez. Bir yolun gerçekten en kısa olduğunu göstermek için alternatifleri veya uygun bir algoritmanın garantisini kullanmak gerekir. İyi sezgi başlangıçtır, kanıt yerine geçmez.

Bir arkadaşına tarif et

Sen labirentte yürüyen kişi ol, arkadaşın kâğıtta kavşakları işaretlesin. Her kavşağa gelince hangi yolların denendiğini kaydetsin. Çıkışa varınca başka bir yolun daha kısa olup olmadığını kontrol edin. Tekrar eden kavşakları işaretlemek aramayı nasıl değiştirdi?

Yolu seçmek karar ister

Harita yazılımları ve oyun karakterleri rota bulurken hedefi, geçitleri ve maliyetleri kullanır. Küçük bir labirentte elle denemek yeterliyken büyük haritada programlı arama yararlıdır. Bazı oyunlar oyuncuyu manzara veya ödüllere uğratmak için kısa olmayan yolu özellikle tasarlayabilir. Sence bir oyunda en kısa yolu seçmek her zaman en eğlenceli yolu seçmek midir?