logo

A* Yapay Zekada Arama Algoritması

Yapay Zekada A* Arama Algoritmasına Giriş

A* ('A yıldızı' olarak telaffuz edilir), yapay zeka ve bilgisayar bilimlerinde yaygın olarak kullanılan güçlü bir grafik geçişi ve yol bulma algoritmasıdır. Mevcut düğümden hedef düğüme ulaşımın tahmini maliyeti göz önüne alındığında, esas olarak bir grafikteki iki düğüm arasındaki en kısa yolu bulmak için kullanılır. Algoritmanın temel avantajı, Dijkstra algoritması gibi geleneksel arama algoritmalarına kıyasla grafiği daha bilgili bir şekilde keşfederek en uygun yolu sağlama yeteneğidir.

Algoritma A* diğer iki arama algoritmasının avantajlarını birleştirir: Dijkstra algoritması ve Greedy Best-First Search. Dijkstra'nın algoritması gibi, A* da bulunan yolun olabildiğince kısa olmasını sağlar ancak bunu, aramasını Greedy Best-First Search'e benzer bir buluşsal yöntem aracılığıyla yönlendirerek daha verimli bir şekilde yapar. h(n) ile gösterilen bir buluşsal fonksiyon, herhangi bir n düğümünden hedef düğüme ulaşmanın maliyetini tahmin eder.

A*'nın ana fikri her düğümü iki parametreye göre değerlendirmektir:

Java'da dizeler nasıl birleştirilir
    g(n):ilk düğümden n düğümüne ulaşmanın gerçek maliyeti. Düğümün n giden kenarlarının maliyetlerinin toplamını temsil eder.sa(n):N düğümünden hedef düğüm n'ye sezgisel maliyet ('tahmin maliyeti' olarak da bilinir). Bu probleme özgü buluşsal fonksiyonun kabul edilebilir olması gerekir; bu, hedefe ulaşmanın gerçek maliyetini hiçbir zaman fazla tahmin etmediği anlamına gelir. N düğümünün değerlendirme fonksiyonu f(n) = g(n) h(n) olarak tanımlanır.

Algoritma A*, hedefe ulaşmak için tahmini toplam maliyeti en düşük olan düğümleri tercih ederek, f(n)'nin en düşük değerine göre keşfedilecek düğümleri seçer. A* algoritması şu şekilde çalışır:

  1. Bulunan ancak keşfedilmemiş düğümlerin açık bir listesini oluşturun.
  2. Zaten keşfedilmiş düğümleri tutmak için kapalı bir liste oluşturun.
  3. Açık listeye başlangıç ​​değeri g olan bir başlangıç ​​düğümü ekleyin
  4. Açık liste boşalana veya hedef düğüme ulaşana kadar aşağıdaki adımları tekrarlayın:
    1. Açık listede en küçük f değerine sahip düğümü (yani küçük g(n) h(n) olan düğümü) bulun.
    2. Seçilen düğümü açık listeden kapalı listeye taşıyın.
    3. Seçilen düğümün tüm geçerli alt öğelerini oluşturun.
    4. Her ardıl için, g değerini, mevcut düğümün g değeri ile mevcut düğümden ardıl düğüme geçme maliyetinin toplamı olarak hesaplayın. Daha iyi bir yol bulunduğunda izleyicinin g değerini güncelleyin.
    5. Takipçi açık listede değilse hesaplanan g değeriyle ekleyin ve h değerini hesaplayın. Zaten açık listedeyse, yeni yol daha iyiyse g değerini güncelleyin.
    6. Döngüyü tekrarlayın. Algoritma A*, hedef düğüme ulaşıldığında veya açık liste boşaldığında, başlangıç ​​düğümünden hedef düğüme giden yol olmadığını göstererek sona erer. A* arama algoritması, verimli olması ve grafiklerde veya ağlarda en uygun yolları bulabilmesi nedeniyle robot bilimi, video oyunları, ağ yönlendirme ve tasarım sorunları gibi çeşitli alanlarda yaygın olarak kullanılmaktadır.

Ancak uygun ve kabul edilebilir bir buluşsal fonksiyonun seçilmesi, algoritmanın doğru bir şekilde çalışması ve en uygun çözümü sağlaması açısından önemlidir.

Bilgilendirilmiş Arama Algoritmaları

Yapay Zekada A* Arama Algoritmasının Tarihçesi

Dijkstra algoritmasının ve o zamanın diğer arama algoritmalarının bir uzantısı olarak Stanford Araştırma Enstitüsü'nde (şu anda SRI International) Peter Hart, Nils Nilsson ve Bertram Raphael tarafından geliştirildi. A* ilk kez 1968'de yayınlandı ve yapay zeka ve bilgisayar bilimi topluluklarındaki önemi ve etkinliği nedeniyle hızla tanındı. A*: arama algoritmasının tarihindeki en kritik dönüm noktalarına kısa bir genel bakış:

    Erken arama algoritmaları:A*'nın geliştirilmesinden önce, Derinlik Öncelikli Arama (DFS) ve Genişlik Öncelikli Arama (BFS) dahil olmak üzere çeşitli grafik arama algoritmaları mevcuttu. Bu algoritmalar yolların bulunmasına yardımcı olmasına rağmen, optimalliği garanti etmediler veya aramaya rehberlik edecek buluşsal yöntemleri dikkate almadılar.Dijkstra'nın algoritması:1959'da Hollandalı bilgisayar bilimcisi Edsger W. Dijkstra, negatif olmayan kenar ağırlıklarına sahip ağırlıklı bir grafikte en kısa yolu bulan Dijkstra algoritmasını tanıttı. Dijkstra'nın algoritması etkiliydi ancak kapsamlı yapısı nedeniyle daha büyük grafiklerde kullanıldığında sınırlamaları vardı.Bilgilendirilmiş Arama:Bilgiye dayalı arama algoritmaları (aynı zamanda buluşsal arama olarak da bilinir), arama sürecini verimli bir şekilde yönlendirmek için tahmini maliyetler gibi buluşsal bilgileri dahil etmek üzere geliştirilmiştir. Açgözlü En İyi-İlk Arama böyle bir algoritmaydı, ancak en kısa yolu bulma konusunda optimalliği garanti etmiyordu.A* geliştirme:1968'de Peter Hart, Nils Nilsson ve Bertram Raphael, Dijkstra algoritması ile Greedy Best-First Search'ün bir kombinasyonu olarak A* algoritmasını tanıttı. A* mevcut düğümden hedef düğüme olan maliyeti, mevcut düğüme ulaşmanın gerçek maliyetiyle birleştirerek tahmin etmek için buluşsal bir işlev kullandı. Bu, A*'nın grafiği daha bilinçli keşfetmesine, gereksiz yollardan kaçınmasına ve en uygun çözümü garanti etmesine olanak sağladı.Doğruluk ve Mükemmellik:A*'nın yazarları, algoritmanın belirli koşullar altında mükemmel (eğer varsa her zaman bir çözüm bulur) ve optimal (en kısa yolu bulur) olduğunu gösterdi.Geniş çapta benimsenme ve ilerleme:A*, verimliliği nedeniyle yapay zeka ve BT topluluklarında hızla popülerlik kazandı. Araştırmacılar ve geliştiriciler, A* algoritmasını robot bilimi, video oyunları, mühendislik ve ağ yönlendirme dahil olmak üzere çeşitli alanlara genişletip uyguladılar. Yıllar boyunca A* algoritmasının Artımlı A* ve Paralel A* gibi çeşitli varyasyonları ve optimizasyonları önerilmiştir. Bugün, A* arama algoritması hala yapay zeka ve grafik geçişinde temel ve yaygın olarak kullanılan bir algoritmadır. Çeşitli uygulama ve araştırma alanlarında önemli bir rol oynamaya devam etmektedir. Yapay zeka üzerindeki etkisi ve yol bulma ve optimizasyon problemlerine olan katkısı, onu akıllı sistem araştırmalarında temel bir algoritma haline getirmiştir.

