آیا یک ستاره حریص است؟

2024 نویسنده: Lynn Donovan | [email protected]. آخرین اصلاح شده: 2023-12-15 23:46

A*(A ستاره ) A* ترکیبی از Dijkstra و حریص . از فاصله گره ریشه به اضافه فاصله اکتشافی تا هدف استفاده می کند. زمانی که گره هدف را پیدا کنیم، الگوریتم پایان می یابد.

همچنین، آیا جستجوی اول greedy best کامل شده است؟

به طور خلاصه، حریص BFS نیست کامل ، نه بهینه ، دارای پیچیدگی زمانی O(bm) و پیچیدگی فضایی است که می تواند چند جمله ای باشد. A* است کامل , بهینه و دارای پیچیدگی زمانی و مکانی O(bm) است. بنابراین، به طور کلی، A* بیشتر از حافظه استفاده می کند حریص BFS. A* زمانی غیر عملی می شود که جستجو کردن فضا بزرگ است

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

علاوه بر این، چرا یک * بهتر از بهترین جستجوی اول است؟

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

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

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