Yapay Zekada Bilgilendirilmiş Arama hakkında her şey

Bilgilendirilmiş arama, aramasını bir sorun alanı boyunca yönlendirmek için alana özgü bilgiyi kullanan bir tür arama algoritmasıdır. Navigasyon sistemlerinden oyun oynamaya, doğal dil işlemeden tedarik zinciri yönetimine ve yapay zekada daha bilinçli arama, farklı sorunları çözmek için gereken süreyi ve hesaplama kaynaklarını önemli ölçüde azalttı.

Bilgilendirilmiş arama algoritmaları , aramayı yönlendirmek için alana özgü bilgileri kullanarak ilgisiz veya daha az umut verici yolları hızla ortadan kaldırarak aramanın en umut verici seçeneklere odaklanmasına olanak tanır. Bunu yapmak için, AI'daki bu tür arama algoritmaları, aramanın verimliliğini ve hızını artırmak için buluşsal yöntemler kullanır.

Dünyanın en iyi Üniversitelerinden Makine Öğrenimi Kursuna kaydolun . Kariyerinizi hızlandırmak için Master, Executive PGP veya Advanced Certificate Programları kazanın.

Bu makale , yapay zekada bilinçli arama kavramını , sezgisel işlevlerini, algoritma örneklerini ve bunların avantajlarını ve dezavantajlarını tartışacaktır.

Sezgisel işlev

Basit bir ifadeyle buluşsal işlev, bir arama probleminde bir hedef duruma olan mesafeyi veya maliyeti tahmin etmek için bir pratik kural veya "en iyi tahmin" kullanan bir problem çözme yaklaşımıdır. Sezgisel işlev, hedef durumun mevcut durumdan ne kadar uzakta olduğunu tahmin eder ve bu, bir arama algoritmasını hedefe doğru yönlendirmek için kullanılabilir.

Bilgiye dayalı arama algoritmaları, hangi yolun izleneceğine ilişkin bilinçli kararlar vermek için bu işlevleri ek bir bilgi kaynağı olarak kullanır. Bu nedenle bilgili arama algoritmalarında buluşsal işlevler çok önemlidir.

Sezgisel işleve ilişkin gerçek hayattan örnekler

Sezgisel işlevleri daha iyi anlamak için işte bazı gerçek hayattan örnekler:

• Klasik "kayan kiremit yapboz" oyununda, basit bir buluşsal işlev, hedef konfigürasyona kıyasla mevcut konfigürasyondaki yersiz karoların sayısını saymak olabilir. Yerinde olmayan karolar ne kadar çoksa, mevcut durum hedef durumdan o kadar uzaktadır.
• Satrançta buluşsal bir işlev, tahtadaki her bir taşa göreceli gücü ve konumuna göre bir değer atamak ve mevcut oyuncunun avantajını veya dezavantajını tahmin etmek için bu değerlerin toplamını kullanmak olabilir. Bu buluşsal işlev, bir arama algoritmasını daha iyi bir konumla sonuçlanması muhtemel hareketlere yönlendirmek için kullanılabilir.

Bunu hallettikten sonra, şimdi ilerleyelim ve yapay zekada bilinçli arama algoritmalarının en çok kullanılan örneklerinden bazılarını anlayalım.

Bilgilendirilmiş Arama Algoritmalarına Örnekler

En sık kullanılan bilinçli arama algoritmalarından ikisi, en iyi ilk arama ve A* aramasını içerir. Bu iki algoritmayı bazı örnekler, avantajlar, dezavantajlar ve bunların Python uygulamasıyla birlikte anlayalım:

1. En İyi İlk Arama

En iyi ilk arama, buluşsal bir işleve göre önce en umut verici düğümü genişleten bir arama algoritmasıdır. Algoritma ilk düğümde başlar ve keşfedilecek bir sonraki düğüm olarak en düşük buluşsal değere sahip çocuğu seçerek tüm alt düğümlerini inceler. Bu süreç, hedef düğüm bulunana veya tüm düğümler keşfedilene kadar devam eder.

En iyi ilk arama – resimli bir örnek

İşte en iyi ilk aramayı göstermek için basit bir örnek:

Evinizden yakındaki bir markete giden en kısa yolu bulmaya çalıştığınızı varsayalım. Yakındaki birkaç yerden markete olan mesafeyi biliyorsunuz, ancak tam olarak nasıl bir yol izleyeceğinizi bilmiyorsunuz. En iyi ilk aramayı kullanarak bu sorunu çözmek için şunları yapabilirsiniz:

