Uygulama: Mini Labirent Çözme Simülasyonu

Bu uygulama, Yapay Zekâ Yöntemleri dersinde öğrencilerin özellikle arama algoritmalarının nasıl çalıştığını uygulamalı olarak anlamalarını amaçlar.

Öğrenciler aynı labirenti farklı yöntemlerle çözerek BFS, DFS ve A* algoritmalarının yaklaşım farklarını gözlemleyecekler.

🎯 Uygulamanın amacı

Uygulama sonunda öğrencilerin:

• Yapay zekâda arama problemi kavramını anlaması,

• Durum, başlangıç ve hedef kavramlarını öğrenmesi,

• BFS (Genişlik Öncelikli Arama) mantığını kavraması,

• DFS (Derinlik Öncelikli Arama) mantığını kavraması,

• A* algoritmasının temel çalışma mantığını anlaması,

• Aynı problemin farklı algoritmalarla nasıl çözülebileceğini karşılaştırması,

• Algoritmaların bulduğu yolları ve ziyaret ettiği hücreleri incelemesi

beklenmektedir.

---

1. Problem Tanımı

Bir robotun aşağıdaki labirentte S (Start) noktasından G (Goal) noktasına ulaşmasını istiyoruz.

S . . # . . .
. . . # . # .
# # . . . # .
. . . # . . .
. # . . . # .
. # # # . . G

Burada:

Sembol	Anlamı
S	Başlangıç
G	Hedef
.	Geçilebilir alan
#	Duvar

Robot yalnızca:

• yukarı,

• aşağı,

• sağ,

• sol

yönlerinde hareket edebilecektir.

Çapraz hareket yoktur.

---

2. Problemi Yapay Zekâ Problemi Olarak Tanımlama

Labirenti yalnızca bir tablo olarak değil, bir arama problemi olarak düşünelim.

Başlangıç durumu

S

Hedef durum

G

Eylemler

Robot:

↑
↓
←
→

hareketlerinden birini seçebilir.

Kısıt

Robot:

# 

duvarlarından geçemez.

Amaç

S → G

arasında geçerli bir yol bulmaktır.

---

3. Önce İnsan Gibi Çözelim

Öğrencilere algoritmayı göstermeden önce şu soruyu sorun:

"Siz olsaydınız bu labirenti nasıl çözerdiniz?"

Muhtemel cevaplar:

• Sağdan giderdim.

• Önce aşağı giderdim.

• Deneyerek bulurdum.

• Geri dönerek başka yolu denerdim.

• En kısa yolu arardım.

Buradan şu noktaya geçebilirsiniz:

Bilgisayar da labirenti çözmek için bir stratejiye ihtiyaç duyar. İşte arama algoritmaları bu stratejileri tanımlar.

---

4. Python ile Labirenti Tanımlayalım

Öncelikle labirenti Python listesi içerisinde oluşturalım:

labirent = [
    "S..#...",
    "...#.#.",
    "##...#.",
    "...#...",
    ".#...#.",
    ".###..G"
]

for satir in labirent:
    print(satir)

Ekran:

S..#...
...#.#.
##...#.
...#...
.#...#.
.###..G

---

5. Başlangıç ve Hedef Noktasını Bulma

Python ile S ve G noktalarının koordinatlarını bulabiliriz.

baslangic = None
hedef = None

for satir in range(len(labirent)):
    for sutun in range(len(labirent[satir])):
        
        if labirent[satir][sutun] == "S":
            baslangic = (satir, sutun)
            
        elif labirent[satir][sutun] == "G":
            hedef = (satir, sutun)

print("Başlangıç:", baslangic)
print("Hedef:", hedef)

Örneğin:

Başlangıç: (0, 0)
Hedef: (5, 6)

Burada:

(satır, sütun)

mantığını kullanıyoruz.

---

6. Robotun Hareketleri

Robotun dört yönde hareket edebileceğini tanımlayalım:

hareketler = [
    (-1, 0),  # yukarı
    (1, 0),   # aşağı
    (0, -1),  # sol
    (0, 1)    # sağ
]

Örneğin robot:

(2, 3)

konumundaysa sağa giderse:

(2, 4)

konumuna geçer.

---

7. Geçerli Hücre Kontrolü

Robotun:

• labirentin dışına çıkmaması,

• duvara girmemesi

gerekir.

def gecerli_mi(labirent, konum):
    satir, sutun = konum

    if satir < 0 or satir >= len(labirent):
        return False

    if sutun < 0 or sutun >= len(labirent[0]):
        return False

    if labirent[satir][sutun] == "#":
        return False

    return True

---

