نمودارها در پایتون – تئوری و پیاده سازی

A* چیست؟

بیایید بگوییم که باید از یک پیچ و خم عظیم عبور کنید. این پیچ و خم به قدری بزرگ است که یافتن دستی هدف ساعت ها طول می کشد. علاوه بر این، هنگامی که پیچ و خم را “با پا” به پایان رساندید، قرار است یکی دیگر را به پایان برسانید.

برای اینکه کارها به طور قابل توجهی آسان تر و زمان کمتری انجام شود، ماز را به یک مشکل جستجو خلاصه می کنیم و راه حلی ارائه می دهیم که می تواند برای هر پیچ و خم اضافی که ممکن است با آن روبرو شویم – تا زمانی که از همان قوانین پیروی کند / استفاده شود. ساختار

هر زمان که بخواهیم هر نوع مشکلی را به مشکل جستجو تبدیل کنیم، باید شش چیز را تعریف کنیم:

1. مجموعه ای از همه حالت هایی که ممکن است در نهایت در آنها قرار بگیریم
2. حالت شروع و پایان
3. یک بررسی پایان (روشی برای بررسی اینکه آیا در وضعیت تمام شده هستیم)
4. مجموعه ای از اقدامات ممکن (در این مورد، جهت های مختلف حرکت)
5. یک تابع پیمایش (عملکردی که به ما می‌گوید اگر در مسیر خاصی برویم به کجا می‌رسیم)
6. مجموعه ای از هزینه های جابجایی از حالت به حالت (که با لبه های نمودار مطابقت دارد)

مشکل پیچ و خم را می توان با نگاشت تقاطع ها به گره های مناسب (نقطه های قرمز) حل کرد و جهت های ممکن را می توانیم به لبه های گراف مناسب (خطوط آبی) برویم.

به طور طبیعی، ما حالت های شروع و پایان را به عنوان تقاطع هایی که در آن وارد ماز می شویم، تعریف می کنیم.node الف) و جایی که می خواهیم از ماز خارج شویم (node ب).

اکنون که یک گراف کامل داریم، می‌توانیم الگوریتم‌هایی را برای یافتن مسیر از حالت A به حالت B مورد بحث قرار دهیم. در موارد ساده (مانند این یکی)، که نمودار تولید شده از تعداد کمی گره و یال تشکیل شده است، BFS، DFS و دیکسترا کافی است.

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

جستجوی آگاهانه به این معنی است که الگوریتم برای شروع اطلاعات اضافی دارد. به عنوان مثال، یک الگوریتم مشکل جستجوی ناآگاه، یافتن مسیری از خانه تا محل کار کاملاً کور است.

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

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

این باعث می شود A* برای سیستم های هوشمند مصنوعی بسیار مفید باشد – به ویژه در یادگیری ماشین و توسعه بازی، زیرا این سیستم ها سناریوهای دنیای واقعی را تکرار می کنند.

مفاهیم پایه A*

A* مبتنی است روی استفاده از روش های اکتشافی برای دستیابی به بهینه بودن و کامل بودن، و گونه ای از الگوریتم best-first است.

هنگامی که یک الگوریتم جستجو دارای خاصیت بهینه است، به این معنی است که تضمین می شود بهترین راه حل ممکن را پیدا کند، در مورد ما کوتاه ترین مسیر تا حالت پایان. هنگامی که یک الگوریتم جستجو دارای خاصیت کامل بودن است، به این معنی است که اگر یک راه حل برای یک مسئله معین وجود داشته باشد، الگوریتم تضمین می شود که آن را پیدا کند.

هر بار که A* وارد یک حالت می شود، هزینه را محاسبه می کند. f(n) (n همسایه بودن node)، برای سفر به تمام گره های همسایه، و سپس وارد می شود node با کمترین مقدار f(n).

این مقادیر با فرمول زیر محاسبه می شوند:

$$
\mathcal f(n) = \mathcal g(n) + \mathcal h(n)
$$

g(n) مقدار کوتاه ترین مسیر از ابتدا است node به node n، و h(n) که یک تقریب اکتشافی از nodeارزش

برای اینکه بتوانیم هر مسیری را بازسازی کنیم، باید هر مسیری را مشخص کنیم node با نسبی که بهینه را دارد f(n) ارزش. این همچنین به این معنی است که اگر گره های خاصی را مجدداً مشاهده کنیم، باید بهینه ترین بستگان آنها را نیز به روز کنیم. بیشتر روی که بعدا

کارایی A* بسیار وابسته است روی ارزش اکتشافی h(n)، و بسته به روی نوع مسئله، ممکن است برای یافتن راه حل بهینه نیاز به استفاده از یک تابع اکتشافی متفاوت برای آن داشته باشیم.

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

