الگوریتم جستجوی عرضی Breadth First Search — راهنمای جامع همراه با مثال

در این بخش از آموزش های درس هوش مصنوعی به الگوریتم جستجوی عرضی Breadth first search یا همان الگوریتم BFS می رسیم. در این آموزش الگوریتم جستجوی عرضی را همراه با مثال و چگونگی پیمایش آموزش خواهیم داد. این الگوریتم که به اختصار BFS نامیده می شود، جزو الگوریتم های معروف هوش مصنوعی برای جستجو است. در ادامه با ما همراه باشید تا این الگوریتم را با یکدیگر بررسی کنیم.

مقدمه

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

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

روش جستجوی اول سطح

جستجوی عرضی همواره جوابی با کمترین تعداد کنش ها را پیدا می کند، زیرا وقتی گره ها را در عمق d ایجاد می کند، تمام گره ها در عمق d-1 را قبلا تولید کرده است. پیچیدگی زمانی و فضا در این الگوریتم بطور نمایی است. بطور مثال مسئله ای را با ضریب انشعاب b=10 سرعت پردازش یک میلیون گره در ثانیه، حافظه مورد نیاز یک کیلو بایت برای هر گره را با جستجوی عمق در نظر بگیرید.

جستجوی عمق d=10 کمتر از 3 ساعت طول می کشد ولی به 10 ترابایت حافظه نیاز دارد، نیازمندی حافظه نسبت به زمان اجزا در الگوریتم های عرضی، مشکل جدی تر است. اما زمان هنوز فاکتور مهمی است. در عمق d=14 حتی با حافظه نامتناهی، جستجو 3.5 سال طول می کشد. به طور کلی مسئله جستجو با پیچیدگی نمایی، نمی تواند با الگوریتم ناآگاهانه حل شود مگر این که نمونه مسئله بسیار کوچک باشد.

جستجوی عرضی در درخت

برای درک بهتر الگوریتم، از این روش جستجو در درخت جستجویی به شکل زیر استفاده می کنیم. فرض کنید فضای جستجوی یک مسئله بصورت درخت زیر است.

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

بررسی کارایی الگوریتم جستجوی عرضی

در ادامه آموزش الگوریتم جستجوی عرضی به بررسی کارایی این الگوریتم می رسیم. کارایی این الگوریتم را با چهار معیار کامل بودن، بهینه بودن، پیچیدگی زمان و پیچیدگی فضا مورد ارزیابی و بررسی قرار می دهیم.

• کامل بودن: بله، این الگوریتم کامل است.
• بهینه بودن: بله (مشروط) در صورتی بهینه است که هزینه مسیر، تابعی غیر نزولی از عمق گره باشد.(مثل وقتی که فعالیتها هزینه یکسانی دارند)
• پیچیدگی زمان: پیچیدگی زمان در این روش بصورت نمایی است.
• پیچیدگی فضا: پیچیدگی فضا در این روش بصورت خطی است.

در پایان ذکر دوباره این نکته ضروری است که به طور کلی مسئله جستجو با پیچیدگی نمایی، نمی تواند با الگوریتم ناآگاهانه حل شود مگر این که نمونه مسئله بسیار کوچک باشد.