جست و جوی هیوریستیک چیست؟

جست و جوی هیوریستیک چیست؟ جست و جوی ابتکاری، روشی است که در حل مسائل، نسبت به روش‌های کلاسیک سریع‌تر عمل می‌کند. جست و جوی کاشف یا ابتکاری، هنگامی که روش‌های کلاسیک در ارائه پاسخ مساله ناتوان هستند، یک راهکار تخمینی برای مساله می‌یابد. این روش، نوعی میانبر برای حل مسائل است، زیرا کاربران معمولا در تلاش برای ایجاد موازنه‌ای میان سرعت و «بهینگی» (Optimality)، «کامل بودن» (Completeness)، «صحت» (Accuracy) یا «دقت» (Precision) هستند. یک هیوریستیک (یا تابع هیوریستیک)، شباهتی به الگوریتم‌های جست و جو دارد. در هر گام «انشعاب» (Branching)، اطلاعات موجود را ارزیابی می‌کند و تصمیمی بر اساس اینکه کدام شاخه را دنبال می‌کند می‌گیرد. الگوریتم این کار را با رتبه‌بندی جایگزین‌ها انجام می‌دهد. هیوریستیک، معمولا در انواع مسائل موثر است، اما الزاما در همه مسائل کار نمی‌کند. چرا به هیوریستیک نیاز است؟ یکی از دلایل نیاز به روش هیوریستیک، ارائه راهکاری در زمان منطقی است که برای مساله مطرح به اندازه کافی خوب باشد. نیازی نیست که خروجی این روش بهترین باشد، زیرا به دلیل داشتن سرعت کافی، بیشتر یک راهکار تخمینی محسوب می‌شود. اغلب مسائلی که از هیوریستیک در آن‌ها استفاده می‌شود، «نمایی» (Exponential) هستند. جست و جوی هیوریستیک امکان کاهش این میزان را به یک عدد چند جمله‌ای می‌دهد. از روش‌های جست و جوی هیوریستیک به این دلیل در هوش مصنوعی استفاده می‌شود که می‌توان از آن‌ها در شرایط‌های گوناگونی بهره برد که امکان استفاده از الگوریتم‌های شناخته شده دیگر وجود ندارد. می‌توان گفت که روش‌های هیوریستیک، روش‌هایی ضعیف محسوب می‌شوند، زیرا نسبت به «انفجار ترکیبی» (Combinatorial Explosion) آسیب‌پذیر هستند. انفجار ترکیبیاتی روش‌های جست و جوی هیوریستیک در هوش مصنوعی به طور کلی، می‌توان روش‌های جست و جوی هیوریستیک را در دو دسته روش‌های «ضعیف» (Weak Techniques) و «مستقیم» (Direct Techniques) قرار داد. در ادامه به هر یک از این موارد پرداخته خواهد شد. روش‌های جست و جوی هیوریستیک مستقیم «جست و جوی ناآگاهانه» یا «جست و جوی کور»‌ (Blind Search)، «جست و جوی غیر مطلع» (Uninformed Search) و «استراتژی کنترل ناآگاهانه» (Blind Control Strategy) نام‌های دیگری هستند که برای روش‌های جست و جوی هیوریستیک مستقیم مورد استفاده قرار می‌گیرند. بهره‌گیری از این روش‌ها همیشه امکان‌پذیر نیست، زیرا نیاز به حافظه یا زمان بیشتری دارند. روش‌های جست و جوی ناآگاهانه، کل «فضای حالت» (State Space) را به دنبال یک راهکار، جست و جو و از یک ترتیب دلخواه از عملیات استفاده می‌کنند. مثالی از این الگوریتم‌ها، «جست و جوی اول سطح» (Breadth First Search | BFS) و «جست و جوی اول عمق» (Depth First Search | DFS) هستند. جست و جوی اول عمق روش‌های جست و جوی هیوریستیک ضعیف «جست و جوی آگاهانه» یا «جست و جوی مطلع» (Informed Search)، «جست و جوی ابتکاری» یا «جست و جوی هیوریستیک» (Heuristic Search) و «استراتژی کنترل هیوریستیک» (Heuristic Control Strategy) اسامی دیگری هستند که برای روش‌های «جست و جوی ضعیف» (Weak Heuristic Search) مورد استفاده قرار می‌گیرند. این روش‌ها، در صورتی که روی نوع صحیحی از مسائل اعمال شوند موثر واقع می‌شوند و معمولا نیاز به نوع خاصی از اطلاعات ویژه دامنه دارند. به این اطلاعات مازاد برای محاسبه کارایی در میان گره‌های فرزند به منظور اکتشاف و بسط دادن آن‌ها نیاز است. هر گره دارای یک تابع هیوریسیتک اختصاص یافته به آن است. مثال‌هایی از این نوع جست و جو عبارتند از «جست و جوی اول بهترین» (BFS | ) و *A. پیش از آنکه روش‌های خاصی تشریح شوند، در ادامه، لیستی از محبوب‌ترین روش‌های جست و جوی هیوریستیک ضعیف آورده شده و سپس، برخی از مهم‌ترین آن‌ها تشریح شده‌اند. جست و جوی اول بهترین جست و جوی *A جست و جوی دوجهته (Bidirectional Search) جست و جوی ممنوعه (Tabu Search) تپه نوردی مسائل ارضای محدودیت الگوریتم تپه‌نوردی در هوش مصنوعی در ادامه، الگوریتم تپه نوردی در هوش مصنوعی مورد بررسی قرار می‌گیرد. این الگوریتم، یک روش هیوریستیک برای مسائل بهینه‌سازی ریاضیاتی است. در الگوریتم تپه نوردی، نیاز به انتخاب یک مقدار از ورودی برای بیشینه یا کمینه کردن تابع واقعی است. این مساله در صورتی که راهکار بیشینه بهینه سراسری نباشد، مناسب محسوب می‌شود. یک مثال شناخته شده برای این نوع الگوریتم، مساله «فروشنده دوره گرد» (Travelling Salesman Problem) است. در این مساله، باید فاصله‌ای که فروشنده می‌پیماید را به حداقل رساند.