AI - Popüler Arama Algoritmaları

Arama, AI'da evrensel problem çözme tekniğidir. Taş oyunları, Sudoku, bulmaca vb. Gibi bazı tek oyunculu oyunlar vardır. Arama algoritmaları, bu tür oyunlarda belirli bir konumu aramanıza yardımcı olur.

Tek Aracılı Yol Bulma Sorunları

3X3 sekiz kiremit, 4X4 on beş kiremit ve 5X5 yirmi dört taş bulmacası gibi oyunlar, tek ajanlı yol bulma zorluklarıdır. Boş bir karo içeren bir karo matrisinden oluşurlar. Oyuncunun, bir hedefi gerçekleştirmek amacıyla karoları dikey veya yatay olarak boş bir alana kaydırarak düzenlemesi gerekir.

Tek ajanlı yol bulma problemlerinin diğer örnekleri, Seyyar Satıcı Problemi, Rubik Küpü ve Teorem Kanıtlamadır.

Arama Terminolojisi

Problem Space- Aramanın gerçekleştiği ortamdır. (Bu durumları değiştirmek için bir dizi durum ve işleç)
Problem Instance - Başlangıç durumu + Hedef durumdur.
Problem Space Graph- Sorunlu durumu temsil eder. Durumlar düğümlerle gösterilir ve operatörler kenarlarla gösterilir.
Depth of a problem - İlk Durumdan hedef duruma kadar en kısa yolun veya en kısa operatör dizisinin uzunluğu.
Space Complexity - Bellekte depolanan maksimum düğüm sayısı.
Time Complexity - Oluşturulan maksimum düğüm sayısı.
Admissibility - Her zaman en uygun çözümü bulmaya yönelik bir algoritmanın özelliği.
Branching Factor - Sorunlu uzay grafiğindeki ortalama alt düğüm sayısı.
Depth - Başlangıç durumundan hedef duruma en kısa yolun uzunluğu.

Brute-Force Arama Stratejileri

Herhangi bir alana özgü bilgiye ihtiyaç duymadıkları için en basitleridir. Az sayıda olası durumla iyi çalışırlar.

Gereksinimler -

Eyalet açıklaması
Bir dizi geçerli operatör
Başlangıç hali
Hedef durum açıklaması

Kapsamlı Arama

Kök düğümden başlar, önce komşu düğümleri araştırır ve bir sonraki seviye komşularına doğru hareket eder. Çözüm bulunana kadar her seferinde bir ağaç oluşturur. FIFO kuyruk veri yapısı kullanılarak uygulanabilir. Bu yöntem çözüme giden en kısa yolu sağlar.

Eğer branching factor(belirli bir düğüm için ortalama alt düğüm sayısı) = b ve derinlik = d, ardından d = b ^d düzeyindeki düğüm sayısı .

En kötü durumda oluşturulan toplam düğüm sayısı b + b ² + b ³ +… + b ^d'dir .

Disadvantage- Her düğüm seviyesi bir sonrakini oluşturmak için kaydedildiğinden, çok fazla bellek alanı tüketir. Düğümleri depolamak için alan gereksinimi üsteldir.

Karmaşıklığı düğüm sayısına bağlıdır. Yinelenen düğümleri kontrol edebilir.

Derinlik öncelikli arama

LIFO yığın veri yapısı ile özyinelemeli olarak uygulanır. Genişlik-İlk yöntemiyle aynı düğüm kümesini yalnızca farklı sırayla oluşturur.

Tek yoldaki düğümler, kökten yaprak düğüme her yinelemede depolandığından, düğümleri depolamak için alan gereksinimi doğrusaldır. Dallanma faktörü b ve derinlik m olarak , depolama alanı bm'dir.

Disadvantage- Bu algoritma tek bir yolda sonlanıp sonsuza kadar devam edemez. Bu sorunun çözümü, bir kesme derinliği seçmektir. İdeal kesme d ise ve seçilen kesme d' den küçükse , bu algoritma başarısız olabilir. Seçilen kesme d' den fazlaysa , yürütme süresi artar.

