آموزش مقدماتی برنامه نویسی هوش مصنوعی

[DeMoN]

به نام خدا

 

با سلام خدمت دوستان عزیز.

در این پست بنده میپردازم به آموزش برنامه نویسی هوش مصنوعی.

خوب این نوع برنامه نویسی در بسیاری از فروم های امنیتی نیست یا اگر هم وجود داشته باشه ناقص هست و نا مفهوم.

در این پست آموزشات مقدماتی این نوع برنامه نویسی قرار میگیره و در پست های بعدی برنامه نویسی پیشرفته هوش مصنوعی قرار خواهد گرفت.

آموزشات ما دارای دو سر فصل اصلی است:

1-مفاهیم

با زیر مجموعه های:

راهبردهای جست و جوی آگاهانه,توابع هیوریستیک,جستجوی محلی

2-انواع جستجوی های آگاهانه

با زیر مجموعه های :

جستجوی حریصانه,جستجوی A,جستجوی IDA,جستجوی بازگشتی RBFS

 

موفق و موید باشید

 

[جهت حفظ قانون کپی رایت:

نویسندگان:

استوارت راسل، پیتر نورویگ(ترجمه و تنظیم توسط تیم امنیتی گارد ایران)]

 

This is the hidden content, please

• ورود
• یا
• ثبت نام

[DeMoN]

بخش اول

 

 

مفاهیم:

راهبردهای جستجوی آگاهانه

توابع هیوریستیک

جستجوی محلی

===================

راهبردهای جستجوی آگاهانه

 

جستجوي اول بهترين:

 

اين استراتژي به اين صورت بيان مي‌شود که در يک درخت، زماني که گره‌ها مرتب مي‌شوند، گره‌اي که بهترين ارزيابي را داشته باشد، قبل از ديگر گره‌ها بسط داده مي‌شود.

هدف: يافتن راه‌حل‌هاي کم‌هزينه است، اين الگوريتم‌ها عموماً از تعدادي معيار تخمين براي هزينه راه‌حل‌ها استفاده مي‌‌کنند و سعي بر حداقل کردن آنها دارند.

 

جستجوی اول بهترین

 

تابع ارزیابی :

 

f(n) تابع ارزیابی گره n ، تابعی است که فاصله گره n تا هدف را تخمین می زند.

توابع هیوریستیک : معمولیترین شکل رساندن اطلاعات اضافی مساله به الگوریتم جستجو هستند.

h(n) هزینه تخمینی کوتاهترین(ارزانترین) مسیر از گره n به هدف است. 

 

 

[DeMoN]

بخش دوم

 

 

 جستجوي حریصانه

 جستجوي A*

 جستجوي IDA*

 جستجوي بازگشتی RBFS

===================

جستجوی حریصانه

 

حداقل هزينه تخمين زده شده براي رسيدن به هدف:

 

يکي از ساده‌ترين استراتژي‌هاي جستجوي بهترين، به حداقل رساندن هزينه تخمين زده شده براي رسيدن به هدف است. بدين صورت که حالت گره‌اي که به حالت 

هدف نزديک ‌تر است، ابتدا بسط داده مي‌شود.

 

جستجوي حريصانه: جستجوي بهترين که h را به منظور انتخاب گره بعدي براي بسط استفاده مي‌کند، جستجوي حريصانه (greedy search) ناميده مي‌شود.

This is the hidden content, please

• ورود
• یا
• ثبت نام

 

 

 

تابع هیوریستیک در مثال رسیدن به شهر بخارست:

This is the hidden content, please

• ورود
• یا
• ثبت نام

[DeMoN]

بخش سوم

 

جستجوی حریصانه

 

به مثالهای زیر توجه کنید:

 

1-

This is the hidden content, please

• ورود
• یا
• ثبت نام

 

2-

This is the hidden content, please

• ورود
• یا
• ثبت نام

3-

This is the hidden content, please

• ورود
• یا
• ثبت نام

4-

This is the hidden content, please

• ورود
• یا
• ثبت نام

 

[DeMoN]

بخش چهارم

 

 

ادمه...

 

به موارد و توضیحات زیر دقت کنید:

 

5-

This is the hidden content, please

• ورود
• یا
• ثبت نام

 

6-

This is the hidden content, please

• ورود
• یا
• ثبت نام

 