A* arama algoritması Yapay Zekada nasıl çalışır?

A* ('A harfi' olarak telaffuz edilir) arama algoritması, yapay zeka ve bilgisayar bilimlerinde popüler ve yaygın olarak kullanılan bir grafik geçiş algoritmasıdır. Ağırlıklı bir grafikte başlangıç ​​düğümünden hedef düğüme en kısa yolu bulmak için kullanılır. A*, aramayı verimli bir şekilde yönlendirmek için buluşsal yöntemler kullanan bilinçli bir arama algoritmasıdır. Arama algoritması A* şu şekilde çalışır:

Algoritma, keşfedilecek düğümleri depolamak için bir öncelik kuyruğuyla başlar. Aynı zamanda iki veri yapısını g(n) başlatır: Başlangıç ​​düğümünden n düğümüne kadar olan en kısa yolun maliyeti ve h(n), düğüm n'den hedef düğüme kadar tahmini maliyet (sezgisel). Bu genellikle makul bir buluşsal yöntemdir, yani bir hedefe ulaşmanın gerçek maliyetini hiçbir zaman olduğundan fazla tahmin etmez. İlk düğümü öncelik kuyruğuna koyun ve g(n) değerini 0'a ayarlayın. Öncelik kuyruğu boş değilse, en düşük f(n) değerine sahip düğümü öncelik kuyruğundan çıkarın. f(n) = g(n) h(n). Silinen düğüm hedef düğüm ise algoritma sonlandırılır ve yol bulunur. Aksi halde düğümü genişletin ve komşularını oluşturun. Her bir komşu düğüm için, mevcut düğümün g değeri ile mevcut düğümden komşu düğüme geçme maliyetinin toplamı olan başlangıç ​​g(n) değerini hesaplayın. Komşu düğüm öncelik sırasına göre değilse veya orijinal g(n) değeri mevcut g değerinden küçükse, g değerini güncelleyin ve üst düğümünü geçerli düğüme ayarlayın. Komşu düğümden f(n) değerini hesaplayın ve bunu öncelik kuyruğuna ekleyin.

Döngü hedef düğümü bulmadan sona ererse grafiğin baştan sona yolu yoktur. A*'nın verimliliğinin anahtarı, herhangi bir düğümün hedefine ulaşmanın kalan maliyetinin tahminini sağlayan h(n) buluşsal fonksiyonunu kullanmasıdır. Algoritma, gerçek g(n) maliyetini h(n) buluşsal maliyetiyle birleştirerek, en kısa yola götürmesi muhtemel düğümlere öncelik vererek gelecek vaat eden yolları etkili bir şekilde araştırır. A* algoritmasının verimliliğinin büyük ölçüde buluşsal fonksiyonun seçimine bağlı olduğunu unutmamak önemlidir. Kabul edilebilir buluşsal yöntemler, algoritmanın her zaman en kısa yolu bulmasını sağlar, ancak daha bilinçli ve doğru buluşsal yöntemler, daha hızlı yakınsamaya ve daha az arama alanına yol açabilir.

Yapay Zekada A* Arama Algoritmasının Avantajları

A* arama algoritması, yapay zeka ve problem çözme senaryolarında çeşitli avantajlar sunar:

build-essential ubuntu nedir
    En uygun çözüm:A*, kabul edilebilir bir buluşsal fonksiyon göz önüne alındığında, ağırlıklı grafikte başlangıç ​​düğümünden hedef düğüme kadar en uygun (en kısa) yolun bulunmasını sağlar. Bu optimallik, en kısa yolu bulmanın önemli olduğu birçok uygulamada belirleyici bir avantajdır.Tamlık:Eğer bir çözüm varsa, grafiğin sonsuz maliyeti olmaması koşuluyla A* onu bulacaktır. Bu tamlık özelliği, A*'nın, eğer varsa bir çözümden yararlanabilmesini sağlar.Yeterlik:Etkin ve kabul edilebilir bir buluşsal fonksiyon kullanıldığında A* etkindir. Buluşsal yöntemler, gelecek vaat eden yollara odaklanarak ve gereksiz keşiflerden kaçınarak aramayı bir hedefe yönlendirir ve A*'yı genişlik öncelikli arama veya derinlik öncelikli arama gibi farkında olmayan arama algoritmalarından daha verimli hale getirir.Çok yönlülük:A*, yön bulma, rota planlama, robot bilimi, oyun geliştirme ve daha fazlasını içeren çeşitli sorunlu alanlara geniş ölçüde uygulanabilir. Anlamlı bir buluşsal yöntem tanımlanabildiği sürece A*, optimum çözümleri verimli bir şekilde bulmak için kullanılabilir.Optimize edilmiş arama:A*, genişleme için küçük f(n) değerine (g(n) ve h(n)) sahip düğümleri seçmek için bir öncelik sırasını korur. Bu, umut verici yolları ilk önce keşfetmesine olanak tanır, bu da arama alanını azaltır ve daha hızlı yakınsamaya yol açar.Bellek verimliliği:Genişlik öncelikli arama gibi diğer bazı arama algoritmalarından farklı olarak A*, öncelik kuyruğunda yalnızca sınırlı sayıda düğüm saklar, bu da onu özellikle büyük grafikler için bellek açısından verimli kılar.Ayarlanabilir Sezgisel Yöntemler:A*'nın performansı, farklı buluşsal işlevler seçilerek ince ayar yapılabilir. Daha eğitimli buluşsal yöntemler daha hızlı yakınsamaya ve daha az genişletilmiş düğümlere yol açabilir.Kapsamlı bir şekilde araştırıldı:A* onlarca yıllık araştırma ve pratik uygulamalara sahip köklü bir algoritmadır. Birçok optimizasyon ve varyasyon geliştirilmiş olup, bu da onu güvenilir ve iyi anlaşılmış bir sorun giderme aracı haline getirmektedir.İnternette arama:A*, algoritmanın ortamdaki değişikliklere veya yeni görünümlere göre yolu sürekli olarak güncellediği web tabanlı yol arama için kullanılabilir. Dinamik senaryolarda gerçek zamanlı karar almayı mümkün kılar.