1. Ev konumunuzdan başlayın ve bakkala olan mesafesine göre yakındaki her konum için buluşsal değeri hesaplayın.
2. Keşfedilecek bir sonraki düğüm olarak en düşük buluşsal değere sahip yakındaki konumu seçin.
3. Yakındaki konumdan alt konumlarının her biri için buluşsal değeri hesaplayın ve keşfedilecek bir sonraki düğüm olarak en düşük buluşsal değere sahip olanı seçin.
4. Markete varana kadar bu işlemi tekrarlayın.

En iyi ilk arama – Python uygulaması

Python'da en iyi ilk arama algoritmasını şu şekilde uygulayabilirsiniz:

yığınq'yi içe aktar

def en iyi_ilk_arama(başlangıç_durumu, hedef_durumu, buluşsal_func, eylemler_func, maliyet_func):

# sınırı ve keşfedilen seti başlat

sınır = [(heuristic_func(başlangıç_durumu, hedef_durum), başlangıç_durumu)]

keşfedildi = ayarla()

# yolu ve maliyeti başlat

yol = {}

maliyet = {}

yol[başlangıç_durumu] = Yok

maliyet[başlangıç_durumu] = 0

iken sınır:

# sınırdan en düşük buluşsal değere sahip düğümü al

(h, current_state) = yığınq.heappop(sınır)

current_state == gol_durumu ise:

# hedef duruma ulaşılırsa yolu döndürür

dönüş yolu

explored.add(current_state)

# mevcut durumdan olası eylemleri üret

action_func(current_state) içindeki eylem için:

next_state = eylem(geçerli_durum)

# yeni yolun maliyetini hesapla

yeni_maliyet = maliyet[geçerli_durum] + maliyet_func(geçerli_durum, eylem, sonraki_durum)

next_state keşfedilen içinde değilse ve next_state [sınırda (h, state) için durum] içinde değilse:

# yeni eyaleti sınıra ekle

yığınq.heappush(sınır, (heuristic_func(sonraki_durum, hedef_durum), sonraki_durum))

yol[sonraki_durum] = geçerli_durum

maliyet[sonraki_durum] = yeni_maliyet

# hedef durumuna ulaşılamıyorsa Yok'u döndür

dönüş Yok

Gördüğünüz gibi, aşağıdaki işlevleri tanımlamanız gerekecek:

• buluşsal_func(geçerli_durum, hedef_durum): Bu işlev, mevcut durumu ve hedef durumu girdi olarak alır ve mevcut durumdan hedef duruma ulaşma maliyetinin bir tahminini döndürür.
• action_func(current_state): Bu işlev mevcut durumu girdi olarak alır ve mevcut durumdan alınabilecek eylemlerin bir listesini döndürür.
• cost_func(current_state, action, next_state): Bu işlev, mevcut durumu, bir eylemi ve bir sonraki durumu girdi olarak alır ve mevcut durumdan bir sonraki duruma geçmenin maliyetini döndürür.

En İyi İlk Arama Örneği

başlangıç_durumu = (0, 0)

gol_durumu = (4, 4)

def buluşsal_func(geçerli_durum, hedef_durum):

dönüş abs(current_state[0] – gol_durumu[0]) + abs(current_state[1] – gol_durumu[1])

def action_func(current_state):

eylemler = []

current_state[0] > 0 ise:

action.append(lambda durumu: (durum[0]-1, durum[1]))

current_state[0] < 4 ise:

action.append(lambda durumu: (durum[0]+1, durum[1]))

geçerli_durum[1] > 0 ise:

action.append(lambda durumu: (durum[0], durum[1]-1))

current_state[1] < 4 ise:

action.append(lambda durumu: (durum[0], durum[1]+1))

dönüş eylemleri

def maliyet_func(geçerli_durum, eylem, sonraki_durum):

dönüş 1

yol = en iyi_ilk_arama(başlangıç_durumu, hedef_durumu, buluşsal_func, eylemler_func, maliyet_func)

eğer yol:

# başlangıç ​​durumundan hedef duruma giden yolu oluşturun

akım_durumu = hedef_durumu

current_state != start_state iken:

yazdır(geçerli_durum)

current_state = yol[current_state]

yazdır(başlangıç_durumu)

