advertise laitec sharif univercity
دانلود پروژه پایانی طراحی وب سایت مخابرات با Asp.net

دانلود پروژه پایانی طراحی وب سایت مخابرات با Asp.net

28000 تومان
دانلود برنامه آزمون تستی در مالتی مدیا بیلدر MMb

دانلود برنامه آزمون تستی در مالتی مدیا بیلدر MMb

5000 تومان
دانلود پروژه وب سایت اشعار با ASP.NET و SQL

دانلود پروژه وب سایت اشعار با ASP.NET و SQL

5000 تومان
دانلود سورس اندروید اپلیکیشن افزایش سرعت گوشی

دانلود سورس اندروید اپلیکیشن افزایش سرعت گوشی

12000 تومان
پروژه پایانی PHP وب سایت فروشگاه کامپیوتری

پروژه پایانی PHP وب سایت فروشگاه کامپیوتری

48000 تومان

الگوریتم جست وجوی *A، مینیمم کردن کل هزینه جواب

الگوریتم جست وجوی *A، از دیگر استراتژی های جست وجوی آگاهانه میباشد و گره ای را برای بسط انتخاب میکند که مسیر بهینه ای برای آن پیدا شده باشد و در شرایطی کامل و بهینه است
الگوریتم جست وجوی *A، مینیمم کردن کل هزینه جواب

الگوریتم جست وجوی*A، مینیمم کردن کل هزینه جواب

معروفترین شکل"جست وجوی اول-بهترین" جست وجوی A* نام دارد که از دیگر  استراتژی های جست وجوی آگاهانه میباشد  . این روش گره ها را با ترکیب g(n) یعنی هزینه رسیدن به گره و h(n) یعنی هزینه رسیدن از این گره به گره هدف، ارزیابی میکند:

f(n)= g(n)+h(n)

چون g(n) هزینه مسیری از گره شروع به گره n و h(n) هزینه برآورد شده ی ارزانترین مسیر از n به گره هدف است، داریم:

 f(n) = n هزینه برآورد شده ارزانترین جواب از طریق  

پس اگر سعی در یافتن ارزانترین جواب داشته باشیم، منطقی است که ابتدا راجع به گره ای فکر کنیم که کمترین مقدار  g(n)+h(n)را دارد. پس نتیجه میشود که این استراتژی فراتر از منطقی بودن است، بطوریکه اگر تابع ابتکاری h(n) بعضی از شرایط را برآورده کند، جست وجوی A* کامل و بهینه است.

شرایط بهینگی: قابل قبول بودن و سازگاری الگوریتم های چستوجو

اولین شرط بهینگی این است که  h(n) یک ابتکار قابل قبول باشد. ابتکار قابل قبول آن است که هزینه رسیدن به هدف را هرگز برآورد نکند. چون g(n) هزینه واقعی برای رسیدن به گره n در امتداد مسیر فعلی است و f(n)=g(n)+h(n) ، نتیجه میگیریم که f(n) هرگز هزینه جواب را در امتداد مسیر فعلی از طریق گره n ،زیاد برآورد نمیکند.

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

شرط قوی تر دیگری بنام سازگاری (یکنواختی یا یکنوایی) برای کاربرد A* در جست وجوی گراف ، ضروری است. تابع ابتکاری h(n) در صورتی سازگار است که برای هر گره n و هر پسین گره n بنام گره n’ که توسط فعالیتی مثل a ایجاد شد، هزینه تخمینی رسیدن به گره هدف از گره n بیش از هزینه مرحله ی  رسیدن به n’ به اضافه هزینه تخمینی رسیدن به هدف از گره n’ نباشد:

h(n)<=c(n,a,n’)+h(n’)

 

بهینه بودن الگوریتم جست وجوی A*

A* دارای این خاصیت است: نسخه جست وجوی درختی A* در صورتی بهینه است که  h(n) قابل قبول باشد، درحالیکه نسخه جست وجوی گرافی A* در صورتی بهینه است که h(n) سازگار باشد.

نکته بعدی در مورد این الگوریتم این است که هر وقت A* گره ای را برای بسط انتخاب میکند، مسیر بهینه ای برای آن گره پیدا شده است.

پس نتیجه میشود که دنباله ای از گره ها که توسط A* و با استفاده از جست وجوی گرافی بسط داده میشوند، برحسب f(n) به ترتیب غیرنزولی هستند. بنابراین، اولین گره هدفی که برای بسط انتخاب شد باید یک جواب بهینه باشد، زیرا f هزینه گره های هدف است و تمام گره های هدف بعدی، گرانتر خواهند بود.

آخرین نکته این است که از بین الگوریتم های بهینه، A* برای هر ابتکار سازگار، بهینه کارآمد یا بهینه موثر است. یعنی، تضمینی نیست که هیچ الگوریتم بهینه دیگری وجود داشته باشد که تعداد گره های کمتر از A* بسط دهد.

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

 

 

 



0
نظرات

نظر خود را ارسال کنید



نام:
ایمیل:
دیدگاه:
captcha
کد امنیتی :


advertise
شبه کد الگوریتم جست وجوی *Aالگوریتم A* searchالگوریتم جست وجوی ابتکاری *Aآشنایی با جست وجوی اول-بهترین *Aجست وجوی آگاهانه *Aالگوریتم جست وجوی اول-بهترین *Aمینیمم کردن کل هزینه جواب چیست؟الگوریتم جست وجوی *A چیست؟معرفی جست وجوی اول-بهترین *Aالگوریتم جست وجوی هیوریستیک *Aالگوریتم جست وجوی *Aدانلود رایگان سورس کد الگوریتم *A لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

پیشنهادات ویژه سورس کد

پکیج ویژه پروژه پایانی رشته کامپیوتر دانلود مجموعه 70 پروژه کاربردی سی شارپ وب سایت فروشگاه با php