Karmaşıklığı, yolların sayısına bağlıdır. Yinelenen düğümleri kontrol edemez.

Çift Yönlü Arama

Ortak bir durumu belirlemek için her ikisi de buluşana kadar başlangıç durumundan ileri ve hedef durumdan geriye doğru arama yapar.

Başlangıç durumundan gelen yol, hedef durumundan ters yol ile birleştirilir. Her arama, toplam yolun yalnızca yarısına kadar yapılır.

Tekdüzen Maliyet Araması

Sıralama, bir düğüme giden yolun maliyetini artırarak yapılır. Her zaman en düşük maliyetli düğümü genişletir. Her geçişin maliyeti aynı ise, Önce Genişlik Araması ile aynıdır.

Yolları artan maliyet sırasına göre araştırır.

Disadvantage- Maliyet ≤ C * olan birden çok uzun yol olabilir. Tekdüzen Maliyet araması hepsini keşfetmelidir.

Yinelemeli Derinleştirme Derinliği İlk Arama

Seviye 1'e derinlemesine arama yapar, baştan başlar, seviye 2'ye kadar derinlemesine arama yapar ve çözüm bulunana kadar bu şekilde devam eder.

Tüm alt düğümler oluşturulana kadar asla bir düğüm oluşturmaz. Yalnızca bir yığın düğüm kaydeder. Algoritma d derinliğinde bir çözüm bulduğunda sona erer . D derinliğinde oluşturulan düğüm sayısı b ^d ve d-1 derinliğinde b ^d-1'dir.

Çeşitli Algoritma Karmaşıklıklarının Karşılaştırılması

Algoritmaların performansını çeşitli kriterlere göre görelim -

Kriter	Önce Genişlik	Önce Derinlik	Çift yönlü	Tekdüzen Maliyet	Etkileşimli Derinleştirme
Zaman	b ^d	b ^m	b g ^{/ 2}	b ^d	b ^d
Uzay	b ^d	b ^m	b g ^{/ 2}	b ^d	b ^d
Optimallik	Evet	Hayır	Evet	Evet	Evet
Tamlık	Evet	Hayır	Evet	Evet	Evet

Bilgilendirilmiş (Sezgisel) Arama Stratejileri

Çok sayıda olası durumla büyük problemleri çözmek için, arama algoritmalarının verimliliğini artırmak için probleme özgü bilginin eklenmesi gerekir.

Sezgisel Değerlendirme İşlevleri

İki durum arasındaki en uygun yolun maliyetini hesaplarlar. Kayan kiremit oyunları için sezgisel bir işlev, her bir karonun hedef durumundan yaptığı hamle sayısını sayarak ve tüm karolar için bu sayıda hamle ekleyerek hesaplanır.

Saf Sezgisel Arama

Düğümleri sezgisel değerlerine göre genişletir. İki liste oluşturur, zaten genişletilmiş düğümler için kapalı bir liste ve oluşturulan ancak genişletilmemiş düğümler için açık bir liste.

Her yinelemede, minimum sezgisel değere sahip bir düğüm genişletilir, tüm alt düğümleri oluşturulur ve kapalı listeye yerleştirilir. Ardından, sezgisel işlev alt düğümlere uygulanır ve bunlar, sezgisel değerlerine göre açık listeye yerleştirilir. Daha kısa yollar kaydedilir ve daha uzun yollar atılır.

Arama

En İyi İlk aramanın en iyi bilinen şeklidir. Zaten pahalı olan genişleyen yolları önler, ancak önce çoğu umut verici yolu genişletir.

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

g (n) düğüme ulaşma maliyeti (şimdiye kadarki)
h (n) düğümden hedefe ulaşmak için tahmini maliyet
f (n) n'den hedefe giden yolun tahmini toplam maliyeti. Öncelik kuyruğu kullanılarak f (n) artırılarak gerçekleştirilir.

