الف* الگوریتم جستجو در جاوا

الگوریتم های جستجوی مختلف برای کارهای مختلف طراحی شده اند. امروز قصد داریم در مورد جستجوی A*، یکی از موثرترین الگوریتم های مسیریابی صحبت کنیم. این یکی برای بازی های رایانه ای و ساخت نمودارهای جستجو مانند راه های بین شهرها و غیره بسیار مناسب است. به عنوان مثال، در بازی های ویدئویی استراتژیک یا تاکتیکی، ممکن است متوجه شده باشید که چگونه پس از فشار دادن یک دکمه، بازیکن یا گروه شما بلافاصله بدون معطلی شروع به عبور از زمین به نقطه ای که شما مشخص کرده اید می کند. دقیقاً به این دلیل که بازی‌ها از الگوریتم‌های مؤثری استفاده می‌کنند که دقیقاً محاسبه می‌کنند بازیکن چگونه باید به جایی برسد، تاخیری وجود ندارد. یا دشمنی که بدون تردید بازیکن را پیدا کرده و از دور شروع به راه رفتن در جهت درست می کند. معمولاً برای چنین اقداماتی از الگوریتم A* استفاده می شود.

الگوریتم A* چیست؟

الگوریتم مسیریابی A* نمونه ای از الگوریتم جستجوی بهترین اول است. هدف از الگوریتم A* یافتن مسیری از یک نقطه به نقطه دیگر است. این یکی از الگوریتم های کلاسیک برای جستجوی الگوریتم های نمودار است. بیایید با استفاده از یک مثال بفهمیم که چگونه کار می کند. یک بازی دو بعدی با نمای بالا به پایین را تصور کنید. بیایید منطقه بازی خود را به حرص مربع تقسیم کنیم، به عنوان مثال سلول های 8*8 مانند یک صفحه شطرنج. سلول های ما می توانند یکی از دو نوع باشند، قابل عبور یا غیر قابل عبور (مانع). در هر بازه زمانی یک بازیکن یا دشمنی که به بازیکن نزدیک می شود یک سلول را حرکت می دهد. در بازی‌ها، سلول‌های قابل عبور می‌توانند ماهیت متفاوتی داشته باشند، به عنوان مثال، یک جاده صاف، چمن یا شن، که دشواری حرکت در امتداد آنها را تعیین می‌کند، اما برای سادگی فرض می‌کنیم که تمام سلول‌های قابل عبور به یک شکل عبور می‌کنند. در تصویر زیر سلول های آبی موانع هستند. بیایید یک سلول (یا گره) را به عنوان سلول شروع اختصاص دهیم (کاراکتر در آن است)، و سلول دیگر را به عنوان سلول هدف یا هدف (یکی که دارای پرچم است)، و نحوه عملکرد الگوریتم A* را برای این مورد توضیح دهیم. کاراکتر در سلول (1،1) و هدف در سلول (7،7) است. هر سلول دارای همسایگان افقی، عمودی و مورب است. بستگی به بازی دارد که گره های مورب را محاسبه کنیم یا خیر. به عنوان مثال در بسیاری از بازی‌های نمایش از بالا به پایین مانند Bomberman یا Pacman، شخصیت‌ها فقط می‌توانند به صورت افقی یا عمودی حرکت کنند. در این حالت هر گره، به جز لمس لبه ها، تنها 4 همسایه دارد. اگر در مورد بازی صحبت می کنیم که شخصیت ها می توانند به صورت مورب حرکت کنند، هر گره می تواند تا 8 همسایه داشته باشد. در مرحله اول الگوریتم، سلولی که کاراکتر در آن قرار دارد دو همسایه دارد. به طور دقیق تر، سه، اما یکی از آنها مانع است. واضح است که راه مورب طولانی تر است. اگر ضلع سلول خود را به طور مشروط برابر با یک قرار دهیم، طول قطر این خانه برابر است با جذر دو. این همان چیزی است که قضیه فیثاغورث می گوید. برای رسیدن از سلول A به سلول B ابتدا باید یکی از سلول های مجاور و سپس سلول بعدی و ... را انتخاب کنید. همچنین، در طول مسیر، درک کنید که آیا می توان از سلول اولیه به سلول هدف رسید یا خیر. الگوریتم A* در هر مرحله یکی از سلول های همسایه را مطابق با مقدار تابع F انتخاب می کند. این تابع اندازه گیری می کند که یک سلول کاندید چقدر خوب است که در کوتاه ترین مسیر ما قرار گیرد. این تابع هزینه است و مجموع تابع حرکت G و تابع اکتشافی است.

• هزینه G - فاصله ای از یک گره شروع است.

