مقاله درباره الگوریتم های جستجو

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

لینک پرداخت و دانلود در "پایین مطلب"

 فرمت فایل: word (قابل ویرایش و آماده پرینت)

 تعداد صفحات:13

عدول کردن

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

این مسئله می تواند یک استراتزی برای یافتن راه حل هایی باشد که بتوان حل مسائل را محدود کرد.بحث

عدول کردن توسط ریاضی دان آمریکایی D. H. Lehmer in 1950s اختراع شد.

اجراء

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

زرف  این سری از راه حل های ممکن می باشد. در طی جستجو ،اگر یک تبدیل کار نکند ،جستجو دوباره به مورد باز می گردد،مکانی که تبدیلات متنوعی را ارایه می دهد،و تبدیل بعدی را امتحان می کند.وقتی تبدیلات

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

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

برای تسریع جستجو ،وقتی یک ارزش انتخاب شده است ،قبل از اینکه تماس بازگشتی انجام شود ، الگوریتم

یا آن ارزش را از تعارض قلمروهای تخصیص داده نشده ،حذف کند یا همه محدودیت ها را برای مشاهده

اینکه دیگر ارزش های نو را از ارزش های تخصیص داده شده مستثنی کرد.این موثرترین تکنیک برای مسائل محقق مانند کوله پشتی 0/1 و مسئله n-queen می باشد.این قضیه نتایج بهتری را نسبت برنامه ریزی دینامیک برای این مسائل ارایه میدهد.

روش اکتشافی

روش های اکتشافی بسیاری برای تسریع پروسه معمول هستند .چرا که متغیرها به هر ترتیبی  پردازش می شوند ،به طور کلی ابتدا آزمایش موردهای اجباری موثرتر است (موردی که با گزینه های ارزشی کمتری است) همان گونه که درخت جستجو را زود قطع می کند.(تاثیر مورد اخیر را به حداکثر می رساند).

وقتی به دنبال انتخاب یک ارزش برای تخصیص هستیم ،بسیاری عملکردها را در آزمایش برای مشاهده اینکه

کدام ارزش حداقل شمار ارزش ها را محدود می کند،استفاده می کنیم ،در پیش بینی اینکه چنین موردی

1>بسیار محتمل در نگاه داشتن یک راه حل ممکن

2>یک راه حل زمانی پیدا می شود که شمار محدودیت های بسیار واضح به صفر کاهش پیدا کرده است.

عملکردهای پیچیده عدول کردن اغلب یک تابع اتصالی را برای راه حل پاره ای اخیراستفاده می کند،که آیا حصول یک راه حل امکان پذیر است.از این رو،یک آزمایش اتصالی که راه حل های پاره ای را معین می کند بهنگام  شکست خوردن می تواند تاثیر گزاری جستجو را افزایش دهد.از آنجایی که در صورت امکان در هر مرحله اغلب اجرا می شود وهزینه محاسبه ای نیازهای محاسبه ای می بایست کمینه باشد،در غیر اینصورت

تاثیرگزاری کلی الگوریتم اصلاح نشده است.توابع اتصالی تاثیرگذار با یک روش مشابه به دیگر توابع اکتشافی خلق می شوند-توسط تعدیل قوانین مسئله .وقتی عدول کردن در یک زبان برنامه ریزی محدودیتی  اتفاق می افتد،یک مقدار اضافی عملیاتی اتفاق می افتد زمانی که اطلاعات راجع به محدودیت ها وقتی توسط

حل کننده محدودیت استفاده می شود ،نیاز به روز شدن دارد.در این زبان ها اولین جستجوی زرف یک تکنیک

اجرایی کافی می باشد،همتن گونه که در Planner & Prolog استفاد شد.به علاوه حصول کمینه بهبود ارزش ها در پشتیبانی استفاده می شود ،عملکرد های عدول کردن به طور معمول یک مسیر متفاوت را حفظ

می کنند، تا اینکه یک سابقه از تغییر ارزش ضبط گردد.یک پیشنهاد متناوب در مسیر متغیر ثبت نوار زمانی

اینکه آخرین تغییر چه زمانی در متغیر ایجاد شده است.نوار زمانی با نوار زمانی  نقطه گزینش مقایسه میشود.