Açgözlü En İyi İlk Arama

Hedefe en yakın olduğu tahmin edilen düğümü genişletir. Düğümleri f (n) = h (n) 'ye göre genişletir. Öncelik kuyruğu kullanılarak uygulanır.

Disadvantage- Döngülere sıkışabilir. Optimal değil.

Yerel Arama Algoritmaları

Muhtemel bir çözümden başlayıp ardından komşu çözüme geçerler. Bitmeden önce herhangi bir zamanda kesilse bile geçerli bir çözüm döndürebilirler.

Hill-Climbing Search

Bir probleme gelişigüzel bir çözümle başlayan ve çözümün tek bir öğesini aşamalı olarak değiştirerek daha iyi bir çözüm bulmaya çalışan yinelemeli bir algoritmadır. Değişiklik daha iyi bir çözüm üretirse, yeni bir çözüm olarak kademeli bir değişiklik alınır. Bu işlem, daha fazla iyileştirme olmayana kadar tekrar edilir.

Hill-Climbing (problem) fonksiyonu, yerel maksimum olan bir durum döndürür.

inputs: problem, a problem
local variables: current, a node
                 neighbor, a node
current <-Make_Node(Initial-State[problem])
loop
   do neighbor <- a highest_valued successor of current
      if Value[neighbor] ≤ Value[current] then
      return State[current]
      current <- neighbor				  
	
end

Disadvantage - Bu algoritma ne tam ne de optimal.

Yerel Işın Arama

Bu algoritmada, herhangi bir zamanda k sayıda durumu tutar. Başlangıçta bu durumlar rastgele oluşturulur. Bu k durumlarının halefleri, nesnel işlevin yardımıyla hesaplanır. Bu haleflerden herhangi biri amaç fonksiyonunun maksimum değeriyse, algoritma durur.

Aksi takdirde (ilk k durumları ve durumların ardıllarının k sayısı = 2k) durumları bir havuza yerleştirilir. Havuz daha sonra sayısal olarak sıralanır. En yüksek k durumları yeni başlangıç durumları olarak seçilir. Bu süreç maksimum değere ulaşılana kadar devam eder.

function BeamSearch ( problem, k ), bir çözüm durumu döndürür.

start with k randomly generated states
loop
   generate all successors of all k states
   if any of the states = solution, then return the state
   else select the k best successors
end

Benzetimli tavlama

Tavlama, fiziksel özelliklerini değiştirmek için iç yapısını değiştirmek için bir metalin ısıtılması ve soğutulması işlemidir. Metal soğuduğunda yeni yapısı ele geçirilir ve metal yeni elde edilen özelliklerini korur. Simüle tavlama işleminde sıcaklık değişken tutulur.

Başlangıçta sıcaklığı yüksek olarak ayarlıyoruz ve ardından algoritma ilerledikçe yavaşça 'soğumasına' izin veriyoruz. Sıcaklık yüksek olduğunda, algoritmanın yüksek frekanslı daha kötü çözümleri kabul etmesine izin verilir.

Başlat

K = 0'ı başlatın; L = tamsayı değişken sayısı;
İ → j'den performans farkını Δ arayın.
Eğer Δ <= 0 ise başka türlü kabul et, eğer exp (-Δ / T (k))> rastgele (0,1) ise kabul et;
L (k) adımları için 1. ve 2. adımları tekrarlayın.
k = k + 1;

Ölçütler karşılanana kadar 1'den 4'e kadar olan adımları tekrarlayın.

Son

Seyahat Eden Satıcı Sorunu

Bu algoritmada amaç, bir şehirden başlayan, tüm şehirleri tam olarak bir kez ziyaret eden ve aynı başlangıç şehrinde biten düşük maliyetli bir tur bulmaktır.

Start
   Find out all (n -1)! Possible solutions, where n is the total number of cities.
   Determine the minimum cost by finding out the cost of each of these (n -1)! solutions.
   Finally, keep the one with the minimum cost.
end