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

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

عدول کردن

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

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

عدول کردن توسط ریاضی دان آمریکایی 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* دانست .اولین-بهترین الگوریتم ها اغلب برای برای مسیریابی در جستجوی ترکیبی استفاده می شود.

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

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

الگوریتم های جستجوی ناشیانه یاجستجوی جاهلانه ساده ترین وابتدایی ترین روش جستجو را در فضای جستجو استفاده می کنند،جایی که الگوریتم های جستجکی آگاهانه روش های اکتشافی را برای کسب دانش

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

جستجوی ناآگاهانه

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

جستجوی درختی

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

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

و جستجو با هزینه یکنواخت مشود.

جستجوی گرافی

بسیاری  از مسائل در تئوری گراف می تواند با استفاده از الگوریتم های جستجو حل کرد،مانند الگوریتم Dijkstra ،الگوریتم Kruskal  ،الگوریتم نزدیک ترین همسایه ،الگوریتم Prima .اینها را می توان به عنوان گسترش دهنده الگوریتم های جستجوی درختی فرض کرد.

جستجو پایاپای

تا زمانیکه جستجوی SQL انعطاف پذیری بسیاری را برای جستجو اطلاعات ارایه می دهد،همچنان همچون رایانه عمل می کند:با محدودیت.در SQL محدودیت ها برای حذف اطلاعات استفاده میشوند،درحالیکه جستجوی پایاپای استعاره انسانی را بیشتر مورد استفاده قرار می دهد.برای مثال اگر شما به دنبال یک خودرو در یک سری اطلاعات می گردید ،اظهاریه SQL شما این چنین خواهد بود:انتخاب کنید خودرو را از اطلاعات جایی که قیمت کمتر از 30000 $باشد ،ومصرف بالاتر از 30MPG باشد ،رنگ آن قرمز باشد.

درحالیکه جستجوی پایاپای مانند این خواهد بود ،"من خودرو قرمز را دوست دارم ،اما من آبی را انتخاب میکنم اگر 2000$ارزان تر باشد."

جستجوی آگاهانه

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

جستجوی ناسازگار

در بازی هایی مانند شطرنج ،یک درخت بازی از همه امکان های حرکت توسط هردوبازیکن ووضعیت های

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

جبران محدودیت

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

انواع دیگر