8. BFS ile Labirenti Çözme

Şimdi ilk yapay zekâ yöntemimizi kullanalım:

Breadth-First Search – BFS

BFS:

Önce yakındaki seçenekleri, sonra daha uzaktaki seçenekleri araştırır.

BFS için Python'da deque kullanabiliriz.

from collections import deque

def bfs(labirent, baslangic, hedef):

    kuyruk = deque()
    kuyruk.append(baslangic)

    ziyaret_edilen = set()
    ziyaret_edilen.add(baslangic)

    onceki = {}

    hareketler = [
        (-1, 0),
        (1, 0),
        (0, -1),
        (0, 1)
    ]

    while kuyruk:

        mevcut = kuyruk.popleft()

        if mevcut == hedef:
            break

        for dr, dc in hareketler:

            yeni = (
                mevcut[0] + dr,
                mevcut[1] + dc
            )

            if gecerli_mi(labirent, yeni):
                
                if yeni not in ziyaret_edilen:

                    ziyaret_edilen.add(yeni)
                    kuyruk.append(yeni)

                    onceki[yeni] = mevcut

    return onceki, ziyaret_edilen

---

9. Bulunan Yolu Geri Oluşturma

BFS hedefe ulaştığında yalnızca hedefi bilmek yeterli değildir.

Hangi hücrelerden geçtiğini de bulmamız gerekir.

def yolu_olustur(onceki, baslangic, hedef):

    yol = []

    mevcut = hedef

    while mevcut != baslangic:

        yol.append(mevcut)

        if mevcut not in onceki:
            return []

        mevcut = onceki[mevcut]

    yol.append(baslangic)

    yol.reverse()

    return yol

---

10. Labirenti Çözdürelim

onceki, ziyaret = bfs(
    labirent,
    baslangic,
    hedef
)

yol = yolu_olustur(
    onceki,
    baslangic,
    hedef
)

print("Bulunan yol:")
print(yol)

print("Yol uzunluğu:", len(yol))
print("Ziyaret edilen hücre sayısı:", len(ziyaret))

Örneğin sonuç:

Bulunan yol:
[(0, 0), (1, 0), (1, 1), ... , (5, 6)]

Yol uzunluğu: ...
Ziyaret edilen hücre sayısı: ...

---

11. Yolu Görsel Olarak Gösterelim

Algoritmanın bulduğu yolu * karakteriyle gösterelim.

def labirenti_goster(labirent, yol):

    harita = [list(satir) for satir in labirent]

    for satir, sutun in yol:

        if harita[satir][sutun] not in ["S", "G"]:
            harita[satir][sutun] = "*"

    for satir in harita:
        print("".join(satir))

Kullanım:

labirenti_goster(labirent, yol)

Öğrenciler artık:

S**#...
.**#.#.
##*..#.
..*#...
.#***#.
.###**G

gibi bir sonuç görebilir.

---

12. Şimdi DFS'yi Deneyelim

BFS'nin ardından öğrencilere şu soruyu sorun:

"Robot çevresindeki bütün seçenekleri araştırmak yerine bir yola girip mümkün olduğunca derine gitse ne olur?"

İşte burada:

DFS – Depth-First Search

kullanılır.

def dfs(labirent, baslangic, hedef):

    yigin = [baslangic]

    ziyaret_edilen = set()
    ziyaret_edilen.add(baslangic)

    onceki = {}

    hareketler = [
        (-1, 0),
        (1, 0),
        (0, -1),
        (0, 1)
    ]

    while yigin:

        mevcut = yigin.pop()

        if mevcut == hedef:
            break

        for dr, dc in hareketler:

            yeni = (
                mevcut[0] + dr,
                mevcut[1] + dc
            )

            if gecerli_mi(labirent, yeni):

                if yeni not in ziyaret_edilen:

                    ziyaret_edilen.add(yeni)
                    yigin.append(yeni)

                    onceki[yeni] = mevcut

    return onceki, ziyaret_edilen

Sonra:

onceki, ziyaret = dfs(
    labirent,
    baslangic,
    hedef
)

yol = yolu_olustur(
    onceki,
    baslangic,
    hedef
)

labirenti_goster(labirent, yol)

---

13. BFS ve DFS'yi Karşılaştıralım

Öğrencilere şu tabloyu doldurtabilirsiniz:

Özellik	BFS	DFS
Yaklaşım	?	?
Veri yapısı	?	?
Önce neyi araştırır?	?	?
En kısa yolu garanti eder mi?	?	?
Bellek kullanımı	?	?

Ders sonunda beklenen temel cevap:

