عدول کردن نوعی الگوریتم است که جستجوی ناشیانه را پالایش می کند.در عدول کردن ،راه حل های متعددی را می توان بدون اینکه صریحا آزمایش کرد ،با استفاده از متعلقات خاص مسئله ، حذف کرد.
این مسئله می تواند یک استراتزی برای یافتن راه حل هایی باشد که بتوان حل مسائل را محدود کرد.بحث
عدول کردن توسط ریاضی دان آمریکایی D. H. Lehmer in 1950s اختراع شد.
اجراء
الگوریتم های عدول کن از هر امکانی استفاده می کند تا وقتی آنها مورد صحیح را بیابند.اولین جستجوی
زرف این سری از راه حل های ممکن می باشد. در طی جستجو ،اگر یک تبدیل کار نکند ،جستجو دوباره به مورد باز می گردد،مکانی که تبدیلات متنوعی را ارایه می دهد،و تبدیل بعدی را امتحان می کند.وقتی تبدیلات
تحلیل بروند ،جستجو دوباره به مورد قبلی باز می گردد و تبدیل بعدی را امتحان می کند.اگر مورد دیگری وجود نداشته باشد ،جستجو شکست می خورد.این مسئله اغلب در توابع بازگشتی به دست می آید جایی که هر
نمونه یک متغیر بیشتردر اختیار بگیرد و متناوبا همه ارزش های در دسترس را به آن تخصیص داد، ویکی را که با تماس های بازگشتی متعاقب سازگار است را نگاه داشت .عدول کردن شبیه اولین جستجوی زرف است اما حتی فضای کمتری را استفاده می کند ،فقط حالت راه حل اخیر را نگاه می دارد و آنرا به روزکند.
برای تسریع جستجو ،وقتی یک ارزش انتخاب شده است ،قبل از اینکه تماس بازگشتی انجام شود ، الگوریتم
یا آن ارزش را از تعارض قلمروهای تخصیص داده نشده ،حذف کند یا همه محدودیت ها را برای مشاهده
اینکه دیگر ارزش های نو را از ارزش های تخصیص داده شده مستثنی کرد.این موثرترین تکنیک برای مسائل محقق مانند کوله پشتی 0/1 و مسئله n-queen می باشد.این قضیه نتایج بهتری را نسبت برنامه ریزی دینامیک برای این مسائل ارایه میدهد.
روش اکتشافی
روش های اکتشافی بسیاری برای تسریع پروسه معمول هستند .چرا که متغیرها به هر ترتیبی پردازش می شوند ،به طور کلی ابتدا آزمایش موردهای اجباری موثرتر است (موردی که با گزینه های ارزشی کمتری است) همان گونه که درخت جستجو را زود قطع می کند.(تاثیر مورد اخیر را به حداکثر می رساند).
وقتی به دنبال انتخاب یک ارزش برای تخصیص هستیم ،بسیاری عملکردها را در آزمایش برای مشاهده اینکه
کدام ارزش حداقل شمار ارزش ها را محدود می کند،استفاده می کنیم ،در پیش بینی اینکه چنین موردی
1>بسیار محتمل در نگاه داشتن یک راه حل ممکن
2>یک راه حل زمانی پیدا می شود که شمار محدودیت های بسیار واضح به صفر کاهش پیدا کرده است.
عملکردهای پیچیده عدول کردن اغلب یک تابع اتصالی را برای راه حل پاره ای اخیراستفاده می کند،که آیا حصول یک راه حل امکان پذیر است.از این رو،یک آزمایش اتصالی که راه حل های پاره ای را معین می کند بهنگام شکست خوردن می تواند تاثیر گزاری جستجو را افزایش دهد.از آنجایی که در صورت امکان در هر مرحله اغلب اجرا می شود وهزینه محاسبه ای نیازهای محاسبه ای می بایست کمینه باشد،در غیر اینصورت
تاثیرگزاری کلی الگوریتم اصلاح نشده است.توابع اتصالی تاثیرگذار با یک روش مشابه به دیگر توابع اکتشافی خلق می شوند-توسط تعدیل قوانین مسئله .وقتی عدول کردن در یک زبان برنامه ریزی محدودیتی اتفاق می افتد،یک مقدار اضافی عملیاتی اتفاق می افتد زمانی که اطلاعات راجع به محدودیت ها وقتی توسط
حل کننده محدودیت استفاده می شود ،نیاز به روز شدن دارد.در این زبان ها اولین جستجوی زرف یک تکنیک
اجرایی کافی می باشد،همتن گونه که در Planner & Prolog استفاد شد.به علاوه حصول کمینه بهبود ارزش ها در پشتیبانی استفاده می شود ،عملکرد های عدول کردن به طور معمول یک مسیر متفاوت را حفظ
می کنند، تا اینکه یک سابقه از تغییر ارزش ضبط گردد.یک پیشنهاد متناوب در مسیر متغیر ثبت نوار زمانی
اینکه آخرین تغییر چه زمانی در متغیر ایجاد شده است.نوار زمانی با نوار زمانی نقطه گزینش مقایسه میشود.
اگر نقطه گزینش دارای زمان همراه دیرتر از زمان متغیر باشد،وقتی نقطه گزینش باز می گردد نیاز نیست که
متتغیر باز گردانده شود،همان گونه که قبل از رخ دادن نقطه گزینش تغییر کرده بود.
عملکردها
بیشترین استفاده عدول کردن در ضبط عبارات منظم می باشد.برای مثال ،عبارت ساده "a*a" در هماهنگ کردن مرحله "a" بدون عدول کردن شکست خواهد هورد.(چرا که در مرحله اول اولین "a" توسط "*" حذف می شودوچیزی برای "a" در هماهنگ شدن باقی نی گذارد.)استفاده معمول دیگر از عدول کردن در الگوریتم های راه یاب در جایی که تابع روی یک گراف از گره ها وراه های بازگشتی راه یابی کند تا وقتی که را کمترین هزینه را بیابد.عدول کردن در عملکرد زبان های برنامه ریزی (مانند Icon, Planner & Prolog )
و دیگر حوزه ها مانند تجزیه متن استفاده می شوند.
جستجوی باریکه ای
جستجوی باریکه ای الگوریتم اکتشافی جستجو است که بهینه سازی اولین وبهترین جستجو بوده اگرچه مفهوم
کلی آن را میتوان تقریبا به هر نوع الگوریتم تعمیم داد.جستجوی باریکه ای اگرچه اولین M که نوید بخش ترین گره در هر عمقی است را آشکار می کند،جایی که m یک عدد ثابت شده است و عرض باریکه میباشد.
پس اولین وبهترین جستجو برای مثال همیشه یک مسیر را با کمترین هزینه خالص مسیری را گسترش می دهد،جستجوی باریکه ای با m=2 بهترین دو مسیر را با کمترین هزینه خالص مسیری به جای یکی گسترش
می دهد.از آنجایی که جستجوی باریکه ای یک تابع کران دار از m میباشد،که یا بهینه است یا کامل از آنجایی که m محدود وکراندار است.با افزایش m جستجوی باریکه ای به وضیعت عملکرد اولین وبهترین
جستجو نزدیک می شود.در ابتدا حالات اتفاقی m انتخاب میشود.ادامه دهندگان این حالات m همه محاسبه شده است.اگر گره نهایی رسیده باشد، الگوریتم متوقف میشود.در غیر اینصورت بهترین حالات m از ادامه دهندگان انتخاب میشود ومراحل دوباره تکرار میشود.
جستجوی توده ای باریکه
جستجوی توده ای باریکه یک الگوریتم جستجو است که عدول کردن را با جستجوی باریکه ای جمع می کند.
این الگوریتم جستجودر طی پانزدهمین کنفرانس جهانی در مورد برنامه ریزی وطراحی اتوماتیک توسط
Rong Zhou and Eric A. Hansen عضو بخش علوم کامپیوتر ومهندسی دانشگاه میسیسیپی کالیفرنیا انجام شده بود. ومی توان به عنوان روشی برای تبدیل جستجو باریکه ای به الگوریتم جستجوی کامل استفاده کرد که برای یافتن یک راه حل بهینه گارانتی شده است.از یک ساختار اطلاعاتی جدید استفاده می کند،که توده باریکه نامیده میشود،که جمع بستن سیستماتیک جستجوی باریکه ای را باعدول کردن ممکن می سازد. الگوریتم حاصل جستجو یک الگوریتم هر زمانی است که راه حل خوب با بیشینه بهینه را به سرعت می یابد،
مانند جستجوی باریکه ای ،وبعد عدول کرده برای یافتن راه حل های اصلاح شده تا پوشش یک راه حل بهینه ادامه می یابد.در بسیاری جتبه ها تکنیک غالب ومقسم می تواند با جستجوی توده ای باریکه با همان روش جستجوی باریکه ای ترکیب شود و الگوریتمی بسازد که ما آنرا جستجوی توده ای باریکه غالب ومقسم می نامیم.
اولین – بهترین جستجو
اولین –بهترین جستجو یک الگوریتم جستجو است که اولین پهنای جستجو را توسط محتمل ترین گره که با توجه به تعدادی قانون انتخاب شده است ،بهینه می سازد.Judea Pearl اولین-بهترین جستجو را اینطور تشریح می کند که محتمل ترین گره n را توسط f(n) تابع ارزش یابی اکتشافی ،تخمین زده می شود،
که در کل به تشریح n بستگی دارد ،تشریح هدف ،اطلاعاتی که توسط جستجو در مورد آن جمع آوری می شود،و از همه مهمتر هر دانش اضافی راجع به حوزه مسئله می باشد."این دیدگاه کلی از قضیه توسط بسیاری نویسنوگان استفاده می شود ،که شامل Russell & Norvig می شود.نویسندگان دیگر اولین-بهترین جستجو رابرای ارجاع به جستجو با دیدگاهی اکتشافی که سعی دارد تا پیش بینی کند که چقدر انتهای میسر به یک راه حل نزدیک است ،پس مسیر هایی که به راه حل نزدیک تر باشندابتدا گسترش می سابند.مثال هایی از الگوریتم های اولین-بهترین جستجو شامل الگوریتم جستجوی A* میشود ،ودر عوض ،الگوریتم Dijkstra را می توان
تخصص یافته A* دانست .اولین-بهترین الگوریتم ها اغلب برای برای مسیریابی در جستجوی ترکیبی استفاده می شود.
فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد
تعداد صفحات این مقاله 14 صفحه
پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید
دانلودمقاله الگوریتم های جستجو