başka:

print(“Hedef durumuna ulaşılamıyor.”)

En İyi İlk Aramanın Avantajları

• Genişlik öncelikli aramaya kıyasla, en iyi ilk aramanın zaman karmaşıklığı daha düşüktür.
• En iyi ilk arama, hem BFS hem de DFS algoritmalarının avantajlarını elde eder ve uygular.

En İyi İlk Aramanın Dezavantajları

• Bazen düşünülenden daha fazla mesafe kat edebilir.
• Bir döngüde takılma şansı oldukça yüksektir.

Arama

A* araması, hem başlangıç ​​düğümünden bir düğüme ulaşmanın maliyetini hem de aramasına rehberlik etmesi için hedef düğüme ulaşmak için kalan maliyetin bir tahminini kullanan bir arama algoritmasıdır. Algoritma ilk düğümde başlar ve keşfedilecek bir sonraki düğüm olarak en düşük birleşik maliyete ve tahmini kalan maliyete sahip çocuğu seçerek tüm alt düğümlerini inceler. Bu süreç, hedef düğüm bulunana veya tüm düğümler keşfedilene kadar devam eder.

A* araması – resimli bir örnek

Evinizden yakındaki bir markete giden en kısa yolu bulmaya çalıştığınız önceki örneğe tekrar bakalım. Şimdi şunları yapabilirsiniz:

1. Ev konumunuzdan başlayın ve evinizden o konuma olan mesafenin toplamı olarak yakındaki her bir konuma ulaşmanın toplam maliyetini ve bu konumdan markete ulaşmak için tahmini kalan maliyeti hesaplayın.
2. Keşfedilecek bir sonraki düğüm olarak en düşük toplam maliyete sahip yakındaki konumu seçin.
3. Bu yakındaki konumdan, o konumdan alt konuma olan mesafenin toplamı olarak alt konumlarının her biri için toplam maliyeti, başlangıç ​​düğümünden o konuma ulaşma maliyeti ve bakkala ulaşmak için tahmini kalan maliyeti hesaplayın. o çocuk konumundan. Keşfedilecek bir sonraki düğüm olarak en düşük toplam maliyete sahip alt konumu seçin.
4. Markete varana kadar bu işlemi tekrarlayın.

Burada dikkat edilmesi gereken önemli bir nokta, A* Search'ün hedef duruma giden en kısa yolu bulmayı garanti eden optimal bir arama algoritması olmasıdır. Geniş arama alanı olan problemlerde etkilidir ve video oyunlarında, robotikte ve rota planlamada yaygın olarak kullanılır. Bununla birlikte, etkili olabilmesi için iyi tanımlanmış bir buluşsal işlev gerektirir. Bu nedenle algoritma, çok sayıda düğüm içeren karmaşık problemlerde bellek yoğun olabilir ve yavaşlayabilir.

A* arama – Python uygulaması

Python programlamayı kullanarak A* arama algoritmasını şu şekilde uygulayabilirsiniz:

yığınq'yi içe aktar

def astar_search(başlangıç_durumu, hedef_durumu, buluşsal_func, eylemler_func, maliyet_func):

# sınırı ve keşfedilen seti başlat

sınır = [(heuristic_func(başlangıç_durumu, hedef_durum), başlangıç_durumu)]

keşfedildi = ayarla()

# yolu ve maliyeti başlat

yol = {}

maliyet = {}

yol[başlangıç_durumu] = Yok

maliyet[başlangıç_durumu] = 0

iken sınır:

# sınırdan en düşük f değerine sahip düğümü al

(f, current_state) = yığınq.heappop(sınır)

current_state == gol_durumu ise:

# hedef duruma ulaşılırsa yolu döndürür

dönüş yolu

explored.add(current_state)

# mevcut durumdan olası eylemleri üret

action_func(current_state) içindeki eylem için:

next_state = eylem(geçerli_durum)

# yeni yolun maliyetini hesapla

yeni_maliyet = maliyet[geçerli_durum] + maliyet_func(geçerli_durum, eylem, sonraki_durum)

next_state keşfedilen içinde değilse ve next_state [sınırda (f, durum) için durum] içinde değilse:

# yeni eyaleti sınıra ekle

yığınq.heappush(sınır, (yeni_maliyet + sezgisel_func(sonraki_durum, hedef_durum), sonraki_durum))

yol[sonraki_durum] = geçerli_durum

