مقاله دانشگاهی – بهینه سازی روش تشخیص اهمیت پیوند در پایگاه پیوند و کاربست آن در …

}
شکل ۳-۸ الگوریتم خزنده با استراتژی اول سطح ]۳۵[
در این روش، با فرض اینکه فاکتور انشعاب b و در بدترین حالت، هدف در عمقd باشد این روش تمامی نودهای موجود در عمق d را گسترش می دهد. تعداد گره های بسط داده شده تا عمق d برابر ۱+b+b2+…+bخواهد بود و در نهایت هنگامیکه به سطح d می رسیم، تعداد نودهای گسترش یافته، برابر است با bd و درنتیجه، پیچیدگی زمانی برابر است باT(bd) ]29[.
d[117] اشاره به عمق وb فاکتور انشعاب است که به حداکثر تعداد یالهایی که از درخت خارج می شون اشاره دارد. هر گره ای که در این روش گستـرش می یابد، باید در حافـظه ذخیره شود، زیرا خود جزیی برای تولیـد گره های دیگر است بنابراین پیچیدگی فضایی این روش نیز مانند پیچیدگی زمانی آن یعنی O(bd) است]۲۹[.
کارآیی یک روش بستگی به پیچیدگی زمانی و فضایی آن دارد. از آنجاییکه پیچیدگی های این روش نمایی و بسیار بالا است، بنابراین این روش کارآمد نیست. در شکل ۳-۹ چگونگی محاسبه پیچیدگی زمانی بر اساس جستجوی اول سطح در درخت باینری با فاکتور انشعاب b، نشان داده شده است:
۱ عمق ۰ ۱b عمق ۱
۲ b عمق۲
bعمق d
.
.
.
شکل ۳-۹ محاسبه پیچیدگی زمانی یک درخت جستجوی دودویی با استفاده از جستجوی اول سطح ]۲۹[
۳-۱۲-۱-۳ جستجو با هزینه یکنواخت[۱۱۸]
ایـن الگـوریتـم بهیـنه شـده ی روش اول سطـح است و در آن گـره ای ابتـدا تـوسعـه داده می شـود
که هزینه رسیـدن به آن حـداقل باشـد. برای پیاده سـازی این روش پیمـایش از صف اولویـت دار استفـاده می شـود. در اول صف همیشـه گره ای قرار می گیـرد که هزینـه رسیـدن به آن حـداقل باشد]۲۶ و ۴۰[.
نکته قابل توجه در مورد جستجوی هزینه یکنواخت این است که این روش جستجو در صورتی جواب بهینه را پیدا می کند که هزینه های هر گام به درستی انتخاب شوند. مشکلی که همچنان در این روش باقی مانده، گسترش گره های اضافی است که این امر موجب کندی در یافتن پاسخ می گردد.
در شکل ۱۰-۳، گره S شروع و گره G هدف می باشد، می خواهیم با استفاده از روش جستجو با هزینه یکنواخت مسیر بهینه را بیابیم. پیچیدگی زمانی و فضایی این روش O(b[c*/ɛ]) است کهc* ، هزینه ی تخمینی مسیر بهینه و e هزینه هر مرحله است. b فاکتور انشعاب می باشد که به حداکثر تعداد یالهایی که از درخت خارج می شوند اشاره دارد]۴۱[. مراحل رسیدن به هدف به صورت شکل ۱۰-۳ خواهد بود:
B
G
۱۰
۵
A
C
S
۱
۱۵
۵
۵
S
A B C
۱۵
G
۱۱ ۱۰
S
A B C
۵ ۱۵
G
۱۱

مطلب دیگر :
پژوهش - بهینه سازی روش تشخیص اهمیت پیوند در پایگاه پیوند و کاربست آن در معماری موتورهای ...

دانلود متن کامل این پایان نامه در سایت abisho.ir