Y@SiN
01-25-2010, 02:04 PM
جستجوی عمقی
از اسم این روش جستجو پیداست که پیمایش گراف فضای جستجو با حرکت در عمق انجام می پذیرد. به عنوان مثال فرض کنید با سه کلمه "جستجو" ، "گراف" و "عمقی" می خواهیم یک جمله معنی دار بسازیم. شکل زیر مراحل مختلف تشکیل گراف هنگام جستجوی عمقی گراف را نشان می دهد :
http://pnu-club.com/imported/mising.jpg
الگوریتم جستجو چنین است : ابتدا فرزندان ریشه درخت تولید شده و در سطح بعدی درخت قرار می گیرند. در ابتدای کار هریک از کلمات می تواند برای شروع جمله بکار روند. سپس اولین گره دارای کلمه "عمقی" در سطح 1 از درخت انتخاب شده و همه فزرندان قابل تولید آن در سطح 2 درخت تشکیل می شوند(شکل 2 ). سپس در سطح 2 از درخت گره شامل کلمه "جستجو" انتخاب شده و همه فرزندان آن در سطح 3 درخت تشکیل می شوند(شکل 3 ). در نهایت نیز کلمه "گراف" انتخاب شده ور همه فزرندان آن تولید می شوند. با توجه به اینکه دیگر هیچ فزرندی برای این گره وجود ندارد، بنابراین جمله "عمقی جستجوی گراف" که از پیمایش درخت از ریشه تا گره فعلی به دست می آید بررسی می شود تا صیحیح بودن این جمله را تعیین کند. همانطور که می دانیم این جمله از نظر قواعدی جمله صحیحی نمی باشد. بنابراین گره فعلی از حافظه حذف شده ( شکل 4 ) و گره "جستجو" در سطح 2 بررسی می شود تا اگر فزرند دیگری برای این گره وجود داشته باشد، ادامه جستجو از آن فرزند ادامه یابد. اما فرزند دیگری برای این گره وجود ندارد. از اینرو این گره نیز از حافظه حذف می شود ( شکل 5 )
حال فرزندان گره "گراف" در سطح 2 تولید می شوند (شکل 6 ). همانطور که می بینیم فرزند دیگری برای گره "جسجتو" در سطح 3 وجود ندارد. بنابراین این گره نیز به همراه گره پدر از حافظه حذف خواهد شد ( شکل 7 و 8 ). سپس به سطح 1 بازگشته و فرزندان گره "جستجو" را گسترش می دهیم( شکل 9 ). سپس فرزندادن گره "عمقی" در سطح 2 گسترش یافته صحت جمله ساخته شده از آن کلمات بررسی می شوند. در این مرحله جمله از نظر قواعدی درست تشخیص داده شده و عبارت "جستجوی عمقی درخت" به عنوان جواب مسئله پیدا می شود ( شکل 10 ).
در مسئله فوق از دو تابع گسترش و تست هدف برای گسترش دادن فرزندان گره و تعیین صحت جواب مسئله استفاده کردیم. این توابع در مسائل مختلف به روش های گوناگونی پیاده سازی می شوند و الگوریتم کلی برای آن ها وجود ندارد.
از اسم این روش جستجو پیداست که پیمایش گراف فضای جستجو با حرکت در عمق انجام می پذیرد. به عنوان مثال فرض کنید با سه کلمه "جستجو" ، "گراف" و "عمقی" می خواهیم یک جمله معنی دار بسازیم. شکل زیر مراحل مختلف تشکیل گراف هنگام جستجوی عمقی گراف را نشان می دهد :
http://pnu-club.com/imported/mising.jpg
الگوریتم جستجو چنین است : ابتدا فرزندان ریشه درخت تولید شده و در سطح بعدی درخت قرار می گیرند. در ابتدای کار هریک از کلمات می تواند برای شروع جمله بکار روند. سپس اولین گره دارای کلمه "عمقی" در سطح 1 از درخت انتخاب شده و همه فزرندان قابل تولید آن در سطح 2 درخت تشکیل می شوند(شکل 2 ). سپس در سطح 2 از درخت گره شامل کلمه "جستجو" انتخاب شده و همه فرزندان آن در سطح 3 درخت تشکیل می شوند(شکل 3 ). در نهایت نیز کلمه "گراف" انتخاب شده ور همه فزرندان آن تولید می شوند. با توجه به اینکه دیگر هیچ فزرندی برای این گره وجود ندارد، بنابراین جمله "عمقی جستجوی گراف" که از پیمایش درخت از ریشه تا گره فعلی به دست می آید بررسی می شود تا صیحیح بودن این جمله را تعیین کند. همانطور که می دانیم این جمله از نظر قواعدی جمله صحیحی نمی باشد. بنابراین گره فعلی از حافظه حذف شده ( شکل 4 ) و گره "جستجو" در سطح 2 بررسی می شود تا اگر فزرند دیگری برای این گره وجود داشته باشد، ادامه جستجو از آن فرزند ادامه یابد. اما فرزند دیگری برای این گره وجود ندارد. از اینرو این گره نیز از حافظه حذف می شود ( شکل 5 )
حال فرزندان گره "گراف" در سطح 2 تولید می شوند (شکل 6 ). همانطور که می بینیم فرزند دیگری برای گره "جسجتو" در سطح 3 وجود ندارد. بنابراین این گره نیز به همراه گره پدر از حافظه حذف خواهد شد ( شکل 7 و 8 ). سپس به سطح 1 بازگشته و فرزندان گره "جستجو" را گسترش می دهیم( شکل 9 ). سپس فرزندادن گره "عمقی" در سطح 2 گسترش یافته صحت جمله ساخته شده از آن کلمات بررسی می شوند. در این مرحله جمله از نظر قواعدی درست تشخیص داده شده و عبارت "جستجوی عمقی درخت" به عنوان جواب مسئله پیدا می شود ( شکل 10 ).
در مسئله فوق از دو تابع گسترش و تست هدف برای گسترش دادن فرزندان گره و تعیین صحت جواب مسئله استفاده کردیم. این توابع در مسائل مختلف به روش های گوناگونی پیاده سازی می شوند و الگوریتم کلی برای آن ها وجود ندارد.