سورس کد پیاده سازی الگوریتم A* در سی شارپ

سورس کد پیاده‌سازی الگوریتم A* در سی‌شارپ: یک راهنمای جامع و کامل

الگوریتم A* (ای-استار) یکی از قدرتمندترین و محبوب‌ترین الگوریتم‌های مسیریابی و جستجو در علوم کامپیوتر و مهندسی نرم‌افزار است. این الگوریتم، با ترکیب بهترین ویژگی‌های جستجوی بهترین مسیر (Best-First Search) و جستجوی در عمق محدود (Depth-First Search)، توانسته است در حل مسائل مختلف، از جمله مسیریابی در نقشه‌ها، رباتیک، بازی‌های رایانه‌ای و سیستم‌های ناوبری، جایگاه ویژه‌ای پیدا کند. حالا بیایید این الگوریتم را به شکل کامل و جامع در زبان برنامه‌نویسی سی‌شارپ بررسی کنیم، و مروری بر نحوه پیاده‌سازی آن داشته باشیم.
مقدمه‌ای بر الگوریتم A*
در ساده‌ترین شکل، الگوریتم A* بر اساس ارزیابی هر گره در مسیر، بهترین مسیر را در میان مسیرهای ممکن انتخاب می‌کند. این ارزیابی توسط یک تابع هزینه (cost function) انجام می‌شود که ترکیبی است از هزینه تاکنون طی شده (g(n)) و تخمین هزینه تا مقصد (h(n)). این تابع، که به عنوان تابع ارزیابی f(n) شناخته می‌شود، به صورت زیر تعریف می‌شود:
\[ f(n) = g(n) + h(n) \]
در اینجا، g(n) هزینه مسیر از شروع تا گره n است، و h(n) تخمین هزینه از نود n تا مقصد است. هدف اصلی، یافتن مسیری است که کم‌ترین هزینه را داشته باشد، و این کار با انتخاب گره‌هایی که کم‌ترین مقدار f(n) را دارند، انجام می‌شود.
ساختار داده‌ها و کدهای پایه
پیاده‌سازی الگوریتم A* در سی‌شارپ نیازمند ساختارهای داده‌ای مناسب است. معمولاً، از لیست‌های باز (Open List) و بسته (Closed List) بهره گرفته می‌شود. لیست باز شامل گره‌هایی است که باید بررسی شوند، و لیست بسته، گره‌هایی است که قبلاً ارزیابی شده‌اند.
برای شروع، باید یک کلاس برای تعریف گره‌ها (Nodes) ایجاد کنیم. این کلاس باید شامل موارد زیر باشد:
- مختصات (X و Y)

- هزینه تاکنون طی شده (g)

- برآورد هزینه تا مقصد (h)

- مقدار f(n)

- اشاره به گره والد (Parent) برای ساخت مسیر نهایی
در ادامه، ساختارهای داده‌ای مورد نیاز، مانند Priority Queue یا لیست مرتب، برای انتخاب سریع‌ترین گره، به کار گرفته می‌شود.
پیاده‌سازی الگوریتم
در کد، روند کار به صورت زیر است:

1. شروع گره به عنوان اولین عضو در لیست باز قرار می‌گیرد.
   
   

1. در حلقه اصلی، گره‌ای با کم‌ترین f(n) از لیست باز انتخاب می‌شود.
   
   

1. اگر این گره همان مقصد باشد، مسیر یافته است و الگوریتم خاتمه می‌یابد.
   
   

1. در غیر این صورت، گره انتخاب شده به لیست بسته منتقل می‌شود.
   
   

1. برای هر همسایه (Neighbor) این گره، هزینه‌های g و h محاسبه می‌شود، و در صورت لزوم، وضعیت آن در لیست‌ها بروزرسانی می‌گردد.
   
   

1. این روند تا زمانی ادامه دارد که مسیر پیدا شود یا لیست باز خالی گردد.
   در اینجا، باید توجه داشت که تابع h باید تخمینی معتبر و قابل اعتماد باشد؛ مثلا، در نقشه‌های مربعی، فاصله هومورفیک (مانند فاصله اقلیدسی یا منهتن) مناسب است.
   کد نمونه در سی‌شارپ
   در ادامه، نمونه‌ای از این پیاده‌سازی آورده شده است:
   

   csharp  
   
   

using System;

using System.Collections.Generic;
public class Node : IComparable<Node>

{

public int X { get; set; }

public int Y { get; set; }

public double G { get; set; } // هزینه تاکنون طی شده

public double H { get; set; } // تخمین هزینه تا مقصد

public double F => G + H; // تابع ارزیابی

public Node Parent { get; set; }
public int CompareTo(Node other)

{

return F.CompareTo(other.F);

}

}
public class AStarPathfinder

{

private int[,] grid; // نقشه یا مسیرهای مسدود و آزاد

private int rows, cols;

private Node startNode, endNode;
public AStarPathfinder(int[,] grid, Node start, Node end)

{

this.grid = grid;

this.rows = grid.GetLength(0);

this.cols = grid.GetLength(1);

this.startNode = start;

this.endNode = end;

}
public List<Node> FindPath()

{

var openList = new SortedSet<Node>();

var closedList = new HashSet<Node>();
startNode.G = 0;

startNode.H = CalculateHeuristic(startNode, endNode);

openList.Add(startNode);
while (openList.Count > 0)

{

var currentNode = GetNodeWithLowestF(openList);

if (currentNode.X == endNode.X && currentNode.Y == endNode.... ← ادامه مطلب در magicfile.ir