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

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

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

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

3000 تومان
دانلود پروژه کامل مهندسی نرم افزار ، شرکت نرم افزاری

دانلود پروژه کامل مهندسی نرم افزار ، شرکت نرم افزاری

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

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

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

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

9500 تومان

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

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

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

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