A* Arama

Önceki iki algoritma kaynaktan tüm düğümlere uzaklık hesaplıyordu. Belirli bir hedefe gidiliyorsa bu israftır: hedefin tersi yöndeki düğümler de aynı özenle işlenir.

A*, hedefin nerede olduğuna dair bir tahmini aramaya katarak bu israfı azaltır.

Değerlendirme İşlevi

Her düğüm için iki büyüklük tutulur:

• $g(v)$ — kaynaktan v‘ye bilinen en iyi maliyet (Dijkstra’daki uzaklık).
• $h(v)$ — v’den hedefe tahmini kalan maliyet; problem bilgisinden gelir.

Arama, ikisinin toplamına göre yapılır:

$$f(v) = g(v) + h(v)$$

$f(v)$, v üzerinden geçen bir çözümün tahmini toplam maliyetidir. Öncelik kuyruğu uzaklığa değil bu değere göre sıralanır; gerisi Dijkstra ile aynıdır.

import heapq


def a_yildiz(cizge: dict[str, list[tuple[str, int]]],
             baslangic: str, hedef: str, h: dict[str, int]) -> float | None:
    g: dict[str, float] = {baslangic: 0}
    acik: list[tuple[float, float, str]] = [(h[baslangic], 0, baslangic)]
    kapali: set[str] = set()

    while acik:
        _, maliyet, dugum = heapq.heappop(acik)
        if dugum in kapali:
            continue
        kapali.add(dugum)
        if dugum == hedef:
            return maliyet
        for komsu, agirlik in cizge[dugum]:
            yeni = maliyet + agirlik
            if yeni < g.get(komsu, float("inf")):
                g[komsu] = yeni
                heapq.heappush(acik, (yeni + h[komsu], yeni, komsu))
    return None

$h(v) = 0$ alınırsa $f = g$ olur ve algoritma tam olarak Dijkstra’ya dönüşür. A*, bu anlamda Dijkstra’nın genellemesidir: sezgi, aramaya eklenen ek bilgidir.

Kabul Edilebilirlik

Sezgi keyfî olamaz. Kabul edilebilir (admissible) olması, hiçbir düğümde gerçek kalan maliyeti aşmaması demektir:

$$h(v) \leq h^*(v)$$

Burada $h^*(v)$ gerçek kalan maliyettir. Kabul edilebilir sezgiyle A*, bulduğu ilk çözümün eniyi olduğunu garanti eder.

Gerekçe: hedef kuyruğun başına geldiğinde $f(\text{hedef}) = g(\text{hedef})$’tir. Daha iyi bir çözüm olsaydı, o çözümün yolundaki bir düğüm kuyrukta bulunur ve $f$ değeri — tahminler aşmadığı için — gerçek toplam maliyetten küçük olurdu; dolayısıyla hedeften önce çıkarılırdı.

Koşul ihlal edilirse eniyilik kaybolur.

cizge = {
    "A": [("B", 1), ("C", 5)],
    "B": [("H", 10)],
    "C": [("H", 1)],
    "H": [],
}

asiri = {"A": 0, "B": 1, "C": 10, "H": 0}     # C'nin tahmini gerçeğin (1) çok üstünde
kabul_edilebilir = {"A": 6, "B": 10, "C": 1, "H": 0}

print(a_yildiz(cizge, "A", "H", asiri))                  # 11  — eniyi değil
print(a_yildiz(cizge, "A", "H", kabul_edilebilir))       # 6
print(a_yildiz(cizge, "A", "H", {d: 0 for d in cizge}))  # 6   — Dijkstra

Aşırı tahmin, C üzerinden geçen gerçek en kısa yolu (A→C→H, 6) elemeye yol açar; algoritma A→B→H yolunu (11) döndürür.

Tutarlılık

Daha güçlü bir koşul, tutarlılıktır (consistency): her (v, w) kenarı için

$$h(v) \leq \text{ağırlık}(v, w) + h(w)$$

Bu, üçgen eşitsizliğinin sezgi üzerindeki karşılığıdır. Tutarlı bir sezgi kabul edilebilirdir ve ek olarak şunu sağlar: bir düğüm kapatıldığında $g$ değeri kesinleşmiştir, yani hiçbir düğüm iki kez genişletilmez.

Tutarlı olmayan ama kabul edilebilir bir sezgide, kapatılmış düğümlerin yeniden açılması gerekebilir; algoritma yine eniyi sonucu verir ama daha çok iş yapar. Pratikte kullanılan sezgilerin çoğu — düzlemde kuş uçuşu uzaklık, ızgarada Manhattan uzaklığı — tutarlıdır.

Ölçülen Kazanç

Kazanç, genişletilen düğüm sayısında görünür. Aşağıdaki ızgarada her adım bir birim maliyetlidir; komşuluk dört yöndedir.

