اندازه گیری کارایی الگوریتم حل مسئله در هوش مصنوعی AI
اندازه گیری کارایی الگوریتم حل مسئله در هوش مصنوعی AI
قبل از پرداختن به طراحی الگوریتم های جست وجو، باید معیاری را برای انتخاب الگوریتم مناسب در نظر بگیریم. کارایی الگوریتم حل مسئله را میتوان به چهار روش تعیین کرد:
• کامل بودن (Completeness) : آیا الگوریتم تضمین میکند که در صورت وجود جواب ، آنرا پیدا کند.
• بهینگی (Optimality) : آیا این استراتژی جواب بهینه را پیدا میکند؟
• پیچیدگی زمانی (Time complexity) : چقدر طول میکشد تا جواب را پیدا کند؟
• پیچیدگی حافظه یا فضا (Space complexity) : برای جست وجو به چقدر حافظه نیاز دارد؟
در اندازه گیری کارایی الگوریتم حل مسئله در هوش مصنوعی ، پیچیدگی زمانی و حافظه، براساس معیاری از میزان دشوار بودن مسئله بیان میشوند. در علم تئوری کامپیوتر یک معیار متداول، اندازه ی "گراف فضای حالت"، یعنی |E|+|V| است که در آن V مجموعه ای از رئوس (گره های گراف ) و E مجموعه ای از یالها (لینک ها) است. این معیار در صورتی مفید است که ساختمان داده ی گراف به عنوان ورودی برنامه ی جستوجو محسوب شود. در AI (هوش مصنوعی) گراف معمولا بطور ضمنی بوسیله "حالت شروع"، فعالیت ها و مدل گذار نمایش داده میشود و غالبا نامتناهی است. به همین دلیل ، پیچیدگی بر حسب سه کمیت بیان میشود:
b : که ضریب انشعاب یا حداکثر تعداد گره های پسین (successor) یک گره است.
d: عمق مربوط به کم عمق ترین گره هدف است (یعنی تعداد مراحل در امتداد مسیری از ریشه).
m : حداکثر طول هر مسیری در فضای حالت است.
زمان معمولا بر حسب تعداد گره های تولید شده دراثنای جست وجو، و حافظه برحسب حداکثر تعداد گره های ذخیره شده در حافظه، اندازه گیری میشود. اغلب پیچیدگی زمان و حافظه را برای جست وجو در یک درخت توصیف میکنیم. برای گراف، پیچیدگی زمان و حافظه به چگونگی مسیرهای زاید در فضای حالت بستگی دارد.
برای برآورد اثربخشی الگوریت جست وجو میتوان قطعه هزینه ی جست وجو را در نظر گرفت که معمولا به پیچیدگی زمان بستگی دارد ولی میتواند شامل عبارتی برای بهره وری از حافظه باشد، یا میتوان از هزینه ی کل استفاده کرد که ترکیبی از هزینه ی جست وجو و هزینه ی مربوط به جواب پیدا شده است.