• هزینه H (ابتکاری) فاصله ای از گره پایانی (هدف) است. این عملکرد می تواند متفاوت باشد، یک توسعه دهنده تصمیم می گیرد که چه چیزی بهتر است. شاید انتخاب H در A* مهم ترین باشد و این همان نکته ای است که هر پیاده سازی خاصی از الگوریتم را کم و بیش موثر می کند. از نظر تئوری می توانید از هر تابعی که می خواهید استفاده کنید.

  در مورد ما، ما موقعیت سلول هدف را می دانیم و برای مثال می توانیم فاصله اقلیدسی هندسی بین سلول هدف و فعلی را محاسبه کنیم. هر چه فاصله کمتر باشد به هدف نزدیکتر می شویم.

• هزینه F = G + H. بنابراین الگوریتم تمام هزینه‌های گره‌های همسایه F را محاسبه می‌کند و یکی از کمترین هزینه‌های F را برای نگاه اول انتخاب می‌کند. وقتی یکی را انتخاب می کنیم، آن را به عنوان بسته علامت گذاری می کنیم و مقادیر همسایه های این گره را محاسبه می کنیم.

همانطور که در بالا ذکر کردیم، اگر کاراکترها بتوانند در 8 جهت روی شبکه ما حرکت کنند، گام مورب طولانی تر از افقی یا عمودی خواهد بود، یعنی گرانتر خواهد بود. اجازه دهید به صورت افقی، عمودی و مورب حرکت کنیم. بیایید برای جلوگیری از اعداد کسری، قیمت "گذر" در امتداد یک سلول را به صورت عمودی و افقی برابر، به عنوان مثال، 10، و به صورت مورب - 14 اختصاص دهیم. به این ترتیب تابع G ما محاسبه خواهد شد.

تابع اکتشافی چگونه می توانیم H را محاسبه کنیم؟

این یک تابع اکتشافی است. نام خود به این معنی است که با تجربه تعیین می شود و می تواند متفاوت باشد. در اینجا آن را برابر با فاصله اقلیدسی بین نقاط (x1, y1) و (x2, y2) می گیریم: در تصویر برای مرحله اول دو گزینه وجود دارد که از نظر هزینه یکسان هستند. اما در مرحله بعد، شخصیت در یکی از گزینه ها به بن بست می رسد. بنابراین، ما به سمت دیگری می رویم. در تکرار بعدی، ما در حال حاضر 4 گزینه داریم. دو مورد از آنها مناسب نیستند، زیرا آنها به عقب هدایت می شوند، و گزینه های دیگر به همان اندازه خوب هستند، اما الگوریتم تصمیم گرفت که بهتر است به صورت مورب به سلول بروید (3،2). علاوه بر این، در هر مرحله، محاسبه تابع F تا زمانی که کاراکتر به سلول هدف برسد، تکرار می شود. البته اگر چنین گذری وجود داشته باشد. رنگ سبز روی تصویر gif مسیر بهینه کاراکتر به پرچم را نشان می دهد.

الف* الگوریتم گام به گام

برای پیاده سازی الگوریتم در جاوا، باید مراحل زیر را انجام دهید 1. ابتدا باید دو لیست برای گره های باز و گره های بسته ایجاد کنید. 2. هر دو لیست را مقداردهی اولیه کنید. در یک لیست بسته، گره شروع به لیست باز اشاره می کند. 3. در حالی که عناصر در لیست باز وجود دارد: 3a. گره min را با کوچکترین F 3b پیدا کنید. min را از لیست باز 3c حذف کنید. همسایگان را حداقل (تا 8، در صورت در نظر گرفتن مورب ها) 3d تعیین کنید. بررسی هر همسایه: الف) اگر همسایه سلول هدف است، جستجو را متوقف کنید ب) اگر نه، G، H را برای آن محاسبه کنید. G = min.G + فاصله بین همسایه و min F = G + H ج) اگر گره با موقعیت همسایه در لیست باز است و F آن کمتر از همسایه است، از آن همسایه صرفنظر کنید. گره با موقعیت همسایه در لیست بسته است و f آن کمتر از همسایه است، از آن همسایه رد شوید. در غیر این صورت، گره را به لیست باز End of inner loop 3e اضافه کنید. افزودن min به لیست بسته پایان حلقه بیرونی بنابراین، در هر تکرار، می‌خواهیم کارهای بعدی را انجام دهیم:

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

A* شبه کد

در اینجا شبه کد مختصری از مسیریابی A* آمده است:

Input: a grid with locked and empty cells, with start and goal cell.
Output: least cost path from start to goal cell.

       Initialisation
