Manhattan mesafesi sezgiseli, sezgisel aramada muhtemelen gelmiş geçmiş en çok kullanılan sezgiseldir. 1960'larda 15 bulmaca için gayriresmî olarak ortaya atıldı, 1968'deki A* makalesinde biçimselleştirildi ve hâlâ her yapay zeka ders kitabının öğrettiği ilk şeydir. Bu yazı, neden işe yaradığı, neyi iyi yaptığı ve nerede yetersiz kalmaya başladığı hakkında.
Tanım
N×N bir kayan bulmacada, her taş için (boşluğu saymayın) şunu hesaplayın:
mesafe = | mevcut_satır − hedef_satır | + | mevcut_sütun − hedef_sütun |
Tüm taşlar üzerinden toplayın. Bu toplam, mevcut tahtanın hedefe olan Manhattan mesafesidir.
Neden "Manhattan"? Manhattan'ın sokakları düzenli bir ızgaradır. Bir köşeden diğerine gitmek için şu kadar blok doğu-batı, şu kadar blok kuzey-güney yürürsünüz. Çapraz kestirme yapamazsınız. Yürünen toplam blok sayısı Manhattan mesafesidir — taksi mesafesi ya da L¹ normu da denir.
Taş için de aynı mantık: her hamlede yatay ya da dikey bir hücre gidebilir, çapraz gidemez. Bulunduğu yerden gitmesi gereken yere ulaşmak için gereken en az hamle sayısı, satır uzaklığı artı sütun uzaklığıdır.
Kabul edilebilirlik
A*, sezgiselin kabul edilebilir olmasını ister: kalan gerçek hamle sayısını asla fazla tahmin etmemelidir. Sezgisel fazla tahmin ederse, A* optimal yolu erkenden budayıp optimal olmayan bir çözüm döndürebilir.
Manhattan mesafesi kabul edilebilirdir, çünkü:
- Her taş en az satır uzaklığı + sütun uzaklığı kadar yol almak zorundadır; çünkü hamleler satır ya da sütunda birim adımlardır.
- Tüm taşlar üzerinden toplamak sınırı aşamaz; çünkü her hamle tam olarak bir taşı tam olarak bir hücre ilerletir. (Boşluğu da hareket ettirir, ama boşluğu saymıyoruz.)
- Aslında gerçek mesafe Manhattan mesafesinden en az bu kadardır; çünkü taşların, başkaları geçebilsin diye sık sık kenara çekilmesi gerekir — ama asla daha az değildir.
Yani Manhattan ≤ gerçek. Kabul edilebilir.
Tutarlılık
Daha güçlü bir özellik: tutarlılık, bazen sezgiselin monotonluğu da denir. Bir sezgisel, her s durumu ve m hamlesiyle ulaşılan her s' ardılı için şunu sağlıyorsa tutarlıdır:
h(s) ≤ maliyet(m) + h(s')
Türkçesi: tek bir hamle yaptığınızda sezgisel değer birden fazla düşemez.
Manhattan mesafesi tutarlıdır; çünkü tek bir hamle Manhattan mesafesini tam olarak +1 ya da −1 değiştirir. (Bir taş bir hücre hareket eder, yani sezgisele katkısı ±1 değişir; diğer tüm taşların katkıları aynı kalır.)
Tutarlılık önemlidir; çünkü A*'ın kapattığı bir durumu asla yeniden açmayacağını garanti eder. Uygulamaların tutarsızlık durumunu ele alması gerekmez — bu da kodu ve kanıtları sadeleştirir.
Pratikte neden bu kadar iyi çalışır
Üç somut özellik:
Hesaplaması ucuzdur. Tahta başına O(N²) — tüm taşlar üzerinden toplam, her katkı sabit zaman. h(s) hesabı herhangi bir modern bilgisayarda mikrosaniyeler alır.
Derin budama yapacak kadar sıkıdır. 15 bulmacada Manhattan sezgiselinin değeri, gerçek mesafenin ortalama %75–90'ıdır. Böyle sıkı bir sezgiselle A*, durum uzayının minicik bir kesrini keşfeder.
Doğrusal çakışmayla iyi birleşir. Her "doğrusal çakışma" için (aynı satırda, ikisi de o satıra ait ama yanlış sırada iki taş) 2 hamle eklemek, marjinal hesaplama maliyetiyle kesinlikle daha sıkı bir sezgisel verir.
Nerede yetersiz kalır
Manhattan mesafesi, taşları birbirinin içinden serbestçe geçebilirmiş gibi ele alır. Geçemezler. En derin kör noktalar:
Satır ya da sütun içi çakışmalar. 2 ve 3 numaralı taşlar ikisi de 1. satırda ama yanlış sıradaysa, Manhattan onlara düz mesafelerini verir ve hiçbir şey fark etmez. Gerçekte birinin satırdan çıkarılması, diğerinin geçirilmesi ve ilkinin geri sokulması gerekir. Bu, Manhattan'ın görmediği en az 2 ekstra hamledir. Doğrusal çakışma (linear conflict) bunu yamar.
"Yürüme" yapısı. Manhattan, hepsi aynı satıra ya da sütuna ait taşların o satır/sütun içinde birbirleriyle nasıl ilişkilendiğini yok sayar. Yanlış permütasyondaki dört taşlık bir satır, birden çok "satır takası" gerektirir — bu yapıyı yürüme mesafesi (walking distance) yakalar.
Ayrık altküme etkileşimleri. Taşların herhangi bir ayrık bölüntüsü için, her parçayı yerine oturtmanın optimal maliyeti, Manhattan'dan (tekli elemanlara bölüntüden) daha sıkı bir alt sınırdır. Toplamsal örüntü veritabanları bunu kullanır.
İlerleyiş şöyledir: Manhattan → Manhattan + doğrusal çakışma → yürüme mesafesi → örüntü veritabanları. Her biri bir öncekinden kesinlikle iyidir.
Büyük tahtalar neden daha fazlasını ister
Manhattan mesafesi 15 bulmacada gerçek mesafenin ortalama %75–90'ını verir. 24 bulmacada ortalama %65'ini. 35 bulmacada yaklaşık %55'ini.
Nedeni şu: tahtalar büyüdükçe taş çakışmaları ve "yürüme yapısı", düz mesafelere kıyasla daha önemli hale gelir. İkisini de yok sayan Manhattan mesafesi, büyük tahtalarda giderek daha fazla eksik tahmin eder.
24 bulmaca ve 35 bulmaca çözümünde örüntü veritabanlarının fiilen zorunlu olmasının nedeni budur. Manhattan sezgiseli 15 bulmaca ve 8 bulmaca için yeterlidir ama daha büyük boyutlarda çok fazla bilgi kaybeder.
Geometrik sezgi
Manhattan mesafesini düşünmenin güzel bir yolu: düz bir düzlemde tek bir taş hayal edin. Taşın k hamlede ulaşabileceği noktalar kümesi, kenarı k olan bir elmastır — Manhattan mesafesi ≤ k olan noktalar. (Öklidyen karşılığı, yarıçapı k olan bir çember olurdu.)
Manhattan mesafesi, ızgara üzerinde hareketin doğal geometrisidir. Hareket modeliniz ızgara adımlarıyla kısıtlıysa geometri Manhattan mesafesidir; Öklid mesafesinin konuyla ilgisi yoktur.
Bunun uygulama geliştiricileri için anlamı
Kayan bulmaca uygulamanıza milisaniyeler içinde çalışan bir ipucu düğmesi yazıyorsanız:
- 3×3 — Manhattan + doğrusal çakışma fazlasıyla yeter. A* onlarca durum keşfeder; mikrosaniyelerde biter.
- 4×4 — Manhattan + doğrusal çakışma bir ipucu için yeterince hızlıdır (tek hamle, tam optimal çözüm değil). Tam optimal çözüm için doğru seçim yürüme mesafesidir.
- 5×5+ — Örüntü veritabanları. Manhattan, ipucu düğmesinin zaman bütçesine sığacak kadar güçlü değildir.
Slide Puzzle, 3×3 ve 4×4 ipucu düğmesi için Manhattan + doğrusal çakışma, 4×4 zorluk kalibrasyonu için yürüme mesafesi, 5×5 ve 6×6 kalibrasyonu için de 5+5+5+9 örüntü veritabanı kullanır. Manhattan sezgiseli hepsinin temelidir.
Son bir sezgi
Kayan bulmacaları aranabilir kılan şey Manhattan mesafesi sezgiselidir. O olmasa A* ve IDA*, BFS'e dönüşürdü — ve BFS, 15 bulmacayı evrenin ömrü içinde bitiremez.
O sezgisel, çözümsüz görünen bir problemi milisaniyelik bir hesaba çeviren tek satırlık koddur. İyi anlamaya değer.