اثبات کامل بودن A*

چون A* به منظور افزایش f گره­ ها را بسط می دهد، سرانجام باید به یک حالت هدف برسد. البته درست است، مگر اینکه گره های نامحدود زیادی با f(n) وجود داشته باشند. تنها راهی که ممکن است گره های نامحدود وجود داشته باشند :

الف – گره ای با فاکتور انشعاب نامحدود وجود دارد

ب – مسیری با هزینه مسیر متناهی اما تعداد زیادی گره های نامحدود در طول مسیر وجود داشته دارد.

از این رو، عبارت صحیح این است که A* روی گراف های متناهی محلی (گراف هایی با فاکتور انشعاب محدود : Locally Finite Graphs) کامل است، مشروط بر اینکه مقدار ثابت مثبت ¶ وجود داشته باشد که هر عملگر حداقل هزینه ای برابر با ¶ داشته باشد.

پیچیدگی A*

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

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

A* به دلیل ذخیره ی تمام گره های تولید شده، معمولا قبل از اینکه دچار کمبود زمان شود، دچار کمبود فضا می شود.

نوشته شده توسط حسین | موضوع: سیستم های جستجو | لینک ثابت | | | |