۳-۲۱-۲-۱ حرکت بهترین-شروع[۱۲۰]
الگوریتم های مختلفی برای روش بهترین-شروع وجود دارند که می توان به خزنده متمرکز، جستجوی کوسه ای، عنکبوتهای اطلاعاتی و… اشاره کرد. در روش بهترین-شروع زمانی به وجودآورنده یک صفحه مانند A از صفحه خود به صفحـه دیگری مانند B لینک برقرار می کند که B از نظر A ارزشمند باشد. یکی از معیارهای بهترین بودن، استفاده از الگوریتم های رتبه بندی صفحات می باشد که واحد کنترل با توجه به رتبه هر صفحه، صفحات را انتخاب کرده و به واحد واکشی می فرستد. به طور نسبی می توان گفت که از نظر واحد کنترل صفحه ای دارای رتبه ی بالاتری است که لینک های بیشتری به آن برقرار شده باشد]۳۵ و ۵۴[. بنابراین می توان گفت که از نظر خزنده هایی که از حرکت بهترین-شروع استفاده می کنند صفحه ای با ارزش تر است که]۴۲[:
-
- لینک های بیشتری به آن صفحه اشاره کنند. برقراری لینک های بیشتر به یک صفحه نشانگر اهمیت و محبوبیت آن صفحه خواهد بود.
-
- هر چه این لینکها از صفحات معتبرتری برقرار شود آن صفحه دارای اهمیت بیشتری خواهد بود.
-
- در صورتیکه از صفحه موردنظر به سایر صفحات لینک برقرار شود از ارزش و اهمیت صفحه موردنظر کاسته خواهد شد.
می توان رتبه یک صفحه را از طریق Eq (3-1) زیر محاسبه نمود]۳۵[.:
Eq (3-1)
در فرمول بالا U نشانگر صفحه اصلی،FU نشانگر صفحاتی که از صفحه اصلی U به آنها لینک برقرار شده است و BU نشان دهنده ی صفحاتی است که به صفحه اصلی U لینک برقرار نموده اندR(V) نیز رتبه صفحات برقرارکننده لینک به صفحه اصلی U می باشد. با بهره گرفتن از نتایج این فرمول می توان پاسخ های بهتر و دقیق تری را در اختیار کاربران قرار داد اما ناجورک و وینر(۲۰۰۱) در عمل ثابت کردند که با توجه به هزینه و زمان بالای رتبه بندی صفحات وب و همچنین عدم ثبات رتبه صفحات در هنگام بایگانی، روش اول سطح به نسبت روش رتبه بندی بهتر عمل می نماید. لینک ها به وسیله محاسبات ساده از طریق شباهت لغوی بیـن عناوین کلمـات کلیدی و صفحات منبع انتخاب می شوند. بنابراین تشابه بین یک صفحه p و عناوین کلمات کلیدی، برای تخمین ارتباط صفحاتی که توسط p اشاره شد به کار می رود وURL با بهترین تخمین برای خزیدن انتخاب می شود. همچنین از تشـابه کسینـوسی استفـاده شده و لینک های با پایین ترین امتیاز تشـابه از محدوده حذف می گـردند]۵۴[. شکل ۳-۱۱ یک خزنده با استـراتژی بهترین-شروع را نمایش می دهد.
Web page
Link
FIFO Queue
Link estimator
شکل ۳-۱۱ یک خزنده با استراتژی بهترین-شروع ]۳۵[
تابع ()sim در Eq (3-2) تشابه کسینوسی بین موضوع و صفحه را بر می گرداند]۳۶[:
Sim(q , p) = Eq (3-2)
در Eq (3-2)، q موضوع مورد نظر، p صفحه واکشی شده و fkd فرکانس واژه k در d می باشد. الگوریتم یک خزنده با استراتژی بهترین-شروع به صورت شکل ۳-۱۲ می باشد:
BFS (topic, starting_urls) {
foreach links (starting_urls) {
enqeueu(frontier, link);
}
While (visited < MAX_PAGES) {
link := dequeue_top_link(frontier);
doc := fetch(link);
score := sin(topic, doc);
enqeueu (frontier, extract_links(doc), score);
if (#frontier > MAX_BUFFER) {
dequeue_botton_links(frontier) ;
}
}
}
شکل ۳-۱۲ الگوریتم خزنده با استراتژی بهترین-شروع ]۳۶[
۳-۱۲-۲-۲ جستجوی A*
معروفترین فرم جستجـوی بهتـرین-شروع، جستجـوی A* اسـت که یکـی از الگوریتـم های پیچیده جستجـو می باشـد. جستجوی A*سعی می کند مجموع هزینه پرداخت شده تا گره فعلی و هزینه باقی مانده از گره فعلی تا هدف را مینیمم کند.
تخمین هزینه باقی مانده تا هدف را هیوریستیک مسئله می گویند. طراحی هیوریستیک مسئله در روش جستجوی A* از اهمیت بسزایی برخوردار است و بهینگی روش A* تحت تاثیر طراحی هیوریستیک مسئله قرار دارد. مطابق(۳-۳) Eq هیوریستیکی قابل قبول[۱۲۱] است که هزینه تخمینی آن از نقطه فعلی تا نقطه هدف، از هزینه واقعی قابل پرداخت از نقطه فعلی تا نقطه هدف کمتر باشد به عبارت دیگر هزینه رسیدن به هدف را بیش از اندازه واقعی تخمین نزند]۲۹[.
h(n)≤h*(n)
h(n)≥۰ Eq (3-3) 0 ≤h(n) ≤h*(n)
هیوریستیکی که این شرط را برآورده نکند ، هیوریستیک غیرقابل قبول می نامند.
تابع ارزیاب در روش A*، f(n) = g(n) + h(n) می باشد]۵۲[. در واقعf(n) هزینه تخمینی ارزانترین راه حل از طریق n می باشد. با توجه به مطالب فوق چنین بیان می کنیم که در آن f هزینه کل گره، g هزینه تا گره فعلی و h هزینه تخمینی تا گره هدف را نشان می دهد. در جستجوی A* گره بعدی برای گسترش گره ای است که کمترین هزینه f را در میان گره های گسترش نیافته دیگر داشته باشد. در روش A* همیشه همه گره های برگ در محیط عملیاتی که هنوز بسـط داده نشده اند، بررسـی و مقایسه می شوند بنابراین همه گره ها در حافظه قرار می گیرند و برخی گره ها نیز ممکن است بارها ارزیابی و بررسی شوند. بنابراین پیچیدگی زمانی و فضایی این روش نمایی و بالا و برابرO(bm) است]۴۲[.
۳-۱۲-۳ جستجوی محلی
الگوریتم های جستجویی که تاکنون توضیح داده شد، به گونه ای طراحی شده اند که یک یا چند مسیر را در حافظه نگهداری می کنند تا وقتی هدف پیدا شود. مسیر رسیدن به آن هدف، به عنوان راه حل مساله انتخاب خواهد شد. اما در بسیاری از مسائل، مسیر رسیدن به هدف مهم نیست بلکه تنها دستیابی به هدف مهم است. در این گونه مسائل، از دسته ای دیگر از الگوریتم های جستجو با عنوان جستجوهای محلی استفـاده می کنیم. در این نوع روش ها به جای در نظر گرفتن چندین مسیر، تنها بر اساس حالت فعلی تصمیم گیری و عمل می شود، این نوع الگوریتـم ها پس از حرکت از حالت فعلی، تنها به همسایه های آن حالت منتقـل
می شوند، مسیرهایی که در جستجو در پیش گرفته می شوند، در حافظه نگهداری نمی شوند]۲۲[.
الگوریتم های جستجوی محلی علاوه بر یافتن هدف، برای حل مسایل بهینه سازی که در آن ها مقصود، یافتن بهترین حالت بر اساس یک تابع هدف است، نیز مناسبند. در زیر به بررسی برخی از مهمترین الگوریتم های محلی پرداخته شده است:
۳-۱۲-۳-۱ جستجوی تپه نوردی[۱۲۲]
یکی دیگر از الگوریتم هایی که در پیمایش گراف مورد استفاده قرار میگیرد، الگوریتم تپه نوردی می باشد. الگوریتم تپه نوردی بدین صورت است که ابتدا جوابی به شکل تصادفی برای مساله تولید می شود و سپس در یک حلقه و تا زمانی که شرط توقف الگوریتم برقرار نشده است، به طور مکرر تعدادی همسایه برای حالت فعلی تولید و از میان حالت های همسایه، بهترین آن ها انتخاب و جایگزین حالت فعلی می شود. برای پیاده سازی روش تپه نوردی نیاز به دو تابع Objective و Neighbor است. تابع Objective میزان بهینگی جواب مسئله را تعیین و تابع Neighbor نیز همسایه های حالت فعلی را تولید می کند]۳۰[. در شکل ۳-۱۳ شبه کد زیر نحوه پیاده سازی الگوریتم تپه نوردی را نشان می دهد:
|
[پنجشنبه 1400-08-13] [ 11:16:00 ب.ظ ]
|