Özellik	BFS	DFS
Yaklaşım	Genişlik	Derinlik
Veri yapısı	Kuyruk	Yığın
Öncelik	Yakındaki düğümler	Derindeki düğümler
En kısa yol	Birim maliyetli grafikte evet	Hayır
Temel fikir	Katman katman ilerle	Bir yolda derinleş

---

14. A* Algoritmasına Geçiş

Şimdi öğrencilerden şu soruyu düşünmelerini isteyin:

"BFS bütün yönlere bakıyor. Acaba hedefin nerede olduğunu da hesaba katabilir miyiz?"

Evet.

Bunu yapan önemli algoritmalardan biri:

A* Algoritması

A* iki bilgiyi birlikte değerlendirir:

Şimdiye kadar ne kadar yol geldim?
+
Hedefe yaklaşık ne kadar kaldı?

Formül:

f(n) = g(n) + h(n)

g(n)

Başlangıçtan mevcut noktaya kadar olan gerçek maliyet.

h(n)

Mevcut noktadan hedefe olan tahmini maliyet.

f(n)

Toplam değerlendirme değeri.

---

15. Manhattan Mesafesi

Izgara şeklindeki bir labirentte basit bir sezgisel fonksiyon olarak Manhattan mesafesi kullanılabilir.

Formülü:

h = |x₁ - x₂| + |y₁ - y₂|

Örneğin:

Mevcut = (2, 3)
Hedef  = (5, 6)

ise:

h = |2 - 5| + |3 - 6|

h = 3 + 3

h = 6

Yani hedefe en az yaklaşık 6 yatay/dikey adım gerektiğini söyleyen bir tahmin elde ederiz.

---

16. A* Algoritmasının Basitleştirilmiş Python Uygulaması

import heapq


