advertise laitec sharif univercity استخراج بیت کوین با کامپیوتر استخراج بیت کوین با کامپیوتر
دانلود پروژه فروشنده دوره گرد با الگوریتم ازدحام ذرات PSO در #C

دانلود پروژه فروشنده دوره گرد با الگوریتم ازدحام ذرات PSO در #C

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

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

9500 تومان
دانلود پروژه مدیریت کتابخانه با سی شارپ و SQL سرور

دانلود پروژه مدیریت کتابخانه با سی شارپ و SQL سرور

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

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

3000 تومان
پکیج ویژه پروژه پایانی و پایان نامه رشته کامپیوتر

پکیج ویژه پروژه پایانی و پایان نامه رشته کامپیوتر

45000 تومان

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

کسب درآمد با کامپیوتر
تولید بیت کوین با کامپیوتر

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

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