advertise laitec sharif univercity تبلیغات در سایت سورس کد تبلیغات در سایت سورس کد
دانلود پروژه مهندسی نرم افزار ، نمایندگی ایران خودرو

دانلود پروژه مهندسی نرم افزار ، نمایندگی ایران خودرو

3000 تومان
دانلود مقاله ای در مورد الگوریتم  کرم شب تاب FireFly در هوش مصنوعی

دانلود مقاله ای در مورد الگوریتم کرم شب تاب FireFly در هوش مصنوعی

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

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

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

دانلود مجموعه 70 پروژه مفید و کاربردی سی شارپ #C

9500 تومان
دانلود سورس پروژه سی شارپ شبیه سازی صف بانک تحت شبکه

دانلود سورس پروژه سی شارپ شبیه سازی صف بانک تحت شبکه

3000 تومان

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

سفارش پروژه در سورس کد

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

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