def manhattan(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


def astar(labirent, baslangic, hedef):

    acik_liste = []

    heapq.heappush(
        acik_liste,
        (0, baslangic)
    )

    onceki = {}

    g_maliyeti = {
        baslangic: 0
    }

    ziyaret_edilen = set()

    hareketler = [
        (-1, 0),
        (1, 0),
        (0, -1),
        (0, 1)
    ]

    while acik_liste:

        _, mevcut = heapq.heappop(acik_liste)

        ziyaret_edilen.add(mevcut)

        if mevcut == hedef:
            break

        for dr, dc in hareketler:

            yeni = (
                mevcut[0] + dr,
                mevcut[1] + dc
            )

            if not gecerli_mi(labirent, yeni):
                continue

            yeni_maliyet = g_maliyeti[mevcut] + 1

            if (
                yeni not in g_maliyeti
                or yeni_maliyet < g_maliyeti[yeni]
            ):

                g_maliyeti[yeni] = yeni_maliyet

                h = manhattan(
                    yeni,
                    hedef
                )

                f = yeni_maliyet + h

                heapq.heappush(
                    acik_liste,
                    (f, yeni)
                )

                onceki[yeni] = mevcut

    return onceki, ziyaret_edilen

---

17. A* ile Labirenti Çözelim

onceki, ziyaret = astar(
    labirent,
    baslangic,
    hedef
)

yol = yolu_olustur(
    onceki,
    baslangic,
    hedef
)

labirenti_goster(
    labirent,
    yol
)

print("Yol uzunluğu:", len(yol))
print("Ziyaret edilen hücre:", len(ziyaret))

Burada öğrencilerin özellikle dikkat etmesi gereken nokta:

Algoritmanın yalnızca yolu bulması değil, hedefe giderken hangi hücreleri değerlendirdiğidir.

---

18. Üç Algoritmayı Karşılaştıralım

Dersin en önemli kısmı burasıdır.

Öğrencilerden aşağıdaki tabloyu doldurmalarını isteyin:

Ölçüt	BFS	DFS	A*
Bulunan yol uzunluğu
Ziyaret edilen hücre
Hedefe ulaşma
Yaklaşım
Tahmin kullanıyor mu?

Daha sonra farklı labirentler oluşturup sonuçları tekrar ölçün.

---

19. Öğrenci Deneyi

Öğrencilere şu görevi verin:

Deney 1

Basit labirent:

S....
####.
....G

Deney 2

Daha karmaşık labirent:

S..#....
.#.#.##.
...#...G
##...#..
....#...

Deney 3

Kendi labirentinizi oluşturun.

Öğrenciler:

1. BFS çalıştırsın.

2. DFS çalıştırsın.

3. A* çalıştırsın.

4. Sonuçları kaydetsin.

5. Algoritmaları karşılaştırsın.

---

20. Öğrencilerin Keşfetmesini İstediğimiz Nokta

Öğrenciler uygulama sonucunda şu önemli fikre ulaşmalıdır:

Bir problemi çözmek için tek bir yapay zekâ yöntemi yoktur.

Aynı problem için farklı algoritmalar kullanılabilir.

Örneğin:

             LABİRENT
                 │
       ┌─────────┼─────────┐
       ↓         ↓         ↓
      BFS       DFS       A*
       │         │         │
       ↓         ↓         ↓
   Katmanlı    Derin      Tahminli
    arama      arama       arama

---

21. Daha Eğlenceli Bir Uygulama: Robot

Labirenti bir robotun hareket ettiği ortam olarak düşünelim.

🤖 → → → → 🎯

Öğrencilere:

"Robotun beynine hangi algoritmayı koyardınız?"

sorusunu yöneltin.

Ardından:

• BFS robotu nasıl yönlendiriyor?

• DFS nasıl yönlendiriyor?

• A* hedefi nasıl dikkate alıyor?

• Robotun her hareketinin maliyeti farklı olsaydı ne olurdu?

sorularını tartışın.

---

22. Bir Üst Seviyeye Geçiş

Bu uygulama, daha sonra pekiştirmeli öğrenme konusuna geçmek için de çok güzel bir köprü oluşturur.

Şimdiye kadar:

Algoritma:
"Şu kurala göre yolu ara."

dedik.

Pekiştirmeli öğrenmede ise:

Robot
 ↓
Hareket et
 ↓
Ödül / ceza al
 ↓
Deneyim kazan
 ↓
Daha iyi hareket etmeyi öğren

mantığına geçebiliriz.

Böylece öğrenciler:

Arama algoritması

ile

öğrenen ajan

arasındaki farkı görebilirler.

---

23. Dersin Sonunda Öğrenciye Sorulabilecek Sorular

Kavramsal

1. Arama problemi nedir?

2. Labirent neden bir arama problemi olarak düşünülebilir?

3. BFS nasıl çalışır?

4. DFS nasıl çalışır?

5. BFS ile DFS arasındaki temel fark nedir?

6. A* neden sezgisel bilgi kullanır?

7. g(n) neyi ifade eder?

8. h(n) neyi ifade eder?

9. f(n) nasıl hesaplanır?

10. Aynı problem neden farklı algoritmalarla çözülebilir?

Uygulamalı

11. Labirente yeni bir duvar ekleyin.

12. Başlangıç noktasını değiştirin.

13. Hedef noktasını değiştirin.

14. Labirentin boyutunu büyütün.

15. BFS, DFS ve A* sonuçlarını karşılaştırın.

16. Kendi labirentinizi tasarlayın.

---

24. Mini Proje

Öğrencilere şu proje verilebilir:

“Yapay Zekâlı Labirent Robotu”

Öğrencilerden Python ile:

• Labirent oluşturması,

• Başlangıç ve hedef belirlemesi,

• BFS uygulaması,

• DFS uygulaması,

• A* uygulaması,

• Bulunan yolu göstermesi,

• Ziyaret edilen hücreleri göstermesi,

• Algoritmaların sonuçlarını karşılaştırması

istenebilir.

Proje çıktısı

Örneğin:

================================
      YAPAY ZEKÂ LABİRENTİ
================================

Algoritma : A*

Başlangıç : (0,0)
Hedef     : (5,6)

Yol uzunluğu          : 12
Ziyaret edilen hücre : 18

Durum: HEDEFE ULAŞILDI ✓

---

🎓 Eğitmen İçin Ana Mesaj

Bu uygulamada amaç öğrencinin BFS veya DFS kodunu ezberlemesi değildir.

Asıl amaç şu düşünceyi kazandırmaktır:

“Bir yapay zekâ problemi tanımlanabilir; problem için durumlar ve eylemler belirlenebilir; ardından uygun bir arama veya öğrenme yöntemi seçilerek çözüm aranabilir.”

Bu nedenle 2 saatlik “Yapay Zekâ Yöntemleri” dersinizde akışın şu şekilde olması oldukça uygun olur:

20 dk: Yapay zekâda problem çözme mantığı
20 dk: Kural tabanlı sistemler
25 dk: Arama algoritmaları: BFS, DFS, A*
40 dk: 🧩 Mini labirent Python uygulaması
10 dk: Algoritmaların karşılaştırılması
5 dk: Pekiştirmeli öğrenmeye geçiş bağlantısı

Bu uygulama, sonraki derste “Makine Öğrenmesi: Veriden Öğrenme” konusuna geçiş için de doğal bir köprü oluşturur.