maliyet[sonraki_durum] = yeni_maliyet

elif sonraki_durum [sınırda (f, durum) için durum] ve yeni_maliyet < maliyet[sonraki_durum]:

# sınırdaki mevcut durumun maliyetini güncelleyin

index = [i for (i, (f, state)) in enumerate(frontier) if state == next_state][0]

sınır[dizin] = (yeni_maliyet + buluşsal_func(sonraki_durum, hedef_durum), sonraki_durum)

yol[sonraki_durum] = geçerli_durum

maliyet[sonraki_durum] = yeni_maliyet

# hedef durumuna ulaşılamıyorsa Yok'u döndür

dönüş Yok

En İyi Çevrimiçi Makine Öğrenimi Kursları ve Yapay Zeka Kursları

A* Arama Örneği

İşte astar_search işlevini bu işlevlerle nasıl kullanabileceğinize bir örnek:

başlangıç_durumu = (0, 0)

gol_durumu = (4, 4)

def buluşsal_func(geçerli_durum, hedef_durum):

dönüş abs(current_state[0] – gol_durumu[0]) + abs(current_state[1] – gol_durumu[1])

def action_func(current_state):

eylemler = []

current_state[0] > 0 ise:

action.append(lambda durumu: (durum[0]-1, durum[1]))

current_state[0] < 4 ise:

action.append(lambda durumu: (durum[0]+1, durum[1]))

geçerli_durum[1] > 0 ise:

action.append(lambda durumu: (durum[0], durum[1]-1))

current_state[1] < 4 ise:

action.append(lambda durumu: (durum[0], durum[1]+1))

dönüş eylemleri

def maliyet_func(geçerli_durum, eylem, sonraki_durum):

dönüş 1

yol = astar_search(başlangıç_durumu, hedef_durumu, buluşsal_func, eylemler_func, maliyet_func)

eğer yol:

# başlangıç ​​durumundan hedef duruma giden yolu oluşturun

akım_durumu = hedef_durumu

current_state != start_state iken:

yazdır(geçerli_durum)

current_state = yol[current_state]

yazdır(başlangıç_durumu)

başka:

print(“Hedef durumuna ulaşılamıyor.”)

A* Aramanın Avantajları

• Önde gelen buluşsal tekniklerden biridir.
• A* araması, karmaşık arama sorunlarını çözmek için kullanılabilir

Trend Olan Makine Öğrenimi Becerileri

A* Aramanın Dezavantajları

• A* arama performansı, buluşsal algoritmaların doğruluğuna büyük ölçüde dayanır.
• Düşük arama verimliliğine sahiptir.

Popüler AI ve ML Blogları ve Ücretsiz Kurslar

Götürmek

Bilgilendirilmiş arama algoritmaları, bilgisayarın bir hedef durumu verimli ve etkili bir şekilde aramasına izin verdiği için yapay zekada çok önemlidir. Bu algoritmalar, olası her hareketin maliyetini tahmin etmek ve arama sürecini hedef duruma doğru yönlendirmek için buluşsal işlevler kullanır. En İyi İlk Arama ve A* Arama, çeşitli alanlarda yaygın olarak kullanılan bilinçli arama algoritmalarına örnektir. Bununla birlikte, iyi tanımlanmış bir sezgisel işlev, bilinçli arama algoritmalarının başarısı için kritik öneme sahiptir.

Yapay zeka ve makine öğrenimi hakkında daha fazla bilgi edinmekle ilgileniyorsanız, Liverpool John Moores Üniversitesi tarafından sunulan Grad's Machine Learning & Yapay Zeka Yüksek Lisans programına göz atın . Bu program, bilinçli arama gibi algoritmalar da dahil olmak üzere çeşitli makine öğrenimi ve yapay zeka konularını kapsar. Bu programı alarak, AI ile ilgili çeşitli kariyerlerde başarılı olmak için ihtiyaç duyduğunuz bilgi ve becerileri kazanabilirsiniz.

Yönetim, Veri Bilimi, Makine Öğrenimi, Dijital Pazarlama ve Teknoloji alanlarında upGrad tarafından sunulanücretsiz kurslarımızada göz atabilirsiniz.Tüm bu kurslarda birinci sınıf öğrenme kaynakları, haftalık canlı dersler, endüstri ödevleri ve kurs bitirme sertifikası bulunur - hepsi ücretsiz!