الگوریتم *A ای استار — راهنمای جامع همراه با مثال

مقدمه مقاله الگوریتم *A ای استار

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

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

اگر فرض کنیم هزینه واقعی برای رفتن به گره جانشین n برابر با مقدار g(n) باشد و هزینه تخمینی رسیدن به گره هدف از گره n را با h(n) نشان دهیم، یک تابع ارزیابی به شکل زیر می‌توان تعریف کرد که بر اساس آن می‌توان حالت جانشین را انتخاب کرد.

f(n)=g(n)+ h(n)

این تابع ارزیابی می‌تواند در قالب کمینه سازی یا بیشینه سازی عمل کند. چند نکته باید در فرآیند الگوریتم جستجوی *A مد نظر قرار گیرد:

• اولاً تابع تخمین h(n) باید مقداری کمتر از هزینه واقعی رفتن از گره n به گره هدف را داشته باشد.
• برای یک مسأله می‌توان توابع تخمین متفاوتی را در نظر گرفت ولی به‌صورت تجربی می‌توان گفت تابع که خروجی عددی بزرگ‌تری دارد. نتیجه بهتری خواهد داشت. (منظور از نتیجه بهتر تعداد گره‌‎های تولید شده در فرآیند حل مسأله و سرعت رسیدن به جواب می‌باشد).

بررسی عملکرد الگوریتم *A

برای بررسی عملکرد الگوریتم آ استار در اغلب منابع درسی از نقشه رومانی و فاصله یافتن دو شهر آراد و بخارست استفاده می‌کنند و در این مقاله از مجله پی استور نیز از نقشه رومانی برای این مثال استفاده می‌کنیم.

حال عملکرد این الگوریتم *A را در قالب یک مثال بررسی می‌کنیم. فرض کنید می‌خواهیم در نقشه کشور رومانی کوتاه‌ترین مسیر بین دو شهر آراد به بخارست را با الگوریتم *A به‌دست آوریم.

مقادیر نوشته شده بر روی یال‌ها هزینه واقعی برای جابجایی بین دو شهر و یا به عبارت دیگر در این مسئله فاصله دو شهر است. در جدول زیر فاصله تخمینی هر یک از شهرها تا بخارست آورده شده است. این فاصله بر اساس خط مستقیمی که دو شهر را به هم وصل می‌کنم بدست آمده است.

حال جستجو را از شهر آراد شروع می کنیم.

f(Sibiu)=c(Arad,Sibiu)+h(Sibiu)=140+253=393
f(Timisoara)=c(Arad,Timisoara)+h(Timisoara)=118+329=447
f(Zerind)=c(Arad,Zerind)+h(Zerind)=75+374=449

با توجه به مقدار تابع ارزیابی می‌توان نتیجه گرفت بهترین جانشین Sibiu می‌باشد. پس این گره را بسط می‌دهیم.

f(Arad)=c(Sibiu,Arad)+h(Arad)=280+366=646
f(Fagaras)=c(Sibiu,Fagaras)+h(Fagaras)=239+179=415
f(Oradea)=c(Sibiu,Oradea)+h(Oradea)=291+380=671
f(Rimnicu Vilcea)=c(Sibiu,Rimnicu Vilcea)+ h(Rimnicu Vilcea)=220+192=413

از بین شش گره کاندید برای بسط Rimnicu Vilcea به‌عنوان گره بعدی انتخاب می‌شود.

f(Craiova)=c(Rimnicu Vilcea, Craiova)+h(Craiova)=366+160=526
f(Pitesti)=c(Rimnicu Vilcea, Pitesti)+h(Pitesti)=317+100=417
f(Sibiu)=c(Rimnicu Vilcea,Sibiu)+h(Sibiu)=300+253=553

با توجه به مقادیر تابع ارزیابی برای حالت‌های جانشین از بین هشت گره کاندید Fagaras به‌عنوان گره بعدی انتخاب می‌شود.

f(Sibiu)=c(Fagaras, Sibiu)+h(Sibiu)=338+253=591
f(Bucharest)=c(Fagaras,Bucharest)+h(Bucharest)=450+0=450

در اینجا ما یک مسیر به بخارست را پیدا کردیم که تابع ارزیابی آن برابر با ۴۵۰ است. اما گره Pitesti را داریم که امیدواری آن برای رسیدن به جواب ۴۱۷ است. پس برای رسیدن به مسیر بهتر جستجو را از Pitesti ادامه می‌‎دهیم.

در این مرحله ما یک مسیر دیگر به بخارست پیدا کردیم که هزینه آن برابر با ۴۱۸ است. از بین گره‌های کاندید هیچ گرهی وجود ندارد که تخمینی کمتر از ۴۱۸ داشته باشد، پس این جواب بیانگر بهترین مسیر از آراد به بخارست است.

f(Bucharest)=c(Pitesti,Bucharest)+h(Bucharest)=418+0=418

بررسی معیارهای کارایی در الگوریتم *A

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

جستجوی عمیق کننده تکراری ای استار terative-deepening A* search

