8 bulmaca, sezgisel aramayı öğrendiğiniz gün ilk yazdığınız şeydir. Neredeyse her yaklaşımın işe yarayacağı kadar küçük, kötü yaklaşımların iyilerinden gözle görülür biçimde kötü olduğu kadar büyüktür. Bu makale standart çözümü baştan sona anlatıyor.
Durum
Tahtayı, satır öncelikli sırayla 0..8 indekslenmiş dokuz tamsayılık bir dizi olarak temsil edin:
konumlar: indeksler:
1 2 3 0 1 2
4 5 6 ←→ 3 4 5
7 8 _ 6 7 8
Boş hücre bir işaret değeridir — genellikle 0 seçilir. Hedef durum: [1, 2, 3, 4, 5, 6, 7, 8, 0].
Hamleler
Boşluğun e indeksinde olduğu bir konumdan, boşluğu dikey-yatay komşularıyla takas edebilirsiniz: üst satırda değilse e-3 (üstü), alt satırda değilse e+3 (altı), en sol sütunda değilse e-1 (solu), en sağ sütunda değilse e+1 (sağı).
neighbors(state) fonksiyonu, tek hamlede ulaşılabilen en fazla dört durumu döndürür.
Sezgisel: Manhattan mesafesi
Her taş için (boşluğu yok sayın), şu anki konumundan hedef konumuna olan satır mesafesi ile sütun mesafesini hesaplayın. Taşlar üzerinden toplayın. Bu toplam, kalan hamle sayısı için bir alt sınırdır — her taş en az o kadar yol katetmek zorundadır.
Sözde kodla:
h(state) = taşlar t üzerinden toplam:
abs(satır(mevcut) - satır(hedef)) + abs(sütun(mevcut) - sütun(hedef))
Manhattan mesafesi kabul edilebilirdir (asla abartmaz) ve tutarlıdır (üçgen eşitsizliğini sağlar). İki özellik de A* için önemlidir.
On iki satırda A*
A*, f = g + h değerine göre sıralanmış bir öncelik kuyruğu tutar; g derinlik (şu ana kadarki hamleler), h kalan hamlelerin sezgisel tahminidir. Her yinelemede: en düşük f'li durumu çıkar, genişlet, komşuları güncellenmiş f ile kuyruğa ekle.
open = priority_queue()
open.push(start, f=h(start))
came_from = {}; g = {start: 0}
while open is not empty:
state = open.pop()
if state == goal: return reconstruct_path(came_from, state)
for n in neighbors(state):
tentative_g = g[state] + 1
if n not in g or tentative_g < g[n]:
g[n] = tentative_g
came_from[n] = state
open.push(n, f=tentative_g + h(n))
Çözücünün tamamı bu. h'yi ve neighbors'ı uygulayın; herhangi bir 8 bulmacayı çözebilirsiniz.
Performans
Manhattan mesafeli A*, herhangi bir 8 bulmacayı birkaç yüz mikrosaniyede çözer ve en zor örneklerde birkaç yüz ile birkaç bin arası durum genişletir. Durum uzayı o kadar küçüktür ki bu boyutta A*, IDA*'a üstün gelir — 3×3 için doğru seçim A*'dır; 4×4 ve üzerinde bayrağı IDA* devralır.
Yaygın tuzaklar
İlk denemede yanlış yapacağınız üç şey:
Durumun karması (hashing). Python'un demetleri güzelce karılır; Java'nın int dizileri karılmaz. Hangi dili kullanırsanız kullanın, kapalı/açık kümelerin çalışması için durumun karılabilir olması gerekir. Yaygın bir numara, 9 taşlık durumu tek bir 32-bit tamsayıya kodlamaktır (hücre başına 4 bit, çünkü değerler 0..8).
İnversiyon-parite kontrolünü unutmak. Rastgele bir 8 bulmacayı karıştırarak üretirseniz, bulmaca yarı yarıya olasılıkla çözülemezdir ve A*, var olmayan bir yolu arayarak 181.440 durumluk yarı-uzayın tamamını tarar. A*'ı çalıştırmadan önce hızlı bir parite kontrolü ekleyin ya da hedeften geriye yürüyerek üretin.
Sezgiselde boşluğu taş gibi saymak. Manhattan mesafesi yalnızca gerçek taşlar üzerinden toplanır. Boşluğu dahil etmek sezgiseli şişirir ve kabul edilebilirliği bozar (boşluğu tek hamleyle "bedavaya düzeltebilirsiniz").
Manhattan'ın ötesi
8 bulmacada Manhattan'dan daha iyisi yapılabilir — ama çok değil:
- Doğrusal çakışma (linear conflict) — aynı satırdaki iki taş hedef satırlarında ama yanlış sıradaysa, birbirlerini geçmek için en az iki ekstra hamleye ihtiyaç duyacaklardır. Çakışma başına 2 ekleyin. Manhattan'ı %5–15 iyileştirir.
- Örüntü veritabanları — taş alt kümeleri üzerinden optimal maliyeti önceden hesaplayın. 8 bulmacada minicik hız kazancı için devasa bellek maliyeti. 15 bulmaca çözücüler için değer, burada değmez.
8 bulmacalar için pratik tatlı nokta, doğrusal çakışmalı düz Manhattan'dır.
Sırada ne inşa etmeli
Bir 8 bulmaca çözücü yazdıysanız doğal devam adımları şunlar:
- IDA* + yürüme mesafeli 15 bulmaca çözücü. Aynı temel fikirler, daha derin arama. (Rehber burada.)
- Örüntü veritabanlı genel N bulmaca çözücü. Bir hafta sonu projesi.
- Çözülebilirlik testi — bir tahtaya hedeften ulaşılıp ulaşılamayacağını döndüren 30 satırlık bir fonksiyon. Uygulama geliştirirken işe yarar. (Parite teoremine dayanır.)
8 bulmaca küçüktür. Onu çözerken öğrendiğiniz teknikler en tepeye kadar ölçeklenir.