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

بخشی از مقاله

الگوريتم های جستجو

عدول کردن
عدول کردن نوعی الگوریتم است که جستجوی ناشیانه را پالایش می کند.در عدول کردن ،راه حل های متعددی را می توان بدون اینکه صریحا آزمایش کرد ،با استفاده از متعلقات خاص مسئله ، حذف کرد.
این مسئله می تواند یک استراتزی برای یافتن راه حل هایی باشد که بتوان حل مسائل را محدود کرد.بحث
عدول کردن توسط ریاضی دان آمریکایی 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* دانست .اولین-بهترین الگوریتم ها اغلب برای برای مسیریابی در جستجوی ترکیبی استفاده می شود.
الگوریتم جستجو
در علوم کامپیوتر ،یک الگوریتم جستجو ،اگر کلی صحبت کنیم ،یک الگوریتم است که یک مسئله را بعنوان ورودی ویک راه حل برای مسئله ارایه می دهد،معمولا بعد از ارزشیابی یک سری از راه حل های ممکن می باشد.بسیاری از الگوریتم های مورد مطالعه توسط محققان کامپیوتر که مسائل را حل می کنند انواعی از الگوریتم های جستجو هستند.سری همه راه حل های ممکن به یک مسئله فضای جستجوی نامیده می شود.

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

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