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

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

الگوریتم A* یکی از قدرتمندترین و پرکاربردترین الگوریتم‌های مسیریابی و پیدا کردن کم‌هزینه‌ترین مسیر در گراف‌ها و شبکه‌ها است. این الگوریتم، که به عنوان یک الگوریتم هوشمند و هماهنگ شناخته می‌شود، در سیستم‌های مسیریابی، رباتیک، بازی‌های ویدیویی و تصمیم‌گیری‌های هوشمند مورد استفاده قرار می‌گیرد، زیرا توانایی پیدا کردن مسیر بهینه را در محیط‌های پیچیده و بزرگ دارد.
در این مقاله، قصد دارم به طور جامع و کامل به توضیح نحوه پیاده‌سازی الگوریتم A* در زبان سی‌شارپ بپردازم؛ از مفاهیم پایه‌ای گرفته تا ساختارهای داده‌ای مورد نیاز، و در نهایت، نمونه کد کامل و قابل اجرا را ارائه دهم. یعنی، ضمن معرفی مفاهیم و اصول کلی، نمونه عملیاتی و کاربردی که به توسعه‌دهندگان کمک می‌کند، همراه با جزئیات فنی و کدهای نمونه، آموزش داده خواهد شد.
مفاهیم پایه‌ای الگوریتم A*
قبل از شروع به نوشتن کد، باید درک خوبی از اصول و مفاهیم پایه‌ای الگوریتم داشته باشیم. الگوریتم A* بر پایه مفهوم جستجو در گراف‌ها است. فرض کنید دارید نقشه‌ای را دارید که از چندین نقطه و مسیرهای ارتباطی بین آنها تشکیل شده است. هدف، پیدا کردن کوتاه‌ترین مسیر بین نقطه شروع و مقصد است.
این الگوریتم از دو معیار برای ارزیابی مسیرها استفاده می‌کند:
- g(n): هزینه از نقطه شروع تا نود n.

- h(n): برآورد هزینه از نود n تا مقصد، که باید تخمینی باشد و اغلب بر اساس تابع heuristic نوشته می‌شود.
در نتیجه، تابع ارزیابی f(n) = g(n) + h(n) است. مسیرهایی که کم‌ترین مقدار f(n) را دارند، در اولویت قرار می‌گیرند. این روش باعث می‌شود که الگوریتم هم به سمت هدف حرکت کند و هم مسیر کم‌هزینه‌تری پیدا کند.
ساختار داده‌ها و کلاس‌ها در سی‌شارپ
برای پیاده‌سازی این الگوریتم، باید کلاس‌هایی برای نود (Node) و مجموعه‌های مورد نیاز ایجاد کنیم. هر نود باید ویژگی‌هایی مانند:
- مختصات یا شناسه
- هزینه g(n)
- برآورد h(n)
- مقدار ف f(n)
- والد (Parent) برای مسیر نهایی
داشته باشد.
در اینجا، یک کلاس نمونه برای نود آورده شده است:

csharp  
public class Node  
{
public int X { get; set; }
public int Y { get; set; }
public double GCost { get; set; }
public double HCost { get; set; }
public double FCost => GCost + HCost;
public Node Parent { get; set; }
public bool IsWalkable { get; set; }
public Node(int x, int y, bool isWalkable)
{
X = x;
Y = y;
IsWalkable = isWalkable;
GCost = double.MaxValue; // مقدار اولیه  
HCost = 0;
}
}

همچنین، برای مدیریت لیست‌های باز و بسته، از ساختارهای داده‌ای مانند PriorityQueue یا لیست‌های مرتب‌شده استفاده می‌شود. در نسخه‌های جدید سی‌شارپ، می‌توان از PriorityQueue بهره برد، اما در نسخه‌های قدیمی‌تر، باید با روش‌های دیگر این کار انجام شود.
چیدمان نقشه و مسیر
در اکثر موارد، نقشه محیط به صورت یک آرایه دوبعدی تعریف می‌شود، که هر خانه نشان‌دهنده مسیر یا موانع است. فرض کنید:

csharp  
int[,] grid = new int[width, height];

در این آرایه، مقدار 0 نشان‌دهنده مسیر قابل عبور است و مقدار 1 نشان‌دهنده مانع.
محاسبه تابع heuristic
اصلی‌ترین بخش در پیاده‌سازی A*، تابع heuristic است که بر اساس آن، برآورد هزینه تا مقصد انجام می‌شود. یکی از گزینه‌های رایج، استفاده از فاصله اقلیدسی یا منهدسکی است. فرض کنیم از فاصله منهتن استفاده می‌کنیم:

csharp  
public double GetHeuristic(Node a, Node b)
{
return Math.Abs(a.X - b.X) + Math.Abs(a.Y - b.Y);
}

این تابع، سریع است و در اکثر نقشه‌های مربعی، عملکرد خوبی دارد.
پیاده‌سازی الگوریتم A*
در ادامه، ساختار کلی و مراحل اجرای الگوریتم را توضیح می‌دهم:

1. ابتدا، نود شروع را مقداردهی می‌کنیم و هزینه g آن را صفر قرار می‌دهیم. سپس، آن را به لیست باز اضافه می‌کنیم.

1. در حلقه اصلی، نود با کم‌ترین مقدار F را از لیست باز انتخاب می‌کنیم.

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

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

5. همسایگان نود کنونی را بررسی می‌کنیم:
- اگر همسایه مو... ← ادامه مطلب در magicfile.ir