جستجوی
اولین بهترین از صف اولویت استفاده میکند.
برای
تبدیل جستجوی UCS
به
بهترین جستجو میتوانیم فرض کنیم f(n)
= g(n) و
برای تبدیل BFS
میتوانیم
فرض کنیم f(n)
= depth(n) و
برای تبدیل DFS
میتوانیم
فرض کنیم f(n)
= 1/depth(n)
هیورستیک
هدف باید صفر باشد.
الگوریتم
های جستجوی آگاهانه :
جستجوی
حریصانه.
الگوریتم
A*.
الگوریتم
جستجوی مسیر اکتشافی.
الگوریتم
IDA*.
الگوریتم
بهترین جستجوی بازگشتی RBFS.
الگوریتم
SMA*.
تپه
نوردی.
قدم
زدن تصادفی.
شبیه
سازی ذوب فلزات.پرتو
محلی.
ژنتیک.جستجوی
عمقی آنلاین.LRTA*
مقدار
هیورستیک معمولا برای گره های نزدیک هدف
بهینگی کمتری دارد.
ارزیابی
جستجوی حریصانه :
کامل
نیست(اگر
بصورت گرافی باشد کامل است)
بهینه
نیست.
پیچیدگی
زمانی و فضایی نمایی دارد O(b^m).
الگوریتم
UCS
حالت
خاص A*
با
h(n)
= 0 است.
ارزیابی
الگوریتم A*
: کامل
است.
بهینه
است.(اگر
تابع هیورستیک قابل قبول و یا یکنواخت
باشد).
پیچیدگی
زمانی در بدترین حالت نمایی است اما ممکن
است با انتخاب هیورستیک خوب سرعت بالاتری
داشته باشد.
پیچیدگی
فضایی نمایی است چون تمام گره های در حافظه
نگهداری میشوند.
اگر
یک هیورستیک یکنواخت باشد قابل قبول هم
هست اما عکس آن صحیح نیست.
اگر
یک هیورستیک یکنواخت باشد مقادیر f(n)
در
طول هر مسیر غیر نزولی است.
اگر
الگوریتم A*
بصورت
گرافی پیاده سازی شود برای بهینه بودن
باید هیورستیک سازگار باشد.
الگوریتم
A*
هیچ
تمام گرهها با هزینه کمتر از راه حل بهینه
را بسط میدهد و هیچ گرهی با هزینه بیشتر
از راه حل بهینه را بسط نمیدهد.
به
ازای هر هیورستیک قابل قبول الگوریتم A*
کارآمد
بهینه است.
ارزیابی
الگوریتم IDA*
: کامل
و بهینه بودن مانند A*
است
و پیچیدگی فضایی خطی است و پیچیدگی زمانی
نمایی است.
الگوریتم
IDA*
برخلاف
A*
نیازی
به نگهداری گره های حاشیه ندارد در صف
اولویت ندارد.
ارزیابی
الگوریتم بهترین جستجوی بازگشتی RBFS
: پیچیدگی
فضایی خطی دارد O(bd)
. مانند
A*
بهینه
است.
هزینه
زمانی نمایی است.
اگر
هدف در عمق SMA
باشد
حتما پیدا میشود و اگر راه حل بهینه در
عمق قابل دسترس SMA
باشد
حتما پیدا میشود.
حالتی
شبیه حالت کوبیدگی سیستم عامل ممکن است
برای SMA
پیش
بیاید.
هزینه
مساله راحت یک هیورستیک قابل قبول است.
پیچیدگی
فضایی الگوریتم های جستجوی محلی ثابت
است.
الگوریتمهای
جستجوی محلی علاوه بر یافتن هدف برای حل
مسایل بهینه سازی هم بکار میروند.
تپه
نوردی استاندارد گرادیان/شیب
صعودی/نزولی
است زیرا همیشه به بهترین همسایه میرود.
مشکل
تپه نوردی ماکزیمم محلی و فلات است.
تپه
نوردی غیر قطعی شیب کمتری دارد اما در
برخی مسایل راه حل بهتری پیدا میکند.
تپه
نوردی اولین انتخاب(تپه
نوردی ساده)
جاهایی
مناسب است که جانشینهای زیادی داشته
باشیم.
هیچ
صورت تپه نوردی کامل نیست.
اگر
تعداد ماکزیمم های محلی و فلات کم باشد
تپه نوردی شروع مجدد تصادفی سریعا راه حل
خوبی را پیدا میکند در غیر اینصورت یک
ماکزیمم محلی خوب پیدا میکند.
الگوریتم
قدم زدن تصادفی کامل است اما کارآمد نیست.
در
ذوب فلزات اگر T=0
باشد
آنگاه تپه نوردی اولین انتخاب و اگر T
بینهایت
باشد قدم زدن تصادفی است.
پرتو
محلی با K
تا
تپه نوردی موازی متفاوت است.
پرتو
محلی با K=1
همان
تپه نوردی و با K
بینهایت
همان BFS
است
که در هر سطح همگی گرهها همزمان تولید
میشوند اما در BFS
گره
ها یکی یکی تولید میشوند.
در
مرحله selection
یک
کرومزوم میتواند چندبار انتخاب شود.
الگوریتم
ژنتیک نوعی از پروتوی غیر قطعی است و
همچنین نوعی تپه نوردی غیر قطعی!
نسلها
به مرور در الگوریتم ژنتیک همگرا میشوند.
الگوریتم
پرتو محلی و ژنتیک مبتنی بر جمعیت هستند.
همه
الگوریتم های جستجوی محلی تست و تولید
هستند.
اگر
مثلا راه حل معکوس پذیر نباشد نسبت رقابتی
بینهایت است.
الگوریتم
آنلاین فقط میتواند گرهی که درآن است را
بسط دهد و نمیتواند به شاخه دیگری بپرد.
جستجوی
عمقی آنلاین فقط در حالتی میتواند کار
کند که معکوس پذیر باشد.
در
جستجوی عمقی آنلاین ممکن است نسبت رقابتی
خیلی بزرگ شود اما جستجوی عمقی تکراری
این مشکل را ندارد و نسبت عدد ثابت کوچک
است.
شرط
خاتمه در ژنتیک میتواند نسل باشد.
اگر
برای مساله ای هیچ راه حل کامل ناآگاهانه
ای وجود نداشته باشد آنگاه هیچ راه حل
کامل آگاهانه ای ندارد و اگر برای مساله
ای یک راه حل کامل ناآگاهانه وجود داشته
باشد آنگاه حداقل یک راه حل کامل آگاهانه
وجود دارد.
هرگاه
در یک مساله به دنبال تمام جوابها باشیم
بهتر است از روش تولید و آزمون اقدام کنیم.
بطور
کلی الگوریتم های آنلاین تمایل بیشتری
به ماندن در حالت جاری دارند.
وجود
حجم اطلاعات کلیدی زیاد باعث میشود طول
رشته کرومزوم افزایش یابد و در نتیجه
فرآیند بهینه سازی پیچیده تر میشود.
آموزش
در الگوریتم ژنتیک برپایه بهینه سازی مدل
استوار است.
برنامه
ژنتیکی دارای کرومزوم درختی است.
چیزهایی
که باید از کتاب خوانده شود:
بهترین
جستجو.
هیورستیک
های پازل ۸.
جستجوی
حریصانه.
الگوریتم
A*.
هیورستیک
قابل قبول/admissible
. هیورستیک
سازگار/یکنواخت/یکنوا/Consistent.
کانتور.
الگوریتم
جستجوی مسیر اکتشافی.الگوریتم
IDA*.الگوریتم
بهترین جستجوی بازگشتی RBFS.
الگوریتم
SMA*.
غلبه
در هیورستیک.
فاکتور
انشعاب موثر.مساله
راحت.
تپه
نوردی.
قدم
زدن تصادفی.
شبیه
سازی ذوب فلزات.
پرتو
محلی.
ژنتیک.
تعریف
فنوتایپ و کرومزوم و تابع برازش.
انواع
روشهای crossover.تست
و تولید.عامل
جستجوی آنلاین.
نسبت
رقابتی.جستجوی
عمقی آنلاین.LRTA*
هیچ نظری موجود نیست:
ارسال یک نظر