Yapay Zekada A* Arama Algoritmasının Dezavantajları

A* (A harfi) arama algoritması yapay zeka yol bulma ve grafik geçiş problemlerini çözmek için yaygın olarak kullanılan ve güçlü bir teknik olmasına rağmen dezavantajları ve sınırlamaları vardır. Arama algoritmasının ana dezavantajlarından bazıları şunlardır:

    Sezgisel doğruluk:A* algoritmasının performansı büyük ölçüde mevcut düğümden düğüme olan maliyeti tahmin etmek için kullanılan buluşsal yöntemin doğruluğuna bağlıdır. Buluşsal yöntem kabul edilemezse (asla gerçek maliyeti fazla tahmin etmez) veya tutarsızsa (üçgen eşitsizliğini karşılar), A* En uygun yolu bulamayabilir veya gereğinden fazla düğüm keşfederek verimliliğini ve doğruluğunu etkileyebilir.Hafıza kullanımı:A*, keşfedilen yolları takip etmek için ziyaret edilen tüm düğümlerin bellekte tutulmasını gerektirir. Bellek kullanımı bazen, özellikle de geniş bir arama alanı veya sınırlı bellek kaynaklarıyla uğraşırken önemli bir sorun haline gelebilir.Zaman karmaşıklığı:A* genel olarak verimli olmasına rağmen zaman karmaşıklığı, geniş arama alanları veya grafikler için endişe kaynağı olabilir. En kötü durumda, buluşsal yöntemin sorun için uygun olmaması durumunda A*'nın en uygun yolu bulması katlanarak daha uzun sürebilir.Hedefteki darboğaz:Belirli senaryolarda, A* algoritmasının nihai olarak hedef bölgeye ulaşmadan önce hedeften uzaktaki düğümleri keşfetmesi gerekir. Bu sorun, buluşsal yöntemin aramayı erken ve etkili bir şekilde hedefe yönlendirmesi gerektiğinde ortaya çıkar.Maliyet Bağlayıcı:A*, birden fazla düğüm aynı f değerine (gerçek maliyet ile buluşsal maliyetin toplamı) sahip olduğunda zorluklarla karşılaşır. Kullanılan strateji, keşfedilen yolun optimalliğini ve verimliliğini etkileyebilir. Doğru şekilde yönetilmezse gereksiz düğümlerin keşfedilmesine ve algoritmanın yavaşlamasına neden olabilir.Dinamik ortamlardaki karmaşıklık:Arama sırasında kenarların veya düğümlerin maliyetinin değişebileceği dinamik ortamlarda A* bu tür değişikliklere iyi uyum sağlayamadığı için uygun olmayabilir. Sıfırdan yeniden formülasyon hesaplama açısından pahalı olabilir ve D* (Dinamik A*) algoritmaları bunu çözmek için tasarlanmıştır.Sonsuz uzayda mükemmellik:A* sonsuz durum uzayında bir çözüm bulamayabilir. Bu gibi durumlarda, süresiz olarak çalışabilir ve bir çözüm bulamadan giderek artan sayıda düğümü keşfedebilir. Bu eksikliklere rağmen A* hala sağlam ve yaygın olarak kullanılan bir algoritmadır çünkü buluşsal fonksiyon iyi tasarlanmışsa ve arama alanı yönetilebilirse birçok pratik durumda en uygun yolları etkili bir şekilde bulabilir. Bazı sınırlamalarını hafifletmek için A*'nın çeşitli varyasyonları ve varyantları önerilmiştir.

A* Arama Algoritmasının Yapay Zekadaki Uygulamaları