پذیرش و سازگاری

یک تابع اکتشافی داده شده h(n) است قابل قبول اگر هرگز فاصله واقعی بین آنها را بیش از حد تخمین نزند n و هدف node.

بنابراین، برای هر node n فرمول زیر اعمال می شود:

$$
h(n)\leq h^*(n)
$$

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

یک تابع اکتشافی داده شده h(n) است استوار اگر برآورد همیشه کمتر یا مساوی فاصله تخمینی بین هدف باشد n و هر همسایه معین، به اضافه هزینه تخمینی رسیدن به آن همسایه:

$$
c(n,m)+h(m)\geq h(n)
$$

c(n,m) فاصله بین گره ها n و m. علاوه بر این، اگر h(n) سازگار است، سپس ما مسیر بهینه برای هر کدام را می دانیم node که قبلاً بازرسی شده است. این بدان معنی است که این تابع است بهینه.

قضیه: اگر یک تابع اکتشافی سازگار باشد، آن را نیز قابل قبول است.

اثبات با استقرا کامل

پارامتر القایی N تعداد گره های بین خواهد بود node n و پایان node s روی کوتاه ترین مسیر بین این دو

پایه: N=0

اگر هیچ گره ای بین آن وجود نداشته باشد n و sو چون ما این را می دانیم h(n) سازگار است، معادله زیر معتبر است:

$$
c(n,s)+h(s)\geq h(n)
$$

دانستن h*(n)=c(n,s) و h(s)=0 با خیال راحت می توانیم نتیجه بگیریم که:

$$
h^*(n)\geq h(n)
$$

فرضیه استقرا: N < k

ما فرض می کنیم که قانون داده شده برای هر یک صادق است N < k.

مرحله القاء:

در شرایطی که N = k گره ها روی کوتاه ترین مسیر از n به s، ما جانشین اول را بازرسی می کنیم (node m) از پایان node n. زیرا می دانیم که مسیری از آن وجود دارد m به n، و ما می دانیم که این مسیر شامل k-1 گره ها، معادله زیر معتبر است:

$$
ℎ^*(𝑛) = 𝑐(𝑛، 𝑚) + ℎ^*(𝑚) ≥ 𝑐(
$$

QED

پیاده سازی

این اجرای مستقیم A* است روی یک ساختار نمودار تابع اکتشافی به منظور سادگی و اختصار به صورت 1 برای همه گره ها تعریف می شود.

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

در اینجا الگوریتم A* پیاده سازی شده در پایتون را خواهید یافت:

from collections import deque

class Graph:
    
    
    
    
    
    

    def __init__(self, adjacency_list):
        self.adjacency_list = adjacency_list

    def get_neighbors(self, v):
        return self.adjacency_list(v)

    
    def h(self, n):
        H = {
            'A': 1,
            'B': 1,
            'C': 1,
            'D': 1
        }

        return H(n)

    def a_star_algorithm(self, start_node, stop_node):
        
        
        
        
        open_list = set((start_node))
        closed_list = set(())

        
        
        g = {}

        g(start_node) = 0

        
        parents = {}
        parents(start_node) = start_node

        while len(open_list) > 0:
            n = None

            
            for v in open_list:
                if n == None or g(v) + self.h(v) < g(n) + self.h(n):
                    n = v;

            if n == None:
                print('Path does not exist!')
                return None

            
            
            if n == stop_node:
                reconst_path = ()

                while parents(n) != n:
                    reconst_path.append(n)
                    n = parents(n)

                reconst_path.append(start_node)

                reconst_path.reverse()

                print('Path found: {}'.format(reconst_path))
                return reconst_path

            
            for (m, weight) in self.get_neighbors(n):
                
                
                if m not in open_list and m not in closed_list:
                    open_list.add(m)
                    parents(m) = n
                    g(m) = g(n) + weight

                
                
                
                else:
                    if g(m) > g(n) + weight:
                        g(m) = g(n) + weight
                        parents(m) = n

                        if m in closed_list:
                            closed_list.remove(m)
                            open_list.add(m)

            
            
            open_list.remove(n)
            closed_list.add(n)

        print('Path does not exist!')
        return None

بیایید به یک مثال با نمودار وزنی زیر نگاه کنیم:

ما کد را به این صورت اجرا می کنیم:

adjacency_list = {
    'A': (('B', 1), ('C', 3), ('D', 7)),
    'B': (('D', 5)),
    'C': (('D', 12))
}
graph1 = Graph(adjacency_list)
graph1.a_star_algorithm('A', 'D')

و خروجی به صورت زیر خواهد بود:

Path found: ('A', 'B', 'D')
('A', 'B', 'D')

بنابراین، مسیر بهینه از A به D، با استفاده از A* یافت می شود A->B->D.