Manhattan, kabul edilebilir bir keşif merkezine nasıl yaklaşıyor?

Question

1 döşemenin hareketlerini sayarken diğer karoların hedef haline gelmesine neden olabileceği doğru değil mi? Ve bu nedenle her bir karo için sayım, hedefe ulaşmak için gereken minimum hamle sayısından daha fazlasını verebilir mi?

Bu soru, 15-Puzzle için Manhattan mesafesi bağlamında.

biz N-Puzzle bir kabul sezgisel olarak Manhattan mesafe kullanabilir miyim: Burada

farklı bir deyişle meselesidir. A * aramasını uygulamak için kabul edilebilir bir keşfe ihtiyacımız var. Manhattan buluşsal bir aday mı? Eğer evet ise, yukarıdaki argümana nasıl karşı çıkıyorsunuz (sorudaki ilk 3 cümlesi)?

Tanımlar: A* bir tür arama algoritmasıdır. Hedefe tahmini mesafeyi belirlemek için sezgisel bir işlev kullanır. Bu sezgisel işlev, hedefe olan uzaklığı asla abartmasa da, algoritma, muhtemelen ilk aramadan daha hızlı olan en kısa yolu bulacaktır. Bu koşulu yerine getiren bir sezgisel kabul edilebilir.

Answer 1

Bu problemi çözmek için kabul edilebilir sezgilerin hareket sayısını fazla tahmin etmemesi gerekir. Blokları (1) sadece bir defada ve 4 yönden sadece birinden hareket ettirebildiğinizden, her bir blok için en uygun senaryo, hedef durumuna açık, engelsiz bir yola sahip olmasıdır. Bu, bir bloklar için geri kalanı bir optimal bloktur, yani bloğun doğru yerde olması için 'un M.D.'den daha fazla harekete geçeceği anlamına gelir. Böylece, sezgisel hiçbir zaman aşırı tahmin ve kabul edilebilir değildir.

Birisi bunun doğru, resmi bir sürümünü gönderdiğinde sileceğim.

Answer 2

Resmi Kanıt: h tanımına göre h (s ∗) = 0, s ∗ hedef durum ise. Bazı ilk durum s0 için çelişki ile ispat için C ∗ < h (s0) olduğunu varsayalım. Her bir eylemin yalnızca bir döşemeyi taşıyabildiğinden, bir eylemi gerçekleştirmenin en fazla h'yi tek tek azaltabileceğini unutmayın. Hedef, C ∗ eylemlerinde 'a ulaşılabildiğinden, h (s ∗) sıfır olması gerektiğinden, bizi çelişkisine getiren h (s ∗) ≥ h (s0) - C ∗> 0'a sahibiz. Bu nedenle, h (s0) ≤ C ∗ forall s0 olmalı ve h kabul edilebilir. (Kaynak: University of California, Irvine)