Arama algoritması A* (A harfi), yapay zeka ve bilgisayar bilimlerinde yaygın olarak kullanılan ve sağlam bir yol bulma algoritmasıdır. Verimliliği ve optimalliği onu çeşitli uygulamalar için uygun kılar. A* arama algoritmasının yapay zekadaki bazı tipik uygulamaları şunlardır:

    Oyunlarda Yol Bulma:A* genellikle video oyunlarında karakter hareketi, düşman yapay zeka navigasyonu ve oyun haritasında bir konumdan diğerine en kısa yolu bulmak için kullanılır. Maliyete ve buluşsal bilgiye dayalı olarak en uygun yolu bulma yeteneği, onu oyunlar gibi gerçek zamanlı uygulamalar için ideal kılar.Robotik ve Otonom Araçlar:A*, robotların bir hedefe ulaşması, engellerden kaçınması ve arazi maliyetlerini dikkate alması için en uygun rotayı planlamak amacıyla robot biliminde ve otonom araç navigasyonunda kullanılır. Bu, doğal ortamlarda verimli ve güvenli hareket için çok önemlidir.Labirent çözümü:A* bir labirentte en kısa yolu verimli bir şekilde bulabilir, bu da onu bulmaca çözme veya karmaşık yapılarda gezinme gibi birçok labirent çözme uygulamasında değerli kılar.Rota planlama ve navigasyon:GPS sistemlerinde ve haritalama uygulamalarında, mesafe, trafik koşulları ve yol ağı topolojisi gibi faktörler dikkate alınarak haritadaki iki nokta arasındaki en uygun rotayı bulmak için A* kullanılabilir.Bulmaca çözümü:A* kayan bulmacalar, Sudoku ve 8 bulmaca problemi gibi çeşitli diyagram bulmacalarını çözebilir. Kaynak Tahsisi: Kaynakların en iyi şekilde tahsis edilmesi gereken senaryolarda A*, en verimli tahsis yolunun bulunmasına yardımcı olarak maliyeti en aza indirir ve verimliliği en üst düzeye çıkarır.Ağ Yönlendirme:A*, bilgisayar ağlarında, veri paketleri için bir kaynaktan hedef düğüme en etkili rotayı bulmak amacıyla kullanılabilir.Doğal Dil İşleme (NLP):Bazı NLP görevlerinde A*, olası kelime dizilerini olasılık ve alaka düzeyine göre arayarak tutarlı ve bağlamsal yanıtlar üretebilir.Robotikte yol planlama:A*, engellerden kaçınmak veya enerji tüketimini en aza indirmek gibi çeşitli kısıtlamaları dikkate alarak bir robotun yolunu bir noktadan diğerine planlamak için kullanılabilir.Oyun Yapay Zekası:A* aynı zamanda oyuncu olmayan karakterler (NPC'ler) için, takım tabanlı bir oyunda bir hedefe ulaşmanın en iyi yolunu belirlemek veya hareketleri koordine etmek gibi akıllı kararlar vermek için de kullanılır.

Bunlar, A* arama algoritmasının yapay zekanın çeşitli alanlarında nasıl uygulama bulduğuna dair yalnızca birkaç örnektir. Esnekliği, verimliliği ve optimizasyonu onu birçok sorun için değerli bir araç haline getiriyor.

Yapay Zekada A* Arama Algoritması için C programı

 #include #include #define ROWS 5 #define COLS 5 // Define a structure for a grid cell typedef struct { int row, col; } Cell; // Define a structure for a node in the A* algorithm typedef struct { Cell position; int g, h, f; struct Node* parent; } Node; // Function to calculate the Manhattan distance between two cells int heuristic(Cell current, Cell goal) { return abs(current.row - goal.row) + abs(current.col - goal.col); } // Function to check if a cell is valid (within the grid and not an obstacle) int isValid(int row, int col, int grid[ROWS][COLS]) { return (row &gt;= 0) &amp;&amp; (row = 0) &amp;&amp; (col <cols) && (grid[row][col]="=" 0); } function to check if a cell is the goal int isgoal(cell cell, goal) { return (cell.row="=" goal.row) (cell.col="=" goal.col); perform a* search algorithm void astarsearch(int grid[rows][cols], start, todo: implement here main() grid[rows][cols]="{" {0, 1, 0, 0}, 0} }; start="{0," 0}; - cols 1}; astarsearch (grid, goal); 0; < pre> <p> <strong>Explanation:</strong> </p> <ol class="points"> <tr><td>Data Structures:</td> A cell structure represents a grid cell with a row and a column. The node structure stores information about a cell during an A* lookup, including its location, cost (g, h, f), and a reference to its parent. </tr><tr><td>Heuristic function (heuristic):</td> This function calculates the Manhattan distance (also known as a &apos;cab ride&apos;) between two cells. It is used as a heuristic to estimate the cost from the current cell to the target cell. The Manhattan distance is the sum of the absolute differences between rows and columns. </tr><tr><td>Validation function (isValid):</td> This function checks if the given cell is valid, i.e., whether it is within the grid boundaries and is not an obstacle (indicated by a grid value of 1). </tr><tr><td>Goal check function (isGoal):</td> This function checks if the given cell is a target cell, i.e., does it match the coordinates of the target cell. </tr><tr><td>Search function* (AStarSearch):</td> This is the main function where the A* search algorithm should be applied. It takes a grid, a source cell, and a target cell as inputs. This activity aims to find the shortest path from the beginning to the end, avoiding the obstacles on the grid. The main function initializes a grid representing the environment, a start, and a target cell. It then calls the AStarSearch function with those inputs. </tr></ol> <p> <strong>Sample Output</strong> </p> <pre> (0, 0) (1, 0) (2, 0) (3, 0) (4, 0) (4, 1) (4, 2) (4, 3) (4, 4) </pre> <h3>C++ program for A* Search Algorithm in Artificial Intelligence</h3> <pre> #include #include #include using namespace std; struct Node { int x, y; // Coordinates of the node int g; // Cost from the start node to this node int h; // Heuristic value (estimated cost from this node to the goal node) Node* parent; // Parent node in the path Node (int x, int y): x(x), y(y), g(0), h(0), parent(nullptr) {} // Calculate the total cost (f = g + h) int f () const { return g + h; } }; // Heuristic function (Euclidean distance) int calculateHeuristic (int x, int y, int goals, int goal) { return static cast (sqrt (pow (goals - x, 2) + pow (goal - y, 2))); } // A* search algorithm vector<pair> AStarSearch (int startX, int startY, int goals, int goal, vector<vector>&amp; grid) { vector<pair> path; int rows = grid. size (); int cols = grid [0].size (); // Create the open and closed lists Priority queue <node*, vector, function> open List([](Node* lhs, Node* rhs) { return lhs-&gt;f() &gt; rhs-&gt;f(); }); vector<vector> closed List (rows, vector (cols, false)); // Push the start node to the open list openList.push(start Node); // Main A* search loop while (! Open-list. Empty ()) { // Get the node with the lowest f value from the open list Node* current = open-list. Top (); openest. pop (); // Check if the current node is the goal node if (current-&gt;x == goals &amp;&amp; current-&gt;y == goal) { // Reconstruct the path while (current! = nullptr) { path. push_back(make_pair(current-&gt;x, current-&gt;y)); current = current-&gt;parent; } Reverse (path. Begin(), path.end ()); break; } // Mark the current node as visited (in the closed list) Closed-list [current-&gt;x] [current-&gt;y] = true; // Generate successors (adjacent nodes) int dx [] = {1, 0, -1, 0}; int dy [] = {0, 1, 0, -1}; for (int i = 0; i x + dx [i]; int new Y = current-&gt;y + dy [i]; } break; } successor-&gt;parent = current; open List.push(successor); } // Cleanup memory for (Node* node: open List) { delete node; } return path; } int main () { int rows, cols; cout &lt;&gt; rows; cout &lt;&gt; cols; vector<vector> grid (rows, vector(cols)); cout &lt;&lt; &apos;Enter the grid (0 for empty, 1 for obstacle):&apos; &lt;&lt; endl; for (int i = 0; i &lt; rows; i++) { for (int j = 0; j&gt; grid[i][j]; } } int startX, startY, goalX, goalY; cout &lt;&gt; startX &gt;&gt; start; cout &lt;&gt; goals &gt;&gt; goals; vector<pair> path = AStarSearch (startX, startY, goal, goal, grid); if (! path. Empty ()) { cout &lt;&lt; &apos;Shortest path from (&apos; &lt;&lt; startX &lt;&lt; &apos;,&apos; &lt;&lt; start &lt;&lt; &apos;) to (&apos; &lt;&lt; goal &lt;&lt; &apos;,&apos; &lt;&lt; goal &lt;&lt; &apos;):&apos; &lt;&lt; endl; for (const auto&amp; point: path) { cout &lt;&lt; &apos;(&apos; &lt;&lt; point. first &lt;&lt; &apos;,&apos; &lt;&lt; point. second &lt;&lt; &apos;) &apos;; } cout &lt;&lt; endl; } else { cout &lt;&lt; &apos;No path found!&apos; &lt;&lt; endl; } return 0; } </pair></vector></vector></node*,></pair></vector></pair></pre> <p> <strong>Explanation:</strong> </p> <ol class="points"> <tr><td>Struct Node:</td> This defines a nodestructure that represents a grid cell. It contains the x and y coordinates of the node, the cost g from the starting node to that node, the heuristic value h (estimated cost from that node to the destination node), and a pointer to the <li>starting node of the path.</li> </tr><tr><td>Calculate heuristic:</td> This function calculates a heuristic using the Euclidean distance between a node and the target AStarSearch: This function runs the A* search algorithm. It takes the start and destination coordinates, a grid, and returns a vector of pairs representing the coordinates of the shortest path from start to finish. </tr><tr><td>Primary:</td> The program&apos;s main function takes input grids, origin, and target coordinates from the user. It then calls AStarSearch to find the shortest path and prints the result. Struct Node: This defines a node structure that represents a grid cell. It contains the x and y coordinates of the node, the cost g from the starting node to that node, the heuristic value h (estimated cost from that node to the destination node), and a pointer to the starting node of the path. </tr><tr><td>Calculate heuristic:</td> This function calculates heuristics using the Euclidean distance between a node and the target AStarSearch: This function runs the A* search algorithm. It takes the start and destination coordinates, a grid, and returns a vector of pairs representing the coordinates of the shortest path from start to finish. </tr></ol> <p> <strong>Sample Output</strong> </p> <pre> Enter the number of rows: 5 Enter the number of columns: 5 Enter the grid (0 for empty, 1 for obstacle): 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 Enter the start coordinates (x y): 0 0 Enter the goal coordinates (x y): 4 4 </pre> <h3>Java program for A* Search Algorithm in Artificial Intelligence</h3> <pre> import java. util.*; class Node { int x, y; // Coordinates of the node int g; // Cost from the start node to the current node int h; // Heuristic value (estimated cost from the current node to goal node) int f; // Total cost f = g + h Node parent; // Parent node in the path public Node (int x, int y) { this. g = x; this. f = y; this. Parent = null; } } public class AStarSearch { // Heuristic function (Manhattan distance) private static int heuristic (Node current, Node goal) { return Math. Abs (current.x - goal.x) + Math. Abs(current.y - goal.y); } // A* search algorithm public static List aStarSearch(int [][] grid, Node start, Node goal) { int rows = grid. Length; int cols = grid [0].length; // Add the start node to the open set opened.add(start); while (! openSet.isEmpty()) { // Get the node with the lowest f value from the open set Node current = openSet.poll(); // If the current node is the goal node, reconstruct the path and return it if (current == goal) { List path = new ArrayList(); while (current != null) { path.add(0, current); current = current.parent; } return path; } // Move the current node from the open set to the closed set closedSet.add(current); // Generate neighbors of the current node int[] dx = {-1, 0, 1, 0}; int[] dy = {0, -1, 0, 1}; for (int i = 0; i = 0 &amp;&amp; nx = 0 &amp;&amp; ny = neighbor.g) { // Skip this neighbor as it is already in the closed set with a lower or equal g value continue; } if (!openSet.contains(neighbor) || tentativeG <neighbor.g) { update the neighbor's values neighbor.g="tentativeG;" neighbor.h="heuristic(neighbor," goal); neighbor.f="neighbor.g" + neighbor.h; neighbor.parent="current;" if (!openset.contains(neighbor)) add neighbor to open set not already present openset.add(neighbor); } is empty and goal reached, there no path return null; public static void main(string[] args) int[][] grid="{" {0, 0, 0}, 1, 0} }; node start="new" node(0, 0); node(4, 4); list start, (path !="null)" system.out.println('path found:'); for (node : path) system.out.println('(' node.x ', ' node.y ')'); else system.out.println('no found.'); < pre> <p> <strong>Explanation:</strong> </p> <ol class="points"> <tr><td>Node Class:</td> We start by defining a nodeclass representing each grid cell. Each node contains coordinates (x, y), an initial node cost (g), a heuristic value (h), a total cost (f = g h), and a reference to the parent node of the path. </tr><tr><td>Heuristicfunction:</td> The heuristic function calculates the Manhattan distance between a node and a destination The Manhattan distance is a heuristic used to estimate the cost from the current node to the destination node. </tr><tr><td>Search algorithm* function:</td> A Star Search is the primary implementation of the search algorithm A*. It takes a 2D grid, a start node, and a destination node as inputs and returns a list of nodes representing the path from the start to the destination node. </tr><tr><td>Priority Queue and Closed Set:</td> The algorithm uses a priority queue (open Set) to track thenodes to be explored. The queue is ordered by total cost f, so the node with the lowest f value is examined The algorithm also uses a set (closed set) to track the explored nodes. </tr><tr><td>The main loop of the algorithm:</td> The main loop of the A* algorithm repeats until there are no more nodes to explore in the open Set. In each iteration, the node f with the lowest total cost is removed from the opener, and its neighbors are created. </tr><tr><td>Creating neighbors:</td> The algorithm creates four neighbors (up, down, left, right) for each node and verifies that each neighbor is valid (within the network boundaries and not as an obstacle). If the neighbor is valid, it calculates the initial value g from the source node to that neighbor and the heuristic value h from that neighbor to the destination The total cost is then calculated as the sum of f, g, and h. </tr><tr><td>Node evaluation:</td> The algorithm checks whether the neighbor is already in the closed set and, if so, whether the initial cost g is greater than or equal to the existing cost of the neighbor If true, the neighbor is omitted. Otherwise, the neighbor values are updated and added to the open Set if it is not already there. </tr><tr><td>Pathreconstruction:</td> When the destination node is reached, the algorithm reconstructs the path from the start node to the destination node following the main links from the destination node back to the start node. The path is returned as a list of nodes </tr></ol> <p> <strong>Sample Output</strong> </p> <pre> Path found: (0, 0) (0, 1) (1, 1) (2, 1) (2, 2) (3, 2) (4, 2) (4, 3) (4, 4) </pre> <h2>A* Search Algorithm Complexity in Artificial Intelligence</h2> <p>The A* (pronounced &apos;A-star&apos;) search algorithm is a popular and widely used graph traversal and path search algorithm in artificial intelligence. Finding the shortest path between two nodes in a graph or grid-based environment is usually common. The algorithm combines Dijkstra&apos;s and greedy best-first search elements to explore the search space while ensuring optimality efficiently. Several factors determine the complexity of the A* search algorithm. Graph size (nodes and edges): A graph&apos;s number of nodes and edges greatly affects the algorithm&apos;s complexity. More nodes and edges mean more possible options to explore, which can increase the execution time of the algorithm.</p> <p>Heuristic function: A* uses a heuristic function (often denoted h(n)) to estimate the cost from the current node to the destination node. The precision of this heuristic greatly affects the efficiency of the A* search. A good heuristic can help guide the search to a goal more quickly, while a bad heuristic can lead to unnecessary searching.</p> <ol class="points"> <tr><td>Data Structures:</td> A* maintains two maindata structures: an open list (priority queue) and a closed list (or visited pool). The efficiency of these data structures, along with the chosen implementation (e.g., priority queue binary heaps), affects the algorithm&apos;s performance. </tr><tr><td>Branch factor:</td> The average number of followers for each node affects the number of nodes expanded during the search. A higher branching factor can lead to more exploration, which increases </tr><tr><td>Optimality and completeness:</td> A* guarantees both optimality (finding the shortest path) and completeness (finding a solution that exists). However, this guarantee comes with a trade-off in terms of computational complexity, as the algorithm must explore different paths for optimal performance. Regarding time complexity, the chosen heuristic function affects A* in the worst case. With an accepted heuristic (which never overestimates the true cost of reaching the goal), A* expands the fewest nodes among the optimization algorithms. The worst-case time complexity of A * is exponential in the worst-case O(b ^ d), where &apos;b&apos; is the effective branching factor (average number of followers per node) and &apos;d&apos; is the optimal </tr></ol> <p>In practice, however, A* often performs significantly better due to the influence of a heuristic function that helps guide the algorithm to promising paths. In the case of a well-designed heuristic, the effective branching factor is much smaller, which leads to a faster approach to the optimal solution.</p> <hr></neighbor.g)></pre></cols)>

Yapay Zekada A* Arama Algoritması için C++ programı

 #include #include #include using namespace std; struct Node { int x, y; // Coordinates of the node int g; // Cost from the start node to this node int h; // Heuristic value (estimated cost from this node to the goal node) Node* parent; // Parent node in the path Node (int x, int y): x(x), y(y), g(0), h(0), parent(nullptr) {} // Calculate the total cost (f = g + h) int f () const { return g + h; } }; // Heuristic function (Euclidean distance) int calculateHeuristic (int x, int y, int goals, int goal) { return static cast (sqrt (pow (goals - x, 2) + pow (goal - y, 2))); } // A* search algorithm vector<pair> AStarSearch (int startX, int startY, int goals, int goal, vector<vector>&amp; grid) { vector<pair> path; int rows = grid. size (); int cols = grid [0].size (); // Create the open and closed lists Priority queue <node*, vector, function> open List([](Node* lhs, Node* rhs) { return lhs-&gt;f() &gt; rhs-&gt;f(); }); vector<vector> closed List (rows, vector (cols, false)); // Push the start node to the open list openList.push(start Node); // Main A* search loop while (! Open-list. Empty ()) { // Get the node with the lowest f value from the open list Node* current = open-list. Top (); openest. pop (); // Check if the current node is the goal node if (current-&gt;x == goals &amp;&amp; current-&gt;y == goal) { // Reconstruct the path while (current! = nullptr) { path. push_back(make_pair(current-&gt;x, current-&gt;y)); current = current-&gt;parent; } Reverse (path. Begin(), path.end ()); break; } // Mark the current node as visited (in the closed list) Closed-list [current-&gt;x] [current-&gt;y] = true; // Generate successors (adjacent nodes) int dx [] = {1, 0, -1, 0}; int dy [] = {0, 1, 0, -1}; for (int i = 0; i x + dx [i]; int new Y = current-&gt;y + dy [i]; } break; } successor-&gt;parent = current; open List.push(successor); } // Cleanup memory for (Node* node: open List) { delete node; } return path; } int main () { int rows, cols; cout &lt;&gt; rows; cout &lt;&gt; cols; vector<vector> grid (rows, vector(cols)); cout &lt;&lt; &apos;Enter the grid (0 for empty, 1 for obstacle):&apos; &lt;&lt; endl; for (int i = 0; i &lt; rows; i++) { for (int j = 0; j&gt; grid[i][j]; } } int startX, startY, goalX, goalY; cout &lt;&gt; startX &gt;&gt; start; cout &lt;&gt; goals &gt;&gt; goals; vector<pair> path = AStarSearch (startX, startY, goal, goal, grid); if (! path. Empty ()) { cout &lt;&lt; &apos;Shortest path from (&apos; &lt;&lt; startX &lt;&lt; &apos;,&apos; &lt;&lt; start &lt;&lt; &apos;) to (&apos; &lt;&lt; goal &lt;&lt; &apos;,&apos; &lt;&lt; goal &lt;&lt; &apos;):&apos; &lt;&lt; endl; for (const auto&amp; point: path) { cout &lt;&lt; &apos;(&apos; &lt;&lt; point. first &lt;&lt; &apos;,&apos; &lt;&lt; point. second &lt;&lt; &apos;) &apos;; } cout &lt;&lt; endl; } else { cout &lt;&lt; &apos;No path found!&apos; &lt;&lt; endl; } return 0; } </pair></vector></vector></node*,></pair></vector></pair>

Açıklama:

    Yapı Düğümü:Bu, bir ızgara hücresini temsil eden bir düğüm yapısını tanımlar. Düğümün x ve y koordinatlarını, başlangıç ​​düğümünden o düğüme olan g maliyetini, h buluşsal değerini (o düğümden hedef düğüme tahmini maliyet) ve düğüme yönelik bir işaretçiyi içerir.
  1. yolun başlangıç ​​düğümü.
  2. Buluşsal yöntemi hesaplayın:Bu işlev, bir düğüm ile hedef AStarSearch arasındaki Öklid mesafesini kullanarak bir buluşsal yöntem hesaplar: Bu işlev, A* arama algoritmasını çalıştırır. Başlangıç ​​ve varış koordinatlarını, bir ızgarayı alır ve baştan sona en kısa yolun koordinatlarını temsil eden çiftlerden oluşan bir vektör döndürür.Öncelik:Programın ana işlevi kullanıcıdan giriş ızgaralarını, başlangıç ​​noktasını ve hedef koordinatlarını alır. Daha sonra en kısa yolu bulmak için AStarSearch'ü çağırır ve sonucu yazdırır. Yapı Düğümü: Bu, bir ızgara hücresini temsil eden bir düğüm yapısını tanımlar. Düğümün x ve y koordinatlarını, başlangıç ​​düğümünden o düğüme olan g maliyetini, h buluşsal değerini (o düğümden hedef düğüme tahmini maliyet) ve yolun başlangıç ​​düğümüne bir işaretçiyi içerir.Buluşsal yöntemi hesaplayın:Bu işlev, bir düğüm ile hedef AStarSearch arasındaki Öklid mesafesini kullanarak buluşsal yöntemi hesaplar: Bu işlev, A* arama algoritmasını çalıştırır. Başlangıç ​​ve varış koordinatlarını, bir ızgarayı alır ve baştan sona en kısa yolun koordinatlarını temsil eden çiftlerden oluşan bir vektör döndürür.

Örnek Çıktı

 Enter the number of rows: 5 Enter the number of columns: 5 Enter the grid (0 for empty, 1 for obstacle): 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 Enter the start coordinates (x y): 0 0 Enter the goal coordinates (x y): 4 4 

Yapay Zekada A* Arama Algoritması için Java programı

 import java. util.*; class Node { int x, y; // Coordinates of the node int g; // Cost from the start node to the current node int h; // Heuristic value (estimated cost from the current node to goal node) int f; // Total cost f = g + h Node parent; // Parent node in the path public Node (int x, int y) { this. g = x; this. f = y; this. Parent = null; } } public class AStarSearch { // Heuristic function (Manhattan distance) private static int heuristic (Node current, Node goal) { return Math. Abs (current.x - goal.x) + Math. Abs(current.y - goal.y); } // A* search algorithm public static List aStarSearch(int [][] grid, Node start, Node goal) { int rows = grid. Length; int cols = grid [0].length; // Add the start node to the open set opened.add(start); while (! openSet.isEmpty()) { // Get the node with the lowest f value from the open set Node current = openSet.poll(); // If the current node is the goal node, reconstruct the path and return it if (current == goal) { List path = new ArrayList(); while (current != null) { path.add(0, current); current = current.parent; } return path; } // Move the current node from the open set to the closed set closedSet.add(current); // Generate neighbors of the current node int[] dx = {-1, 0, 1, 0}; int[] dy = {0, -1, 0, 1}; for (int i = 0; i = 0 &amp;&amp; nx = 0 &amp;&amp; ny = neighbor.g) { // Skip this neighbor as it is already in the closed set with a lower or equal g value continue; } if (!openSet.contains(neighbor) || tentativeG <neighbor.g) { update the neighbor\'s values neighbor.g="tentativeG;" neighbor.h="heuristic(neighbor," goal); neighbor.f="neighbor.g" + neighbor.h; neighbor.parent="current;" if (!openset.contains(neighbor)) add neighbor to open set not already present openset.add(neighbor); } is empty and goal reached, there no path return null; public static void main(string[] args) int[][] grid="{" {0, 0, 0}, 1, 0} }; node start="new" node(0, 0); node(4, 4); list start, (path !="null)" system.out.println(\'path found:\'); for (node : path) system.out.println(\'(\' node.x \', \' node.y \')\'); else system.out.println(\'no found.\'); < pre> <p> <strong>Explanation:</strong> </p> <ol class="points"> <tr><td>Node Class:</td> We start by defining a nodeclass representing each grid cell. Each node contains coordinates (x, y), an initial node cost (g), a heuristic value (h), a total cost (f = g h), and a reference to the parent node of the path. </tr><tr><td>Heuristicfunction:</td> The heuristic function calculates the Manhattan distance between a node and a destination The Manhattan distance is a heuristic used to estimate the cost from the current node to the destination node. </tr><tr><td>Search algorithm* function:</td> A Star Search is the primary implementation of the search algorithm A*. It takes a 2D grid, a start node, and a destination node as inputs and returns a list of nodes representing the path from the start to the destination node. </tr><tr><td>Priority Queue and Closed Set:</td> The algorithm uses a priority queue (open Set) to track thenodes to be explored. The queue is ordered by total cost f, so the node with the lowest f value is examined The algorithm also uses a set (closed set) to track the explored nodes. </tr><tr><td>The main loop of the algorithm:</td> The main loop of the A* algorithm repeats until there are no more nodes to explore in the open Set. In each iteration, the node f with the lowest total cost is removed from the opener, and its neighbors are created. </tr><tr><td>Creating neighbors:</td> The algorithm creates four neighbors (up, down, left, right) for each node and verifies that each neighbor is valid (within the network boundaries and not as an obstacle). If the neighbor is valid, it calculates the initial value g from the source node to that neighbor and the heuristic value h from that neighbor to the destination The total cost is then calculated as the sum of f, g, and h. </tr><tr><td>Node evaluation:</td> The algorithm checks whether the neighbor is already in the closed set and, if so, whether the initial cost g is greater than or equal to the existing cost of the neighbor If true, the neighbor is omitted. Otherwise, the neighbor values are updated and added to the open Set if it is not already there. </tr><tr><td>Pathreconstruction:</td> When the destination node is reached, the algorithm reconstructs the path from the start node to the destination node following the main links from the destination node back to the start node. The path is returned as a list of nodes </tr></ol> <p> <strong>Sample Output</strong> </p> <pre> Path found: (0, 0) (0, 1) (1, 1) (2, 1) (2, 2) (3, 2) (4, 2) (4, 3) (4, 4) </pre> <h2>A* Search Algorithm Complexity in Artificial Intelligence</h2> <p>The A* (pronounced &apos;A-star&apos;) search algorithm is a popular and widely used graph traversal and path search algorithm in artificial intelligence. Finding the shortest path between two nodes in a graph or grid-based environment is usually common. The algorithm combines Dijkstra&apos;s and greedy best-first search elements to explore the search space while ensuring optimality efficiently. Several factors determine the complexity of the A* search algorithm. Graph size (nodes and edges): A graph&apos;s number of nodes and edges greatly affects the algorithm&apos;s complexity. More nodes and edges mean more possible options to explore, which can increase the execution time of the algorithm.</p> <p>Heuristic function: A* uses a heuristic function (often denoted h(n)) to estimate the cost from the current node to the destination node. The precision of this heuristic greatly affects the efficiency of the A* search. A good heuristic can help guide the search to a goal more quickly, while a bad heuristic can lead to unnecessary searching.</p> <ol class="points"> <tr><td>Data Structures:</td> A* maintains two maindata structures: an open list (priority queue) and a closed list (or visited pool). The efficiency of these data structures, along with the chosen implementation (e.g., priority queue binary heaps), affects the algorithm&apos;s performance. </tr><tr><td>Branch factor:</td> The average number of followers for each node affects the number of nodes expanded during the search. A higher branching factor can lead to more exploration, which increases </tr><tr><td>Optimality and completeness:</td> A* guarantees both optimality (finding the shortest path) and completeness (finding a solution that exists). However, this guarantee comes with a trade-off in terms of computational complexity, as the algorithm must explore different paths for optimal performance. Regarding time complexity, the chosen heuristic function affects A* in the worst case. With an accepted heuristic (which never overestimates the true cost of reaching the goal), A* expands the fewest nodes among the optimization algorithms. The worst-case time complexity of A * is exponential in the worst-case O(b ^ d), where &apos;b&apos; is the effective branching factor (average number of followers per node) and &apos;d&apos; is the optimal </tr></ol> <p>In practice, however, A* often performs significantly better due to the influence of a heuristic function that helps guide the algorithm to promising paths. In the case of a well-designed heuristic, the effective branching factor is much smaller, which leads to a faster approach to the optimal solution.</p> <hr></neighbor.g)>

A* Yapay Zekada Arama Algoritmasının Karmaşıklığı

A* ('A-yıldızı' olarak telaffuz edilir) arama algoritması, yapay zekada popüler ve yaygın olarak kullanılan bir grafik geçişi ve yol arama algoritmasıdır. Bir grafik veya ızgara tabanlı ortamda iki düğüm arasındaki en kısa yolu bulmak genellikle yaygındır. Algoritma, Dijkstra'nın ve açgözlü en iyi ilk arama öğelerini birleştirerek arama alanını keşfederken optimumluğu verimli bir şekilde sağlar. A* arama algoritmasının karmaşıklığını çeşitli faktörler belirler. Grafik boyutu (düğümler ve kenarlar): Bir grafiğin düğüm ve kenar sayısı, algoritmanın karmaşıklığını büyük ölçüde etkiler. Daha fazla düğüm ve kenar, keşfedilecek daha fazla olası seçenek anlamına gelir ve bu da algoritmanın yürütme süresini artırabilir.

Buluşsal fonksiyon: A*, mevcut düğümden hedef düğüme olan maliyeti tahmin etmek için bir buluşsal fonksiyon (genellikle h(n) ile gösterilir) kullanır. Bu buluşsal yöntemin kesinliği, A* aramasının verimliliğini büyük ölçüde etkiler. İyi bir buluşsal yöntem, aramayı bir hedefe daha hızlı yönlendirmeye yardımcı olabilirken, kötü bir buluşsal yöntem gereksiz aramaya yol açabilir.

    Veri Yapıları:A* iki ana veri yapısını korur: açık liste (öncelik sırası) ve kapalı liste (veya ziyaret edilen havuz). Bu veri yapılarının verimliliği, seçilen uygulamayla (örneğin, öncelik kuyruğu ikili yığınları) birlikte, algoritmanın performansını etkiler.Şube faktörü:Her düğüm için ortalama takipçi sayısı, arama sırasında genişletilen düğüm sayısını etkiler. Daha yüksek bir dallanma faktörü daha fazla araştırmaya yol açabilir, bu daOptimumluk ve bütünlük:A* hem optimalliği (en kısa yolu bulma) hem de bütünlüğü (var olan bir çözümü bulma) garanti eder. Bununla birlikte, algoritmanın optimum performans için farklı yollar keşfetmesi gerektiğinden, bu garanti, hesaplama karmaşıklığı açısından bir ödünleşimi de beraberinde getirir. Zaman karmaşıklığıyla ilgili olarak, seçilen sezgisel fonksiyon en kötü durumda A*'yı etkiler. A*, kabul edilen bir buluşsal yöntemle (hedefe ulaşmanın gerçek maliyetini asla fazla tahmin etmez), optimizasyon algoritmaları arasında en az sayıda düğümü genişletir. A*'nın en kötü durum zaman karmaşıklığı, en kötü durum O(b ^ d)'de üsteldir; burada 'b' etkin dallanma faktörüdür (düğüm başına ortalama takipçi sayısı) ve 'd' optimaldir

Ancak pratikte A*, algoritmayı gelecek vaat eden yollara yönlendirmeye yardımcı olan buluşsal fonksiyonun etkisinden dolayı sıklıkla önemli ölçüde daha iyi performans gösterir. İyi tasarlanmış bir buluşsal yöntem durumunda etkili dallanma faktörü çok daha küçüktür ve bu da optimal çözüme daha hızlı yaklaşmayı sağlar.