Bu derste oyunun haritası 🗺️
- Temeller — en kısa yollar ağacı, gevşetme relaxation
- Dijkstra — negatif olmayan ağırlıklar için klasik
- Oyunda yol bulma — arazi maliyeti, Dijkstra haritaları, A*’a köprü
- DAG’ler — doğrusal zaman; en uzun yol = kritik yol
- Negatif ağırlıklar — Bellman–Ford ve “sonsuz altın” açığı
…bir birimin bataklıktan değil yoldan dolaşmasını sağlayan yol bulmayı, yüzlerce düşmanı tek bir hesapla yönlendiren “Dijkstra haritası”nı ve oyun ekonomisindeki ticaret açıklarını bulan algoritmayı anlayacaksınız.
Bir RTS biriminiz haritanın öbür ucuna gidecek. Düz gitse 20 kare ama 12’si bataklık (her biri 6 kat yavaş). Yoldan dolaşsa 30 kare, hepsi hızlı.
- BFS (Yönsüz Graflar sunumu) adım sayar → bataklıktan geçer: 8 + 12×6 = 80 birim süre
- Yoldan: 30 × 1 = 30 birim süre
- Kenarların ağırlığı (süre, yakıt, tehlike) varsa “en kısa” = toplam ağırlığı en küçük yol. Bunun için yeni algoritmalar gerekiyor.
Mini sözlük
| edge-weighted digraph | kenar ağırlıklı yönlü graf | Her yönlü kenarın bir maliyeti var |
| shortest-path tree (SPT) | en kısa yollar ağacı | Kaynaktan herkese en kısa yolların birleşimi |
| distTo[] · edgeTo[] | uzaklık · son kenar | Şimdiye kadarki en iyi uzaklık · o yolun son kenarı |
| relaxation | gevşetme | “Bu kenarı kullanınca daha kısa olur mu?” kontrolü ve güncellemesi |
| negative cycle | negatif döngü | Ağırlıkları toplamı negatif olan döngü |
| critical path | kritik yol | Bir iş planındaki en uzun bağımlılık zinciri |
| heuristic | sezgisel tahmin | “Hedefe aşağı yukarı ne kadar kaldı?” (A*’ın sırrı) |
- temeller ve gevşetme
- Dijkstra
- oyunda yol bulma
- DAG’ler ve kritik yol
- negatif ağırlıklar
Problemin çeşitleri
- Tek kaynak: s’den herkese (bu derste)
- Kaynak–hedef: s’den t’ye (oyunda en sık; aynı algoritma, t bulununca dur)
- Tüm çiftler: herkesten herkese (küçük haritalarda önceden hesaplanıp tabloda tutulur)
| ağırlıklar… | algoritma |
|---|---|
| hepsi eşit (1) | BFS |
| negatif değil | Dijkstra |
| herhangi, graf DAG | topolojik sırayla gevşet |
| negatif olabilir, negatif döngü yok | Bellman–Ford |
distTo[v] (s’den v’ye en kısa uzaklık) ve edgeTo[v] (o yoldaki son kenar). Yol = edgeTo zincirini geriye izlemek (DFS/BFS’teki gibi!).Gevşetme relaxation — kendiniz deneyin
Soru: “s’den w’ye, v üzerinden (v→w kenarıyla) gitmek şimdiki en iyi yoldan daha mı kısa?” Evetse güncelle. Kaydırıcılarla oynayın. Bütün algoritmalar sadece bu hamleyi farklı sıralarda yapar.
Gevşetme — kod
distTo[] değerleri ancak ve ancak hiçbir kenar gevşetilemiyorsa (her v→w için distTo[w] ≤ distTo[v] + ağırlık) en kısa uzaklıklardır.Genel algoritma: “Gevşetilebilen bir kenar kaldıkça gevşet.” Doğru ama yavaş olabilir. Dijkstra, DAG ve Bellman–Ford bu genel algoritmanın akıllı sıralamalarıdır.
🎒 Sonsuz (∞) neden işe yarar? ∞ + 5 = ∞ ve her sayı ∞’dan küçük → ilk bulunan yol her zaman kabul edilir. Tam sayı dizilerde ∞ yoksa çok büyük bir sayı (ör. int.MaxValue / 2 — taşmasın diye yarısı!) kullanılır.
🎒 Kodu okuyalım
| ifade | ne demek | neden böyle |
|---|---|---|
distTo[v] + weight < distTo[w] | v’ye kadar + v→w kenarı, w’nin bilinen en iyisinden kısa mı? | “daha kısa bir yol buldum mu?” sorusunun tamamı bu satır |
distTo[w] = … | w’nin en iyi bilinen uzaklığını güncelle | bu değer yalnızca küçülebilir; büyümez |
edgeTo[w] = v | w’ye artık v’den geliniyor | yolu geri izlemek için; eski kayıt silinir |
| başlangıç değerleri | distTo[s] = 0, ötekiler Infinity | Infinity + ağırlık hâlâ Infinity: henüz ulaşılmamış düğüm hiçbir şeyi gevşetemez |
return true | bir şey değişti | Dijkstra bu cevaba göre öncelik kuyruğunu günceller |
🔗 Başka gözle: etkileşimli anlatımlar ve yazılar
Aynı konuyu başka bir anlatımla, kendi elinizle oynayarak görmek çok işe yarar. Kartlar yeni sekmede açılır; çoğu İngilizce ama görsel ve etkileşimli.
distTo[v] = 7, distTo[w] = 12, v→w kenarının ağırlığı 4. v→w gevşetilince ne olur?distTo[w] = 11, edgeTo[w] = v. Gevşetme sadece kenarın ucundaki (w) değerleri değiştirir.- temeller ve gevşetme
- Dijkstra
- oyunda yol bulma
- DAG’ler ve kritik yol
- negatif ağırlıklar
Saf yaklaşım: bütün yolları dene
Köy S’den kale T’ye; sayılar yol süresi (dakika). Yeşil = en kısa yol; kırmızı kesikli = en az adımlı yolun son kenarı.
| yol | adım | süre |
|---|---|---|
| S → A → C → T | 3 | 4 + 1 + 3 = 8 |
| S → B → A → C → T | 4 | 1 + 2 + 1 + 3 = 7 ✔ |
| S → B → C → T | 3 | 1 + 5 + 3 = 9 |
| S → B → T | 2 | 1 + 8 = 9 |
Bu grafta 4 yol var. Bir k × k ızgarada yalnızca sağa ve aşağı giden yollar bile: 10 × 10 → 48 620; 20 × 20 → 35 milyar; 50 × 50 → 2,5 × 1028.
Dijkstra’nın fikri
distTo[s] = 0, diğerleri ∞- Henüz kesinleşmemiş düğümler arasından distTo’su en küçük olanı (v) seç → v artık kesin
- v’nin bütün oklarını gevşet
- Herkes kesinleşene kadar tekrarla
Prim ile kardeş: Prim “ağaca en yakın”ı, Dijkstra “kaynağa en yakın”ı seçer.
Dijkstra — iz tablosu
Mor kesikli = PQ’da, yeşil = kesinleşti, mavi kenar = az önce gevşedi. Sonuç (0’dan): 2: .26, 4: .38, 7: .60, 5: .73, 3: .99, 1: 1.05, 6: 1.51. Başka bir kaynak için düğüme tıklayın.
Elle izleme: Dijkstra, adım adım
Rozet = kesinleşen uzaklık. Yeşil = en kısa yollar ağacı (edgeTo): T ← C ← A ← B ← S.
| # | PQ’dan çıkan | gevşetmeler | PQ (sonra) |
|---|---|---|---|
| 0 | — | dist[S] = 0 | (S, 0) |
| 1 | (S, 0) | S → A: 0 + 4 = 4 · S → B: 0 + 1 = 1 | (B, 1) (A, 4) |
| 2 | (B, 1) | B → A: 1 + 2 = 3 < 4 · B → C: 6 · B → T: 9 | (A, 3) (A, 4) (C, 6) (T, 9) |
| 3 | (A, 3) | A → C: 3 + 1 = 4 < 6 | (C, 4) (A, 4) (C, 6) (T, 9) |
| 4 | (C, 4) | C → T: 4 + 3 = 7 < 9 | (A, 4) (C, 6) (T, 7) (T, 9) |
| 5 | (A, 4) | bayat: A zaten 3 ile kesin, at | (C, 6) (T, 7) (T, 9) |
| 6 | (C, 6) | bayat, at | (T, 7) (T, 9) |
| 7 | (T, 7) | T kesin: hedef! | (T, 9) |
Sonuç: S 0, B 1, A 3, C 4, T 7. Yol: S → B → A → C → T.
“Bayat kayıt” hilesi: uzaklık azalınca eski kaydı silmek yerine yenisini ekleriz; eski kayıt çıkınca “bu düğüm zaten kesin” deyip atarız. Tek hedef aranıyorsa 7. adımda durulur.
Dijkstra — kod (ikili yığınla)
🎒 “Bayat kayıt” hilesi ve indeksli PQ
Bir düğümün uzaklığı iyileşince PQ’daki eski kaydını güncellemek gerekir. İki yol:
- İndeksli öncelik kuyruğu (iz tablosundaki demo): PQ her düğümün nerede olduğunu bilir, önceliğini düşürür (decreaseKey). PQ’da en fazla V kayıt.
- Tembel silme (koddaki): yeni bir kayıt ekle, eskisini bırak. Eski kayıt çıkınca
d > dist[v]ile tanı ve atla. Pythonheapq, C#PriorityQueuedecreaseKey desteklemediği için pratikte bu kullanılır.
Neden negatif olmamalı? Bir düğüm kesinleştiğinde “daha kısa bir yol bulunamaz” varsayıyoruz: geri kalan bütün yollar daha uzun bir yerden başlıyor ve kenar eklemek yolu kısaltamaz. Negatif kenar bu varsayımı yıkar.
🎬 Ara: Dijkstra, kâğıt üzerinde
Dijkstra’s Algorithm
Computerphile (Mike Pound) · 10 dk 43 sn · YouTube’da aç
Az önceki gevşetme ve öncelik kuyruğu adımlarının küçük bir graf üzerinde elle, sırayla yapılışı. Hangi düğümün neden önce alındığını izleyin.
1956’da Amsterdam’da genç Edsger Dijkstra, yeni bir bilgisayarın gücünü halka göstermek için bir problem arıyordu: “Rotterdam’dan Groningen’e en kısa yol”.
Kendi anlatımına göre nişanlısıyla alışverişteyken bir kafede oturdu ve algoritmayı kâğıt kalem olmadan, yaklaşık yirmi dakikada tasarladı. “Kâğıt kalemsiz tasarlamanın bir avantajı, kaçınılabilecek bütün karmaşıklıklardan kaçınmak zorunda kalmanızdır” dedi.
Makalesini 1959’da yayımladı — 3 sayfa. Bugün telefonunuzdaki harita uygulamasından oyunlardaki A*’a kadar her yerde onun izi var.
- temeller ve gevşetme
- Dijkstra
- oyunda yol bulma
- DAG’ler ve kritik yol
- negatif ağırlıklar
🎮 Arazili harita: BFS vs Dijkstra
Koyu yeşil = bataklık (6), sarı = orman (3), gri = yol (0,5). Karenin maliyeti = oraya girmenin maliyeti. Algoritmayı BFS yapın: adım sayısı azalır ama maliyet artar. Fırçayla bataklık/yol çizip tekrar arayın.
🔗 Ayrıntısı: Y8 · A* (sezgiyle hızlandırılmış Dijkstra, oyun haritalarında) sunumunda.
🎮 Dijkstra haritası: bir hesap, yüz düşman
Kaynak olarak hedefi (oyuncuyu) al, Dijkstra’yı bütün haritaya yay. Her karede “oyuncuya maliyet” yazar.
- Her düşman sadece: “komşularımdan sayısı en küçük olana git” → yol bulma bitti! 200 düşman = 1 Dijkstra.
- Birden çok hedef (bütün can paketleri) = çok kaynaklı Dijkstra → “en yakın can paketine” harita.
- Kaçış haritası: değerleri −1,2 ile çarp, bir kez daha yay → korkan düşmanlar köşeye değil, açık alana kaçar (Brogue’un ünlü hilesi).
RTS’lerde aynı fikrin vektör hâli: akış alanı flow field — Supreme Commander 2 gibi oyunlarda binlerce birim böyle yönlendirilir.
🔗 Ayrıntısı: Y7 · Yönlendirme (akış alanlarıyla kalabalık hareket) sunumunda.
🔮 Köprü: Dijkstra’dan A*’a
- Dijkstra hedefin nerede olduğunu bilmez: kaynak etrafında bir daire gibi her yöne yayılır.
- A*: PQ önceliği =
distTo[v]+ h(v), h = “hedefe kalan tahmini mesafe” (ör. kuş uçuşu). Arama hedefe doğru eğilir, çok daha az kare açar. - h hiçbir zaman gerçeği aşmazsa A* yine en kısa yolu bulur. h = 0 ise A* = Dijkstra.
Red Blob Games’in A* rehberi (kaynaklarda) ileriye bakmak için mükemmel.
- temeller ve gevşetme
- Dijkstra
- oyunda yol bulma
- DAG’ler ve kritik yol
- negatif ağırlıklar
DAG’de en kısa yol: topolojik sırayla gevşet
- Düğümleri topolojik sırayla (Yönlü Graflar sunumu) ele al, her birinin oklarını gevşet
- Bir düğüme sıra gelince ona gelen bütün oklar zaten gevşetilmiş → değeri kesin
- E + V süre (Dijkstra’dan hızlı, PQ yok!)
- Negatif ağırlıklarla da çalışır
- En uzun yol: ağırlıkları eksi yap (ya da
<yerine>). Genel graflarda imkânsız derecede zor olan problem, DAG’de kolay!
Elle izleme: nehirde sal yolculuğu
Sal yalnızca akıntı yönünde gider: geri dönüş yok, graf bir DAG. Sayılar saat. Topolojik sıra: Pınar, Değirmen, Orman, Köprü, Liman. Rozet = sonuçtaki uzaklık.
| # | sıradaki | oklarını gevşet | dist[] (Pınar … Liman) |
|---|---|---|---|
| 0 | — | — | 0, ∞, ∞, ∞, ∞ |
| 1 | Pınar | → Değirmen: 0 + 2 = 2 · → Orman: 0 + 6 = 6 | 0, 2, 6, ∞, ∞ |
| 2 | Değirmen | → Orman: 2 + 3 = 5 < 6 · → Köprü: 2 + 7 = 9 | 0, 2, 5, 9, ∞ |
| 3 | Orman | → Köprü: 5 + 1 = 6 < 9 · → Liman: 5 + 8 = 13 | 0, 2, 5, 6, 13 |
| 4 | Köprü | → Liman: 6 + 2 = 8 < 13 | 0, 2, 5, 6, 8 |
| 5 | Liman | oku yok | 0, 2, 5, 6, 8 |
En kısa yol: Pınar → Değirmen → Orman → Köprü → Liman, 8 saat. Orman’dan Liman’a doğrudan ok 8 saat; Köprü üzerinden 1 + 2 = 3 saat.
Öncelik kuyruğu yok, bayat kayıt yok: her düğüme sıra geldiğinde ona gelen bütün oklar zaten gevşetilmiş. 7 ok, her biri bir kez. Ağırlıklardan biri eksi olsaydı da (ör. yolda hazine) yöntem aynen çalışırdı.
🎮 Kritik yol: boss savaşına en hızlı hazırlık
Her iş bir süre alıyor, bazıları başkalarını bekliyor; işçi sınırsız (paralel). En erken bitiş = başlangıçtan bitişe en uzun yol. “Paralel iş zamanlama” problemi; oyun stüdyolarında proje planlarında (ve RTS yapı sıralarında) aynısı.
- temeller ve gevşetme
- Dijkstra
- oyunda yol bulma
- DAG’ler ve kritik yol
- negatif ağırlıklar
Problem: eksi ağırlık ne demek, Dijkstra neden yanılır?
- Şimdiye kadar her kenar bir bedeldi: süre, mesafe, yakıt. Hepsi artı.
- Bazı kenarlar kazandırır: içinden geçince can dolduran şifalı pınar, yokuş aşağı inerken dolan batarya, ödül veren ara görev.
- “Bedel” yerine “bedel − kazanç” yazınca ağırlık eksi olabilir.
- Soru aynı: A’dan B’ye toplamı en küçük yol hangisi?
Bir de en önemli kullanım var: döngü boyunca toplam eksiyse, o döngüde her tur kâr edilir. Oyun ekonomisindeki açıkları bulmanın yolu budur (birazdan).
Dijkstra kuyruktan çıkan düğüme “uzaklığı kesinleşti” der; çünkü daha uzun bir yoldan dolaşmak onu kısaltamaz. Eksi kenar varsa kısaltabilir.
| kenar | ağırlık |
|---|---|
| 0 → 1 | 4 |
| 0 → 2 | 5 |
| 2 → 1 | −3 |
- Dijkstra: kuyrukta 1 (uzaklık 4) ve 2 (uzaklık 5). En küçük 1 → “1’in uzaklığı 4, kesin.”
- Sonra 2 çıkar; 2 → 1 kenarı: 5 − 3 = 2. Ama 1 çoktan “kesin” sayıldı.
- Doğru cevap 2; Dijkstra 4 dedi.
“Bütün ağırlıklara 3 ekleyip eksiyi yok edeyim” işe yaramaz: çok kenarlı yollar daha çok cezalanır, en kısa yol değişir.
Bellman–Ford
- V − 1 tur boyunca, her turda bütün kenarları gevşet
- Neden V − 1? En kısa yol en fazla V − 1 kenarlı; k. turdan sonra k kenarlı bütün yollar doğru
- Negatif kenarlarla çalışır; süre E · V (yavaş!). Pratikte: sadece bir önceki turda değişen düğümlerin kenarlarını gevşet (kuyruklu sürüm)
- V. turda hâlâ bir şey değişiyorsa → negatif döngü var: en kısa yol tanımsız (döngüde sonsuza kadar dönüp maliyeti −∞’a indirebilirsin)
📜 Richard Bellman (1958), Lester Ford Jr. (1956). Bellman “dinamik programlama”nın da babası.
Elle izleme: Bellman–Ford tur tur
Aynı üç kenar; kenarlar listede yazıldığı sırayla gevşetiliyor: 0 → 1 (4), 2 → 1 (−3), 0 → 2 (5). Kaynak 0.
- Fikir: hangi düğümün “kesin” olduğuna karar vermeye çalışma. Bütün kenarları gevşet; sonra bir daha; bir daha…
- Her tur, doğru bilgiyi bir kenar daha uzağa taşır. En kısa yol en çok V − 1 kenarlıdır: V − 1 tur yeter.
- Ek veri yapısı yok: yalnızca
dist[]dizisi ve kenar listesi. (Dijkstra’da öncelik kuyruğu vardı.) - Son bir kontrol turu: hâlâ kısalan bir kenar varsa, sonsuza kadar kısaltan bir eksi döngü var demektir.
| tur | gevşetilen kenar | hesap | dist[] |
|---|---|---|---|
| başlangıç | — | — | 0, ∞, ∞ |
| 1 | 0 → 1 (4) | 0 + 4 = 4 < ∞ | 0, 4, ∞ |
| 1 | 2 → 1 (−3) | ∞ − 3: 2’ye henüz ulaşılmadı | 0, 4, ∞ |
| 1 | 0 → 2 (5) | 0 + 5 = 5 < ∞ | 0, 4, 5 |
| 2 | 0 → 1 (4) | değişmez | 0, 4, 5 |
| 2 | 2 → 1 (−3) | 5 − 3 = 2 < 4 | 0, 2, 5 |
| 2 | 0 → 2 (5) | değişmez | 0, 2, 5 |
| kontrol | üç kenar da | hiçbiri kısalmıyor | eksi döngü yok ✔ |
1. turda 2 → 1 kenarı işe yaramadı, çünkü 2’nin uzaklığı henüz bilinmiyordu. 2. turda bilindi ve 1’in uzaklığı düzeldi: turların tekrarlanmasının nedeni bu. Maliyet: tur sayısı × kenar sayısı = (V − 1) · E.
Kur, arbitraj ve “neden logaritma?”
- Kur = takas oranı. Tüccar “1 Altın verene 10 Gümüş veririm” diyorsa Altın → Gümüş kuru 10’dur. Geri dönüş kuru ayrıdır: 1 Gümüş → 0,09 Altın.
- Arbitraj: bir tur takas yapıp başladığınız paraya daha fazlasıyla dönmek. Oyunda bu bir hatadır: oyuncu aynı turu yüz kez atıp sınırsız zengin olur.
- Bir turun sonucu, yol üstündeki kurların çarpımıdır. Çarpım 1’den büyükse kâr var.
- Sorun: en kısa yol algoritmaları toplar, çarpmaz.
- Logaritma çarpmayı toplamaya çevirir: ln(a · b) = ln a + ln b. (ln x: “2,718’in kaçıncı kuvveti x eder?” 1’den büyük sayılarda artı, küçüklerde eksi, ln 1 = 0.)
- Kenar ağırlığı olarak −ln(kur) yazarsak: çarpım > 1 ⇔ ln’lerin toplamı > 0 ⇔ −ln’lerin toplamı < 0. Yani kârlı tur = eksi döngü; onu da Bellman–Ford’un kontrol turu bulur.
| takas | kur | elde | ln(kur) | ağırlık = −ln(kur) |
|---|---|---|---|---|
| başlangıç | — | 1 Altın | — | — |
| Altın → Gümüş | 10 | 10 Gümüş | 2,303 | −2,303 |
| Gümüş → Mücevher | 0,25 | 2,5 Mücevher | −1,386 | +1,386 |
| Mücevher → Altın | 0,43 | 1,075 Altın | −0,844 | +0,844 |
| tur | çarpım 1,075 | %7,5 kâr | toplam +0,073 | toplam −0,073 |
Kontrol: e0,073 = 1,075 ✓. Öbür turlar zararda: Altın → Gümüş → Altın = 10 · 0,09 = 0,90; Altın → Kürk → Altın = 2 · 0,48 = 0,96.
Aynı numara her “çarparak birleşen” ölçüde işe yarar: art arda isabet olasılıkları, hasar çarpanları, güvenilirlik. Çarpımı en büyük yol = −ln toplamı en küçük yol.
- Düğümler dört para birimi; okların üstündeki sayı kur: “okun başındaki paradan 1 verirsen ucundakinden bu kadar alırsın”.
- Algoritma kurlarla değil −ln(kur) ağırlıklarıyla çalışır; sağdaki tabloda
distTo[]bu ağırlıkların toplamıdır (Altın’dan o paraya en “ucuz” takas zinciri). Mor rozetler aynı sayılar. - “İleri ▶|” ile adım adım: mavi kenar az önce gevşedi. Üç tur (V − 1 = 3) sonunda tablo oturmuş olmalıydı.
- 4. tur kontrol turudur: bir kenar hâlâ gevşiyor → kırmızı döngü belirir: Altın → Gümüş → Mücevher → Altın, çarpım 1,075.
- Soru: tüccarlardan birinin kurunu değiştirerek açığı kapatın. Mücevher → Altın kuru en çok kaç olabilir? (10 · 0,25 · k ≤ 1 → k ≤ 0,40.)
💰 Oyun ekonomisinde arbitraj = negatif döngü
- Düğümler dört para birimi; okların üstündeki sayı kur: “okun başındaki paradan 1 verirsen ucundakinden bu kadar alırsın”.
- Algoritma kurlarla değil −ln(kur) ağırlıklarıyla çalışır; sağdaki tabloda
distTo[]bu ağırlıkların toplamıdır (Altın’dan o paraya en “ucuz” takas zinciri). Mor rozetler aynı sayılar. - “İleri ▶|” ile adım adım: mavi kenar az önce gevşedi. Üç tur (V − 1 = 3) sonunda tablo oturmuş olmalıydı.
- 4. tur kontrol turudur: bir kenar hâlâ gevşiyor → kırmızı döngü belirir: Altın → Gümüş → Mücevher → Altın, çarpım 1,075.
- Soru: tüccarlardan birinin kurunu değiştirerek açığı kapatın. Mücevher → Altın kuru en çok kaç olabilir? (10 · 0,25 · k ≤ 1 → k ≤ 0,40.)
NPC tüccarlarının takas oranları. Bir döngüde kurların çarpımı 1’den büyükse oyuncu o turu tekrar tekrar atıp bedava altın basar. Bellman–Ford’un kontrol turu bu döngüyü bulur; siz de yayımlamadan önce kurları düzeltirsiniz.
🧪 Kod laboratuvarı: Dijkstra
if (d > dist[v]) continue; satırını silin: sonuç değişiyor mu? Hız? (Doğru kalır ama bayat kayıtlar boşuna işlenir.)🐍 Kod laboratuvarı — Dijkstra (Python)
Derin hikâye: Shakey ve A*’ın doğuşu (1968)
- 1966–1972: Stanford Araştırma Enstitüsü’nde (SRI) geliştirilen Shakey, kendi eylemleri hakkında akıl yürüten ilk mobil robot olarak anılır: kamera ve mesafe sensörleriyle odaları algılıyor, kutuları itiyor, rampalardan geçiyordu.
- Shakey’in odalar arasında yol bulması gerekiyordu. Dijkstra’nın algoritması (1959) doğruydu ama hedefin nerede olduğunu hiç kullanmadan her yöne eşit yayılıyordu.
- Peter Hart, Nils Nilsson ve Bertram Raphael, 1968’de hedefe olan tahmini uzaklığı (sezgisel) aramaya ekleyen A*’ı yayımladı ve sezgisel “gerçek uzaklığı hiç aşmadığı” sürece en kısa yolu bulacağını ispatladı.
- Shakey bugün Bilgisayar Tarihi Müzesi’nde sergileniyor; A* ise neredeyse her oyunun yol bulucusunun kalbinde (Y8).
Kaynak: Wikipedia: Shakey the robot · CACM: Dijkstra röportajı (2001)
🧰 Kütüphaneler ve araçlar
| ad | platform | ne yapar / sınırları | nasıl eklenir |
|---|---|---|---|
| NetworkX | Python | dijkstra_path, bellman_ford_path, astar_path, all_pairs… | pip install networkx |
| scipy.sparse.csgraph.shortest_path | Python | Dijkstra, Bellman–Ford, Johnson, Floyd–Warshall; seyrek matrislerde hızlı. | pip install scipy |
| Unity NavMesh (AI Navigation) | Unity | Navmesh üzerinde A* + funnel; NavMesh.CalculatePath, NavMeshAgent (Y9). | Package Manager: AI Navigation |
| A* Pathfinding Project | Unity | Izgara, navmesh ve nokta grafları; çok iş parçacıklı arama, etiketler ve cezalar (Y8, Y12). | Asset Store |
| PathFinding.js | JavaScript | Izgara üzerinde A*, Dijkstra, JPS ve diğerleri; görsel demo. | npm install pathfinding |
🧩 Hangi algoritma, ne zaman?
- Tek hedef, iyi bir sezgisel var → A* (oyunların %90’ı).
- Bir noktadan herkese (ör. bir kuleden bütün hücrelere uzaklık, akış alanı) → Dijkstra / BFS.
- Negatif ağırlık (ödül veren kenarlar, döviz kurları) → Bellman–Ford; negatif döngü = sonsuz kazanç (arbitraj).
- Herkesten herkese, küçük graf (ör. 50 şehirlik dünya haritası) → Floyd–Warshall, bir kez hesaplanıp saklanır.
- Hareketli engeller → yeniden arama ya da artımlı algoritmalar (D* Lite); çoğu oyunda kısa aralıklarla yeniden A* yeterli.
- Negatif kenarla Dijkstra.
- Düğümü kuyruğa eklerken kapatmak (Dijkstra’da yanlış; çıkarırken kapatın).
- Gerçek maliyeti aşan (kabul edilemez) sezgisel.
- Kuyrukta bayat kayıtları atlamamak.
🤖 Bu konuyu bir YZ kod asistanıyla yazarken
- Negatif kenarla Dijkstra
- Düğümü eklerken kapatmak
- Kabul edilemez sezgisel
- Bayat kuyruk kayıtlarını işlemek
“Unity 6, C#. 8 yönlü ızgara A* yaz: düz adım 1, çapraz √2; köşe kesmeyi engelle; sezgisel octile; eşit f’de daha küçük h’yi tercih et; açık liste için kendi ikili yığının; kapalı küme bool[]; sonuç: yol + açılan düğüm sayısı. Ayrıca aynı API ile Dijkstra (sezgisel 0) ve BFS; üçünün aynı haritada aynı uzunlukta yol bulduğunu doğrulayan NUnit testleri.”
- Kenar ağırlıklarının negatif olup olamayacağını yazın
- Sezgiselin kabul edilebilirliğini açıklatın
- Eşitlik bozma (tie-breaking) kuralı isteyin
- Yolun yanında “açılan düğüm sayısı”nı da döndürsün
🚀 Proje ve araştırma önerileri
- [kolay] Metro haritası — Bir şehrin metro hatlarında en kısa ve en az aktarmalı rotalar.
- [orta] En güvenli yol — Kenar başına “güvenli geçme olasılığı” verin; −log(olasılık) ağırlıklarıyla en güvenli yolu Dijkstra ile bulun.
- [orta] Kule savunma uzaklık alanı — Hedeften bütün hücrelere Dijkstra ile uzaklık; düşmanlar alanın eğimini izlesin.
- [araştırma] Hızlandırma teknikleri — ALT (yer imli A*) ya da kontraksiyon hiyerarşilerini küçük bir yol ağında deneyin.
📄 Akademik okumalar ve kaynaklar
Dijkstra algoritması (ve Prim’in yeniden keşfi).
A*.
Bellman–Ford.
Neler öğrendik? 🎒
| algoritma | kısıt | tipik süre | en kötü | 🎮 oyunda |
|---|---|---|---|---|
| BFS | ağırlıklar eşit | E + V | E + V | karo haritada adım |
| Dijkstra (ikili yığın) | ağırlıklar ≥ 0 | E log V | E log V | arazili yol bulma, Dijkstra haritası |
| topolojik sıra | DAG | E + V | E + V | kritik yol, yapı sırası |
| Bellman–Ford (kuyruklu) | negatif döngü yok | E + V | E · V | ekonomi arbitraj kontrolü |
Hepsi aynı hamleyi (gevşetme) farklı sıralarda yapıyor.
🏁 Algoritmalar bölümünün sonu
18 sunumda neler topladınız:
- Analiz: büyüme hızları, ölçme, kare bütçesi
- Temel yapılar: dizi, bağlı liste, yığın, kuyruk, Union–Find
- Sıralama & arama: ikili arama, 7 sıralama algoritması
- Sembol tabloları: BST, dengeli ağaçlar, kd-ağaçları, hash
- Öncelik kuyrukları: ikili yığın
- Graflar: DFS, BFS, topolojik sıra, MST, en kısa yollar
Alıştırmalar 🏋️
- Kâğıt-kalem: tinyEWD’de 0’dan Dijkstra iz tablosunu çıkarın; sonuçları demo ile karşılaştırın.
- Karo haritada 8 yönlü harekete izin verin; çapraz adımın maliyeti √2. Dijkstra’nın yolu nasıl değişir?
- p5.js’te bir Dijkstra haritası yapın: fare = hedef; 100 “zombi” her karede en küçük komşuya gitsin.
- “s’den t’ye en kısa yol” için Dijkstra’yı t kesinleşince durdurun. Ortalama kaç kare açılıyor? Sonra kuş uçuşu mesafeyi önceliğe ekleyin (ilk A*’ınız!) ve tekrar sayın.
- Kendi oyununuzdaki bir “üretim zinciri” için DAG çizip kritik yolu bulun.
- 🤖 Bir YZ asistanından “Unity’de ızgarada Dijkstra” isteyin. PQ olarak ne kullandı?
List.Sortise her adımda N log N — neden kötü?
🎮 Bu sunumdaki oyunlar
Adı geçen oyunu tanımıyorsanız: oyuncuların kullandığı wiki sayfası ve oyunu kısaca gösteren bir video. ▶ video slaydın üstünde açılır (Esc ile kapanır); 🎯 işaretli bağlantılar doğrudan bu sunumdaki konuya gider.