در این روش اساس کار مانند جستجوی A* است با این تفاوت که در ابتدا برای تابع ارزیابی گره‌های تولید شده یک محدودیت در نظر می‌گیریم. به‌طور مثال در مسأله جستجوی مسیر آراد به بخارست فرض می‌کنیم گره‌هایی در حافظه می‌توانند مقیم باشند که تابع ارزیابی آن‌ها از عدد ۴۸۰ کمتر باشد. به این شکل به گره‌های که میزان امیدواری بهتر یا احتمال پیدا کردن مسیر کوتاه‌تر را دارند در حافظه حفظ می‌کنیم که به این شکل تعداد گره‌های کمتری در حافظه مقیم می‌شوند.

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

جستجوی اول بهترین بازگشتی (RBFS) Recursive best-first search

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

بدین ترتیب، بهترین برگ موجود در زیر درخت فراموش شده (ذخیره نشده) را به خاطر دارد و می‌تواند بعدها تصمیم بگیرد که آیا ارزش آن را دارد که این زیر درخت دوباره بسط داده شود یا خیر. حال به بررسی این الگوریتم در مثال جستجوی کوتاه‌ترین مسیر از اراد به بخارست می‌پردازیم.

با محاسبه تابع ارزیابی برای شهرهای جانشین arad ، بهترین مقدار sibiu می‌باشد اما مقدار تابع ارزیابی Timisoara برای یادآوری به‌عنوان پشتیبان حفظ می‌شود.

در این مرحله از بین فرزندان sibiu، rimnicu بسط داده می‌شود ولی مقدار fagaras به‌عنوان پشتیبان حفظ می‌گردد. با بسط rimnicu و محاسبه تابع ارزیابی گره‌های جانشین می‌بینید از بین گره‌های مقیم در حافظه fagaras بهترین تابع ارزیابی را دارد، پس زیر شاخه rimnicu از حافظه حذف می‌شود ولی مقدار بهترین فرزند یعنی ۴۱۷ برای Pitesti برای یادآوری ذخیره می‌شود و خواهیم داشت.

با تولید حالت‌های جانشین fagaras و محاسبه تابع ارزیابی برای آن‌ها، از بین گره‌های مقیم در حافظه سراغ rimnicu می‌رویم که می‌دانیم فرزندی با تابع برازندگی ۴۱۷ دارد که با بسط آن خواهیم داشت.

همان گونه که مشاهده می‌کنید fagaras با مقدار تابع ارزیابی بهترین فرزند خود برچسب گذاری و سراغ rimnicu می‌رویم. مسیر منتهی به Bucharest هزینه ۴۱۸ دارد. در ادامه جستجو گرهی که می‌توان را از آن ادامه داد، Timisoara است اما چون تابع برازندگی آن بیشتر ۴۱۸ است جواب بهتری تولید نخواهد کرد.

عمده‌ترین مشکل این روش تولید زیاد گره‌هاست، هرچند عملکرد بهتری از IDA* دارد. همان گونه که در مثال بالا دیدید، ممکن است گره‌های فراموش شده چندین بار بسط داده شوند تا جواب بهینه به‌دست آید.

روش *SMA

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

این الگوریتم همیشه بدترین برگ را از درخت جستجو حذف می‌کند و بدترین برگ، برگی است که تابع ارزیابی بدی داشته باشد. اما قبل از حذف مقدار تابع ارزیابی را به والدش انتصاب می‌دهد تا در صورت نیاز بتوان آن‌را دوباره در حافظه تولید کنیم. این الگوریتم در صورتی کامل است که حداقل یک جواب داشته باشد که در عمقی کمتر از اندازه حافظه باشد.

شبه کد الگوریتم *A

....
A_star_algorithm(graph, start_point, end_point):
    open_list = []  # List of open nodes to be considered
    closed_list = []  # List of closed nodes for which we are sure about the optimal path
    start_node = create_node(start_point)
    goal_node = create_node(end_point)

    open_list.append(start_node)  # Initially, add the start node to the open list

    while open_list is not empty:
        current_node = open_list.pop(0)  # Remove the current node from the open list
        closed_list.append(current_node)  # Add the current node to the closed list

        if current_node == goal_node:
            path = form_path(current_node)  # Optimal path found
            return path

        for neighbor_node in graph.get_neighbors(current_node):
            if neighbor_node in closed_list:
                continue  # This node has already been considered
            new_node = create_new_node(neighbor_node, current_node)
            if new_node not in open_list:
                open_list.append(new_node)  # If the new node is not in the open list, add it
            update_node_info(new_node)  # Update costs and information of the new node

    return error  # If the goal is not reached
...

نتیجه کلی مقاله الگوریتم *A ای استار

الگوریتم A* با ترکیب الگوریتم Dijkstra و Best-First Search، یکی از پرکاربردترین الگوریتم‌های جستجو در مسائل مسیریابی و هوش مصنوعی است. این الگوریتم با توجه به هزینه‌های واقعی و تخمینی، مسیرهای بهینه را با کارایی بالا پیدا می‌کند و در محاسبات بسیاری از حوزه‌های علوم کامپیوتر و مهندسی مورد استفاده قرار می‌گیرد.