A Star Algorithm V2

Herkese merhabalar;

Geçen yazılarımızda a star algoritması ile ilgili bir yazı yayınlamıştık fakat final sınavlarının yaklaşmasıyla bu yazıyı güncellemek tekrar amacında avantajlı olacağını düşündüm.Önceki yazımıza ulaşmak için buraya tıklayabilirsiniz.

Giriş

A star algoritması bir arama optimizasyon algoritmasının temelinde gidilecek yere en kısa yoldan gitmeyi amaçlar

Algoritmayı çalıştırmak

Şimdi bu algoritmayı anlatanlarda bir kural olmuş bizde bu kuralı bozmayalım.Roma’da bir harita üzerinden algoritmayı çalıştıralım.

İlk durumumuz Arad ile başlıyoruz. Bir düğüm oluşturuyoruz ve açık listeye ekliyoruz. Açık listedeki tek şey bu olduğu için düğümü genişletiyoruz.

Açık listeyi, içindeki düğümleri g()+h() puanlarına göre sıralayan bir öncelik sırası (veya yığın) olarak düşünün.

Adım Adım A Start Search

1.Adım

Şimdi başlangıç noktası olarak arad seçildiği için arad gidilebilecek 3 şehir var.Amac Bucharest şehrine gitmek.Geçen yazımızdada bahsettimiz üzere gidilen şehirleri bir dizide tutarız.

Gidilenler:Arad

2.Adım

Arad üzerinden hangi şehirlere gidebiliriz fakat bu gidilen şehir en az maliyetli olacak.En az maliyetli şehire gittik fakat gördüğümüz şehirleride Gidilenler listesine atmalıyız.

Gidilenler: Sibiu,Timisoara,Zerind

3.Adım

Bu adımda da geçen adımda gidilen yer sibiu olduğu için sibiu’dan gidilebilecek minimum maliyetli şehri buluyoruz.Burada Arad şehrini daha önce gittiğimiz için direk eliyoruz şayet Arad min. Maliyetli şehir olarak bu adımda secilseydi gene alamazdık çünkü gidilen yerlere bir daha gitmiyoruz.

Gidilenler:Rimricu Vicea,Fagaras,Timisoara,Zerind,Arad(Elendi),Oradea

4.Adım

Bir önceki adımda Rimricu Vicea şehrine gitmiştik.Bu adımda bu şehirden gidilebilecek tüm şehirleri çıkartıyoruz.

Gidilenler: Fagaras,Pitesti,Timisoara,Zerind,Craiova,Sibiu(Elendi),Oradea

Bu şehirden sibiu gidiş olduğu için sibiu da bizim eski gidilenler listelerimizde olduğu için bu şehri direk eliyoruz.Burada en az maliyetli olan şehir Pitesti sibiu gidilenlerden çıkardığımıza göre genel anlamda toparlarsak grafımız alttaki görseldeki gibi gidilenler kümesinide güncel olarak yazar isek;

Fagaras’ı genişlettiğimizde tekrar Sibiu’yu buluyoruz. Gidilenler listesine eklenmiyor.

Bükreş’i de bulduk ama işimiz bitmedi. Hedef düğümü “genişleten”e kadar algoritma sona ermez

Gidilenler:Pitesti,Timisoara,Zerind,Bucharest,Craiova,Oradea

5.Adım:

Bükreş için daha iyi bir değer bulduk; bu yüzden gidilenler listesinde daha üst sıralara taşındı. Ayrıca Craiova için daha kötü bir değer bulduk bunu görmezden geliyoruz.Ve tabii ki yine Rimricu Vicea ile karşılaştık. Zaten bir kez genişletildiğinden ötürü, onu Açık Listeye yeniden ekleyemiyoruz.

Gidilenler:Bucharest,Timisoara,Zerind,Craiova,Rimricu Vicea(Elendi),Oradea

Şimdi gideceğimiz şehir listenin en başında gözüktüğü için bu şehri genişletmeye gerek yok bakın Bucharest için 2 farklı yol vardı bu algoritma ilk yolu kabul etseydi daha az maliyetli olan Pitesti şehrini tanımıyacaktı.

Bu sebeple tüm alternatif şehirleri geziyoruz tabi buda algoritmanın yavaş çalışmasını sağlıyor ama optimum sonucu vermekte başarılı.

Son

Buraya kadar okuduğunuz için teşekkür ederim.Herkese sağlıklı günler