زیرساخت الگوریتم های جست وجو در هوش مصنوعی AI

زیرساخت الگوریتم های جست وجو در هوش مصنوعی AI

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

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

زیرساخت الگوریتم های جست وجو

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

•   n.STATE : حالتی در فضای حالت که متناظر با گره n است.

• n.PARENT : گره ای در درخت جست وجو که گره n را تولید کرد.

• n.ACTION : فعالیتی است که در گره والد اجرا شد تا گره n را تولید کند.

• n.PATH-COST : هزینه مسیری از حالت شروع به گره n که توسط اشاره گرهای والد مشخص میشوند. این هزینه بصورت g(n) نمایش داده میشود.

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

تاکنون به تفکیک بین گره ها و حالت ها توجه زیادی نکرده ایم. اما هنگام نوشتن الگوریتم های کامل، تفکیک آنها اهمیت ویژه ای دارد. گره یک ساختمان داده کمکی است که برای نمایش درخت جست وجو بکار میرود. حالت، متناظر با یک پیکربندی از دنیاست. همچنین اگر حالتی توسط دو مسیر جست وجوی مختلف تولید شده باشد، دو گره مختلف میتوانند این حالت را دربرگیرند.

اکنون که با گره ها سروکار داریم، باید جایی باشد که آنها را ذخیره کنیم. مرز باید طوری ذخیره شود که الگوریتم جست وجو به آسانی بتواند گره بعدی را انتخاب کند و آن را بر اساس یک استراتژی دلخواه بسط دهد. ساختمان داده ی مناسب برای این کار ، صف است. عملیات در صف به شرح زیر میباشند:

• EMPTY?(queue)  : اگر هیچ عنصری در صف نباشد و صف خالی باشد مقدار true برمیگرداند.

•POP (queue) : اولین عنصر صف را حذف میکند و آنرا برمیگرداند.

• INSERT(element,queue) : عنصری را در صف قرار میدهد و صف جدید را برمیگرداند.

صف ها، با توجه به ترتیب ذخیره ی گره های درج شده در آنها، مشخص میشوند. سه شکل مختلف صفها، عبارتند از:

1. خروج به ترتیب ورود یا همان صف FIFO ، که عملیات POP در آن قدیمی ترین عنصر موجود در صف را حذف میکند.

2. خروج به ترتیب عکس ورود یا صف LIFO (پشته) و عملیات POP در آن، جدیدترین عنصر موجود در صف را حذف میکند (آخرین عنصری که وارد شده است) .

3. صف اولویت که عمل POP در آن، عنصری را از صف حذف میکند که بالاترین اولویت را دارد.

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