def izgara_ara(izgara: list[str], baslangic: tuple[int, int],
               hedef: tuple[int, int], sezgi) -> tuple[int, int]:
    """(yol maliyeti, genişletilen düğüm sayısı)"""
    g = {baslangic: 0}
    acik = [(sezgi(baslangic, hedef), 0, baslangic)]
    kapali: set[tuple[int, int]] = set()
    sayac = 0

    while acik:
        _, maliyet, dugum = heapq.heappop(acik)
        if dugum in kapali:
            continue
        kapali.add(dugum)
        sayac += 1
        if dugum == hedef:
            return maliyet, sayac
        s, t = dugum
        for ds, dt in ((-1, 0), (0, -1), (0, 1), (1, 0)):
            y, x = s + ds, t + dt
            if 0 <= y < len(izgara) and 0 <= x < len(izgara[0]) and izgara[y][x] != "#":
                yeni = maliyet + 1
                if yeni < g.get((y, x), float("inf")):
                    g[(y, x)] = yeni
                    heapq.heappush(acik, (yeni + sezgi((y, x), hedef), yeni, (y, x)))
    return -1, sayac


sifir = lambda a, b: 0
manhattan = lambda a, b: abs(a[0] - b[0]) + abs(a[1] - b[1])

acik_izgara = ["." * 15 for _ in range(15)]
duvarli = ["".join("#" if (2 <= y <= 12 and x == 7) else "." for x in range(15))
           for y in range(15)]

print(izgara_ara(acik_izgara, (7, 1), (7, 13), sifir))       # (12, 147)
print(izgara_ara(acik_izgara, (7, 1), (7, 13), manhattan))   # (12, 13)
print(izgara_ara(duvarli, (7, 1), (7, 13), sifir))           # (24, 212)
print(izgara_ara(duvarli, (7, 1), (7, 13), manhattan))       # (24, 169)

Engelsiz ızgarada A*, hedefe giden şeridi izler ve 147 yerine 13 düğüm genişletir. Yol maliyeti aynıdır — kazanç doğrulukta değil, harcanan işte.

Duvarlı ızgarada kazanç erir: Manhattan uzaklığı duvarı görmediğinden tahmin gerçeğin çok altında kalır ve sezgi arama yönünü yeterince daraltmaz. Sezginin kalitesi, gerçeğe ne kadar yaklaştığıyla ölçülür; $h = 0$ ile $h = h^*$ arasındaki her nokta, Dijkstra ile doğrudan hedefe yürüme arasında bir yerdedir.

Ödünleşimler

Bellek. A*, açık kümedeki tüm düğümleri saklar; büyük arama uzaylarında bellek, zaman kadar kısıtlayıcıdır. Derinliği artırarak yineleyen değişkeler ($O(b\,d)$ bellek) bu sorunu maliyet karşılığında çözer.

Kasıtlı aşırı tahmin. Sezgiyi bir çarpanla büyütmek aramayı daraltır ama eniyiliği bozar; bulunan çözümün çarpan kadar kötü olabileceği bilinerek kullanılır. Yanıtın hızlı olması eniyi olmasından değerliyse makul bir değiş tokuştur.

Sezginin maliyeti. $h$ her düğüm için hesaplanır; pahalı bir sezgi, kazandırdığı genişletmeden fazlasını götürebilir.

Bu ödünleşimler, aramanın yapay zekâ tarafındaki uzantısıdır ve oyun ağaçlarıyla birlikte yapay zekâ müfredatının konusudur; burada ele alınmaz.

Özet

• A*, düğümleri $f(v) = g(v) + h(v)$ değerine göre genişletir; $h = 0$ alındığında Dijkstra’ya indirgenir.
• Kabul edilebilir sezgi gerçek kalan maliyeti aşmaz ve bulunan çözümün eniyi olmasını garanti eder.
• Tutarlı sezgi üçgen eşitsizliğini sağlar; hiçbir düğüm iki kez genişletilmez.
• Kazanç genişletilen düğüm sayısında ortaya çıkar ve sezginin gerçeğe yakınlığıyla orantılıdır.
• Engeller tahmini gerçekten uzaklaştırır ve kazancı azaltır.
• Bellek kullanımı, kasıtlı aşırı tahmin ve sezginin hesaplama maliyeti başlıca ödünleşimlerdir.

Sonraki Adım

Buraya kadar sorulan soru “iki düğüm arasındaki en ucuz yol neydi” oldu. Sonraki ders soruyu değiştirir: tüm düğümleri birbirine bağlayan en ucuz kenar kümesi hangisidir? Minimum kapsayan ağaç problemi, açgözlü seçimin doğruluğunu farklı bir gerekçeyle — kesme özelliğiyle — kuracak.