7-

This is the hidden content, please

• ورود
• یا
• ثبت نام

 

8-

This is the hidden content, please

• ورود
• یا
• ثبت نام

[DeMoN]

بخش پنجم

 

 

ادامه...

 

به موارد و مثال های زیر توجه کنید.

 

 

9-

This is the hidden content, please

• ورود
• یا
• ثبت نام

 

10-

This is the hidden content, please

• ورود
• یا
• ثبت نام

 

11-

This is the hidden content, please

• ورود
• یا
• ثبت نام

12-

This is the hidden content, please

• ورود
• یا
• ثبت نام

13-

This is the hidden content, please

• ورود
• یا
• ثبت نام

[DeMoN]

بخش ششم

 

جستجوی A*

 

تابع کشف‌کنندگي قابل قبول:

تابع hاي را که هزينه‌اي بيش از تخمين براي رسيدن به هدف نداشته باشد، يک کشف‌کنندگي قابل قبول (admissible heuristic) گويند.

 

This is the hidden content, please

• ورود
• یا
• ثبت نام

[DeMoN]

بخش هفتم

 

جست و جوی A*

 

به موارد زیر توجه کنید(نمونه ای از موارد بالا)

 

1-

This is the hidden content, please

• ورود
• یا
• ثبت نام

 

 

 

 

جستجوی  (Iterative deepening A*)IDA*

 

 

ساده ترين راه براي کاهش حافظه مورد نياز A* استفاده از عميق کننده تکرار در زمينه جست و جوي اکتشافي است.

الگوريتم عميق کننده تکرار A*                 

در جستجوي IDA* مقدار برش مورد استفاده، عمق نيست بلکه هزينه (f(g+h است.

IDA* براي اغلب مسئله هاي با هزينه هاي مرحله اي، مناسب است و از سربار ناشي از نگهداري صف مرتبي از گره ها اجتناب ميکند.

[DeMoN]

بخش هشتم

 

جستجوی RBFS 

 

ساختار آن شبيه جست و جوي عمقي بازگشتي است، اما به جاي اينکه دائما به طرف پايين مسير حرکت کند، مقدار f مربوط به بهترين مسير از هر جد گره فعلي را نگهداري ميکند، اگر گره فعلي از اين حد تجاوز کند، بازگشتي به عقب برميگردد تا مسير ديگري را انتخاب کند.

اين جستجو اگر تابع اکتشافي قابل قبولي داشته باشد، بهينه است.

پيچيدگي فضايي آن (O(bd است

تعيين پيچيدگي زماني آن به دقت تابع اکتشافي و ميزان تغيير بهترين مسير در اثر بسط گره ها بستگي دارد.

 

RBFS تا حدي از IDA* کارآمدتر است، اما گره هاي زيادي توليد ميکند.

 IDA* و RBFS در معرض افزايش تواني پيچيدگي قرار دارند که در جست و جوي گرافها مرسوم است، زيرا نميتوانند حالتهاي تکراري را در غير از مسير فعلي بررسي کنند. لذا، ممکن است يک حالت را چندين بار بررسي کنند.

[DeMoN]

بخش نهم

 

جستجوی SMA*

 

الگوريتم SMA*، حافظه محدود A* ساده شده (Simplified-Memory-BoundedA*) مي‌باشد.

اين الگوريتم، قادر است تا از تمام حافظه موجود براي اجراي جستجو استفاده کند. استفاده از حافظه بيشتر کارايي جستجو را وسعت مي‌بخشد. 

طراحي SMA* ساده است:

 زماني که نياز به توليد فرزند داشته باشد ولي حافظه‌اي نداشته باشد، نياز به ساختن فضا بر روي صف دارد. براي انجام اين امر، يک گره را حذف مي‌کند. گره‌هايي که به اين طريق از صف حذف مي‌شوند، گره‌هاي فراموش‌شده يا (forgotten nodes) ناميده مي‌شوند.

 براي اجتناب از جستجوي مجدد زيردرخت‌هايي که از حافظه حذف شده‌اند، در گره‌هاي اجدادي، اطلاعاتي در مورد کيفيت بهترين مسير در زير درخت فراموش شده، نگهداري مي‌شود.

 

The End./

 

پایان بخش آموزش مقدماتی برنامه نویسی هوش مصنوعی