openList = {startCell} //list of traversed cells
closedList = {}  //list of already traversed cells
g.startCell = 0 //cost from source cell to a cell
h.startCell = h(startCell, goal) //heuristic
f.startCell = g.startCell + h.StartCell

   while openList is not empty
           do

       //let the currentCell equal the cell with the least f value
       currentCell = Cell on top of openList, with least f


                if currentCell == end return
       remove currentCell from openList
       add currentCell to closedList
       foreach n in child.currentCell
                    if n in closedList
       continue
       cost = g.currentCell + distance(currentCell,n)
       if (n in openList and cost < g.n)
           remove n from closedList
           g.n = cost
           h.n = h(n, goal)
           f.n = g.n + h.n

از شبه کد تا A* پیاده سازی در جاوا

الف* مسیریابی در تحقق جاوا باید چند روش برای ارائه الگوریتم داشته باشد:

• سلول، ساختاری برای نگهداری پارامترهای لازم
• لیست های باز و بسته
• روش محاسبه تابع اکتشافی
• روشی برای ردیابی مسیر از مبدا تا مقصد
• روش‌هایی برای بررسی اینکه آیا سلول داده‌شده مسدود است، آیا قبلاً به آن رسیده است، آیا معتبر است و غیره

package Asterist;

import java.util.PriorityQueue;
import java.util.Stack;

public class AAsterisk {

//Java Program to implement A* Search Algorithm

   //Here we're creating a shortcut for (int, int) pair
   public static class Pair {
       int first;
       int second;
       public Pair(int first, int second){
           this.first = first;
           this.second = second;
       }

       @Override
       public boolean equals(Object obj) {
           return obj instanceof Pair && this.first == ((Pair)obj).first && this.second == ((Pair)obj).second;
       }
   }

   // Creating a shortcut for tuple<int, int, int> type
   public static class Details {
       double value;
       int i;
       int j;

       public Details(double value, int i, int j) {
           this.value = value;
           this.i = i;
           this.j = j;
       }
   }

   // a Cell (node) structure
   public static class Cell {
       public Pair parent;
       // f = g + h, where h is heuristic
       public double f, g, h;
       Cell()
       {
           parent = new Pair(-1, -1);
           f = -1;
           g = -1;
           h = -1;
       }

       public Cell(Pair parent, double f, double g, double h) {
           this.parent = parent;
           this.f = f;
           this.g = g;
           this.h = h;
       }
   }

   // method to check if our cell (row, col) is valid
   boolean isValid(int[][] grid, int rows, int cols,
                   Pair point)
   {
       if (rows > 0 && cols > 0)
           return (point.first >= 0) && (point.first < rows)
                   && (point.second >= 0)
                   && (point.second < cols);

       return false;
   }

   //is the cell blocked?

   boolean isUnBlocked(int[][] grid, int rows, int cols,
                       Pair point)
   {
       return isValid(grid, rows, cols, point)
               && grid[point.first][point.second] == 1;
   }

   //Method to check if destination cell has been already reached
   boolean isDestination(Pair position, Pair dest)
   {
       return position == dest || position.equals(dest);
   }

   // Method to calculate heuristic function
   double calculateHValue(Pair src, Pair dest)
   {
       return Math.sqrt(Math.pow((src.first - dest.first), 2.0) + Math.pow((src.second - dest.second), 2.0));
   }

   // Method for tracking the path from source to destination

   void tracePath(
           Cell[][] cellDetails,
           int cols,
           int rows,
           Pair dest)
   {   //A* Search algorithm path
       System.out.println("The Path:  ");

       Stack<Pair> path = new Stack<>();

       int row = dest.first;
       int col = dest.second;

       Pair nextNode = cellDetails[row][col].parent;
       do {
           path.push(new Pair(row, col));
           nextNode = cellDetails[row][col].parent;
           row = nextNode.first;
           col = nextNode.second;
       } while (cellDetails[row][col].parent != nextNode); // until src


       while (!path.empty()) {
           Pair p = path.peek();
           path.pop();
           System.out.println("-> (" + p.first + "," + p.second + ") ");
       }
   }

// A main method, A* Search algorithm to find the shortest path

