İçeriğe atla
Arama sonuçlarına dön

A* Arama Algoritması

Ortaya koyan
Peter E. Hart, Nils J. Nilsson, and Bertram Raphael
Yıl
1968
Tür
algorithm
Aile
Graph Algorithms

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

Peter E. Hart, Nils J. Nilsson ve Bertram Raphael tarafından 1968'de geliştirilen A* Arama Algoritması, Dijkstra algoritmasının faydalarını sezgisel yönlendirme ile birleştiren optimal bir yol bulma algoritmasıdır.

Başlangıçtan olan gerçek mesafeyi hedef mesafesiyle dengeleyerek en kısa yolu verimli bir şekilde bulur.

Yöntemin mantığı

A*, f(n) = g(n) + h(n) değerlendirme fonksiyonunu kullanır; burada g(n), başlangıçtan n düğümüne olan gerçek maliyettir ve h(n), hedefe kalan maliyetin sezgisel bir tahminidir. En düşük f(n) değerine sahip düğümleri keşfederek, algoritma arama alanını hedefe doğru verimli bir şekilde daraltırken, sezgisel kabul edilebilir olduğunda (asla aşırı tahmin etmediğinde) optimalliği korur. Bu, A*'yı bilgisiz arama yöntemlerinden önemli ölçüde daha hızlı hale getirirken, optimal yolu bulmayı garanti eder.

Tarih

Hart, Nilsson ve Raphael, 1968'de A*'yı yayınlayarak, Dijkstra algoritmasına sezgisel bilgi eklemenin, optimalliği korurken arama verimliliğini önemli ölçüde artırabileceğini gösterdiler. Algoritma, yapay zeka ve operasyon araştırmalarında temel oluşturdu. Sonraki gelişmeler arasında çift yönlü A*, IDA* (iteratif derinleştirme) ve çeşitli sezgisel iyileştirmeler yer almaktadır. A*, modern oyun motorları ve robotik sistemlerinde yol bulma için standart seçim olmaya devam etmektedir.

Ne zaman kullanılır?

İyi bir sezgisel fonksiyonun mevcut olduğu grafiklerde optimal yollar bulmanız gerektiğinde A*'yı uygulayın. Özellikle oyunlarda, robotikte ve yönlendirme planlamasında, bilgilendirilmiş aramanın hesaplamayı önemli ölçüde azaltabileceği yol bulma için etkilidir. Hızın önemli olduğu ancak optimalliğin gerekli olduğu durumlarda kullanın. Güvenilir bir sezgisel fonksiyonun olmadığı durumlar için bunun yerine Dijkstra algoritmasını kullanın.

Sınırlar ve dikkat edilmesi gerekenler

  • Optimallik, sezgisel fonksiyonun kabul edilebilirliğine bağlıdır
  • Kötü veya kabul edilemez sezgisel fonksiyonlarla performans önemli ölçüde düşer
  • Büyük arama alanlarında bellek kullanımı önemli olabilir (açık ve kapalı kümeleri tutar)
  • İyi sezgisel fonksiyonlar tasarlamak için açık alan bilgisi gerektirir

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • Sezgisel kabul edilebilir olduğunda optimal yol bulma
  • İyi sezgisel fonksiyonlar mevcut olduğunda Dijkstra veya genişlik öncelikli aramadan çok daha hızlı
  • Esnek: herhangi bir kabul edilebilir sezgisel fonksiyonla çalışır
  • Tek hedefli yol bulma problemleri için çok uygundur
  • Oyunlarda, robotikte ve navigasyon sistemlerinde kapsamlı gerçek dünya doğrulaması

Uygulama alanları

  • Video oyunu yol bulma: dinamik oyun ortamlarında gerçek zamanlı YZ gezintisi
  • Robot hareket planlaması: engellerden kaçınan otonom robotlar için optimal yol planlaması
  • GPS navigasyonu: yol ağları ve trafiği dikkate alarak verimli rotalar hesaplama
  • Bulmaca çözme: 15-bulmaca gibi kombinatoryal problemlerde optimal çözümler bulma
  • Ağ yönlendirme: bağlantı kalitesi sezgisel fonksiyonlarıyla verimli paket rotaları belirleme
  • Biyoenformatik: dizi hizalama ve protein yapısı tahmin aramaları

Nasıl çalışır?

Nasıl çalışır?

1

Başlangıç düğümüyle bir açık küme oluşturun, g-değerini (başlangıçtan maliyet) sıfıra ayarlayın ve sezgisel fonksiyonu kullanarak h-değerini hesaplayın.

2

Açık kümeden en düşük f-değerine sahip düğümü seçin, ziyaret edilmemiş komşuları için f-değerlerini hesaplayın ve umut vadeden komşuları açık kümeye ekleyin.

3

Optimal yolu garanti eden en düşük f-değeriyle hedefe ulaşılana kadar düğümleri genişletmeye devam edin; yol, üst düğüm işaretçilerini izleyerek yeniden oluşturulur.

Sık yapılan hatalar

  • Maliyetleri aşırı tahmin eden, suboptimal yollara yol açan kabul edilemez bir sezgisel fonksiyon kullanmak
  • Probleme çok basit veya ilgisiz bir sezgisel fonksiyon seçmek, arama verimliliğini azaltır
  • Açık kümenin verimsiz uygulanması (öncelik kuyruğu kullanılmalı), yavaş düğüm seçimine neden olur

Sık sorulan sorular

Kabul edilebilir bir sezgisel fonksiyon nedir ve neden önemlidir?

Kabul edilebilir bir sezgisel fonksiyon, hedefe giden gerçek maliyeti asla aşırı tahmin etmez. Bu özellik, A*'nın optimal yolu bulmasını garanti eder. Bir sezgisel fonksiyon aşırı tahmin ederse, A* daha kısa yolları kaçırabilir ve suboptimal çözümler döndürebilir.

Bir problem için iyi bir sezgisel fonksiyon nasıl tasarlanır?

İyi sezgisel fonksiyonlar, alan bilgisine ve problem yapısına dayanır. Izgara tabanlı yol bulma için Manhattan veya Öklid mesafesi iyi çalışır. Daha karmaşık problemler için, kısıtlamaları gevşetmeyi veya kabul edilebilir sezgisel fonksiyonları hesaplamak için desen veritabanlarını kullanmayı düşünün.

A* ile Dijkstra algoritması arasındaki fark nedir?

Her ikisi de optimal yollar bulur, ancak A*, iyi bir sezgisel fonksiyon mevcut olduğunda onu çok daha hızlı hale getiren hedef yönünde keşfi önceliklendirmek için bir sezgisel fonksiyon kullanır. Dijkstra her yönde eşit olarak keşfeder ve sezgisel fonksiyonlar güvenilmez olduğunda daha güvenlidir.

A* en kısa yolu bulmayı garanti edebilir mi?

Evet, sezgisel fonksiyon kabul edilebilir olduğunda (gerçek maliyeti asla aşırı tahmin etmediğinde) A* en kısa yolu garanti eder. Kabul edilemez sezgisel fonksiyonlarla optimallik garanti edilmez.

İlgili yöntemler

Kaynaklar

  1. Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107.

    DOI kaynağını aç
    Kopyalandı.
  2. Russell, S. J., & Norvig, P. (2009). Artificial Intelligence: A Modern Approach (3rd ed.). Pearson.

    ISBN: 978-0-13-604259-4
    Kopyalandı.