--- title: 'A* Arama' source: 'https://academia.sh/tr/kurslar/algoritmalar/a-yildiz-arama' course: Algoritmalar language: tr updated: '2026-08-17T18:07:36+00:00' license: 'CC BY-SA 4.0' --- # A* Arama Sezgisel fonksiyonla hedefe yönelmiş arama, kabul edilebilirlik ve tutarlılık koşulları, Dijkstra ile ilişkisi ve genişletilen düğüm sayısındaki kazanç. Ö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. ```python 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. ```python 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. ```python 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.