   void aStarSearch(int[][] grid,
                    int rows,
                    int cols,
                    Pair src,
                    Pair dest)
   {

       if (!isValid(grid, rows, cols, src)) {
           System.out.println("Source is invalid...");
           return;
       }


       if (!isValid(grid, rows, cols, dest)) {
           System.out.println("Destination is invalid...");
           return;
       }


       if (!isUnBlocked(grid, rows, cols, src)
               || !isUnBlocked(grid, rows, cols, dest)) {
           System.out.println("Source or destination is blocked...");
           return;
       }


       if (isDestination(src, dest)) {
           System.out.println("We're already (t)here...");
           return;
       }


       boolean[][] closedList = new boolean[rows][cols];//our closed list

       Cell[][] cellDetails = new Cell[rows][cols];

       int i, j;
       // Initialising of the starting cell
       i = src.first;
       j = src.second;
       cellDetails[i][j] = new Cell();
       cellDetails[i][j].f = 0.0;
       cellDetails[i][j].g = 0.0;
       cellDetails[i][j].h = 0.0;
       cellDetails[i][j].parent = new Pair( i, j );


  // Creating an open list


       PriorityQueue<Details> openList = new PriorityQueue<>((o1, o2) -> (int) Math.round(o1.value - o2.value));

       // Put the starting cell on the open list,   set f.startCell = 0

       openList.add(new Details(0.0, i, j));

       while (!openList.isEmpty()) {
           Details p = openList.peek();
           // Add to the closed list
           i = p.i; // second element of tuple
           j = p.j; // third element of tuple

           // Remove from the open list
           openList.poll();
           closedList[i][j] = true;

              // Generating all the 8 neighbors of the cell

           for (int addX = -1; addX <= 1; addX++) {
               for (int addY = -1; addY <= 1; addY++) {
                   Pair neighbour = new Pair(i + addX, j + addY);
                   if (isValid(grid, rows, cols, neighbour)) {
                       if(cellDetails[neighbour.first] == null){ cellDetails[neighbour.first] = new Cell[cols]; }
                       if (cellDetails[neighbour.first][neighbour.second] == null) {
                           cellDetails[neighbour.first][neighbour.second] = new Cell();
                       }

                       if (isDestination(neighbour, dest)) {
                           cellDetails[neighbour.first][neighbour.second].parent = new Pair ( i, j );
                           System.out.println("The destination cell is found");
                           tracePath(cellDetails, rows, cols, dest);
                           return;
                       }

                       else if (!closedList[neighbour.first][neighbour.second]
                               && isUnBlocked(grid, rows, cols, neighbour)) {
                           double gNew, hNew, fNew;
                           gNew = cellDetails[i][j].g + 1.0;
                           hNew = calculateHValue(neighbour, dest);
                           fNew = gNew + hNew;

                           if (cellDetails[neighbour.first][neighbour.second].f == -1
                                   || cellDetails[neighbour.first][neighbour.second].f > fNew) {

                               openList.add(new Details(fNew, neighbour.first, neighbour.second));

                               // Update the details of this
                               // cell
                               cellDetails[neighbour.first][neighbour.second].g = gNew;
//heuristic function                               cellDetails[neighbour.first][neighbour.second].h = hNew;
                               cellDetails[neighbour.first][neighbour.second].f = fNew;
                               cellDetails[neighbour.first][neighbour.second].parent = new Pair( i, j );
                           }
                       }
                   }
               }
           }
       }

       System.out.println("Failed to find the Destination Cell");
   }

   // test
   public static void main(String[] args) {


   //0: The cell is blocked
  // 1: The cell is not blocked

       int[][] grid = {
               { 1, 1, 0, 0, 1, 0, 0, 0 },
               { 1, 0, 0, 1, 1, 0, 1, 0 },
               { 1, 1, 0, 1, 0, 0, 1, 0 },
               { 1, 1, 0, 1, 1, 1, 1, 1 },
               { 1, 1, 0, 0, 0, 1, 1, 1 },
               { 0, 1, 1, 1, 0, 1, 1, 0 },
               { 1, 1, 0, 1, 1, 1, 1, 0 },
               { 0, 1, 1, 1, 1, 1, 1, 1 }

       };


       // Start is the left-most upper-most corner
       Pair src = new Pair(0,0);
               //(8, 0);

       // Destination is the right-most bottom-most corner
       Pair dest = new Pair(6, 6);

       AAsterisk app = new AAsterisk();
       app.aStarSearch(grid, grid.length , grid[0].length, src, dest);

   }
}

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

نتیجه

ما نگاهی به الگوریتم جستجوی A* انداختیم، متوجه شدیم که چگونه کار می کند و چرا در عمل بسیار خوب است. ما فقط یک تابع اکتشافی را در نظر گرفته ایم - فاصله اقلیدسی. در واقع، ما می توانیم به عنوان مثال، فاصله منهتن را نیز اعمال کنیم، در نتیجه از نیاز به محاسبه ریشه دوم خلاص شویم. الگوریتم A* در عمل عالی عمل می کند: در بازی های ویدیویی، یافتن کوتاه ترین مسیر برای ناوبرها، ساختن نقشه ها.