جستجوی عمقی

//جستجوی عمقی

جستجوی عمقی

ابتدا فرزندان ریشه درخت تولید شده و در سطح بعدی درخت قرار می گیرند. در ابتدای کار هریک از کلمات می تواند برای شروع جمله بکار روند. سپس اولوین گره ارای کلمه “عمقی” در سطح 1 از درخت انتخاب شده و همه فزرندان قابل تولید آن در سطح 2 درخت تشکیل می شوند(شکل 2 ). سپس در سطح 2 از درخت گره شامل کلمه “جستجو” انتخاب شده و همه فرزندان آن در سطح 3 درخت تشکیل می شوند(شکل 3 ).  در نهایت نیز کلمه

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

حال فرزندان گره “گراف” در سطح 2 تولید می شوند (شکل 6 ). همانطور که می بینیم فرزند دیگری برای گره “جسجتو” در سطح 3 وجود ندارد. بنابراین این گره نیز به همراه گره پدر از حافظه حذف خواهد شد ( شکل 7 و 8 ). سپس به سطح 1 بازگشته و فرزندان گره “جستجو” را گسترش می دهیم( شکل 9 ). سپس فرزندادن گره “عمقی” در سطح 2 گسترش یافته صحت جمله ساخته شده از آن کلمات بررسی می شوند. در این مرحله جمله از نظر قواعدی درست تشخیص داده شده و عبارت “جستجوی عمقی درخت” به عنوان جواب مسئله پیدا می شود ( شکل 10 ).

در مسئله فوق از دو تابع گسترش و تست هدف برای گسترش دادن فرزندان گره و تعیین صحت جواب مسئله استفاده کردیم. این توابع در مسائل مختلف به روش های گوناگونی پیاده سازی می شوند و الگوریتم کلی برای آن ها وجود ندارد.

۱۳۹۲-۱۲-۵ ۱۰:۳۹:۱۲ +۰۳:۳۰اسفند ۵ام, ۱۳۹۲|عمومی دسته بندی ها|بدون ديدگاه

ثبت ديدگاه

پرداخت

1-پرداخت آنلاین
برای پرداخت آنلاین از لینک زیر استفاده کنید
پرداخت آنلاین
2- پرداخت آفلاین
برای پرداخت آفلاین مبلغ مورد نظر را به یکی از شماره کارت
6037997245888723بانک ملی