اثبات کامل بودن A*

چون A* به منظور افزایش f گره­ ها را بسط می دهد، سرانجام باید به یک حالت هدف برسد. البته درست است، مگر اینکه گره های نامحدود زیادی با f(n) وجود داشته باشند. تنها راهی که ممکن است گره های نامحدود وجود داشته باشند :

الف – گره ای با فاکتور انشعاب نامحدود وجود دارد

ب – مسیری با هزینه مسیر متناهی اما تعداد زیادی گره های نامحدود در طول مسیر وجود داشته دارد.

از این رو، عبارت صحیح این است که A* روی گراف های متناهی محلی (گراف هایی با فاکتور انشعاب محدود : Locally Finite Graphs) کامل است، مشروط بر اینکه مقدار ثابت مثبت ¶ وجود داشته باشد که هر عملگر حداقل هزینه ای برابر با ¶ داشته باشد.

پیچیدگی A*

جستجوی A* بین تمام الگوریتم ها کامل، بهینه و کارآ بهینه است. متأسفانه بدین معنا نیست که A* پاسخی برای تمام نیازهای جستجو است. برای بیشتر مسائل، تعداد گره ها که در شمارنده هدف قرار دارند نسبت به طول راه حل مرتبه نمایی دارند. اگر خطا در تابع کشف کننده رشدی سریع تر از لگاریتم هزینه مسیر واقعی نداشته باشد، رشد نمایی اتفاق نخواهد افتاد. به زبان ریاضی، شرط برای رشد زیرنمایی عبارت زیر است :

که در آن h*(n) هزینه واقعی رسیدن از n به هدف است. در استفاده ی عملی، خطاها با هزینه مسیر متناسب هستند و سرانجام رشدنمایی هر کامپیوتری را تسخیر می کند. البته استفاده از یک کشف کنندگی خوب هنوز باعث صرفه جویی زیادی نسبت به جستجوی ناآگاهانه می شود.

A* به دلیل ذخیره ی تمام گره های تولید شده، معمولا قبل از اینکه دچار کمبود زمان شود، دچار کمبود فضا می شود.

نوشته شده توسط حسین | موضوع: سیستم های جستجو | لینک ثابت | | | |

[...] اگر f در طول هر مسیری از ریشه هرگز کاهش پیدا نکند، ما می توانیم ناحیه هایی (Contours) در فضای حالت بکشیم. شکل زیر مثالی را نشان می دهد. داخل ناحیه ای که 400 نام گذاری شده، تمام گره ها (n)f ای که کمتر یا مساوی 400 هستند به هم وصل شده و الی آخر.

پس به علت اینکه A* ، گره برگی کمترین f را بسط می دهد، می توانیم ببینیم که جستجوی A* از گره اولیه، گره هایی با هزینه f افزایشی را در نواحی متحدالمرکز اضافه می کند.

اگر f* را هزینه مسیر راه حل تعریف کنیم می توانی بگوییم که جستجوی A* :

• تمام گره ها با f(n)>f* را بسط می دهد.
• ممکن است تعدادی از گره هایی که به درستی بر روی ناحیه هدف برای f(n)=f* قرار دارند، قبل از اینکه گره هدف انتخاب شود، بسط دهد.

بهینگی A*

فرض کنید که G حالت هدف بهینه با هزینه مسیر f* باشد. ₂G نیز یک حالت هدف زیر بهینه باشد، که یک حالت هدف با هزینه مسیر g(G₂)>f* است. شرایطی را که فرض می کنیم این است که A*، G₂ را از صف انتخاب کرده است. زیرا G₂ یک حالت هدف است و جستجو را با یک راه حل زیر بهینه پایان می دهد.

حال نشان می دهیم ای غیر ممکن است :

یک گره همانند n را در نظر بگیرید که در حال حاضر گره ای برای روی مسیر بهینه به G است. (نباید چینن گره ای وجود داشته باشد مگر اینکه مسیر به طور کامل بسط داده شده باشد، در اینصورت الگوریتم G را برمی گرداند) چون h مجاز است داریم :

f*> f(n)

علاوه بر آن، اگر n برای بسط روی G₂ انتخاب نشده باشد، داریم :

f(n) > f(G₂)

با ترکیب این دو نتیجه می گیریم :

f* > f(G₂)

اما به این علت که G₂ یک حالت هدف است، داریم 0=h(G₂) ؛ از این رو f(G₂)=g(G₂) . بنابراین ما با استفاده از این فرضیات ثابت کردیم که f* > g(G₂) .

این نتیجه با این فرض که G₂  زیر بهینه است در تناقض خواهد بود. بنابراین باید توجه کنیم که A* هرگز یک هدف زیر بهینه را برای بسط انتخاب نمی کند. به علت اینکه فقط یک راه حل پس از انتخاب آن برای بسط برمی گردد، پس A* یک الگوریتم بهینه است.

مطالب مرتبط :

جستجوی آگاهانه (3)

جستجوی آگاهانه (2)

جستجوی آگاهانه (1)

نوشته شده توسط حسین | موضوع: سیستم های جستجو | لینک ثابت | | | |

هوش مصنوعی در ویکی پدیا

هوش مصنوعی در استنفورد

هوش مصنوعی در ویکی پدیا-انگلیسی (1)

هوش مصنوعی در ویکی پدیا-انگلیسی (2)

مقاله : هوش مصنوعی چیست؟ (PDF)

یکی دیگه از بازدیدکنندگان هم پرسیده بودند که اگر در جستجوی *A در یک سطح به چند گره مساوی رسیدیم چه کار کنیم؟ این هم جواب دکتر مینایی به این سوال :

One of the equal utilities is selected and the rest of tree expanded
from there. A* Algorithm is not clear to do what. However, you can go
and see the codes of A* in many open source versions of A* and see what
they have done.

یکی از گره ها رو انتخاب می کنیم و درخت رو گسترش می دهیم. البته الگوریتم کلی *A معلوم نمی کند که چه کار می کند و به code برنامه بستگی دارد. شما می تونید نمونه کدهای این جستجو رو توی اینترنت پیدا کنید و ببینید چه کار می کنند.

نوشته شده توسط حسین | موضوع: سیستم های جستجو | لینک ثابت | | | |

رفتار جستجوی A*

قبل از اینکه به اثبات کامل و بهینه بودن A* بپردازیم، بهتر است که تصویری از چگونگی کارکرد این جستجو نشان دهیم.

(فایل فلش این درخت را می توانید از اینجا دانلود کنید.)

اگر شما درخت جستجوی A* را امتحان کنید، متوجه یک پدیده خواهید شد. در طول هر مسیری از ریشه، هزینه f هرگز کاهش پیدا نمی کند. این یک حادثه نیست و تقریبا در مورد تمام کشف کنندگی های مجاز وجود دارد. این خاصیت برای کشف کنندگی، خاصیت یکنواختٌی (Monotonicity) گفته می شود.

اگر کشف کنندگی یک از آن استثناهایی باشد که یکنواخت نیست، ما می توانیم یک اصلاح جزیی ایجاد کنیم تا یکنواختی را به دست آورد.

دو گره n و n’ را در نظر می گیریم که n پدر n’ است. حال تصور کنید که g(n)=3 و h(n)=4 . سپس f(n) = g(n) + h(n) = 7 . بنابراین حداقل هزینه واقعی یک مسیر از n، 7 است. حال فرض کنید g(n’)=4 و h(n’)=2 در نتیجه f(n’) = g(n’) + h(n’) = 6 . این یک مثال از یک کشف کنندگی یکنواخت بود. با استفاده از این واقعیت که هر مسیری از n’ هم چنین مسیری از n است، می توانیم ببینیم که مقدار 6 بی معناست، زیرا ما قبلا هزینه واقعی، که حداقل 7 است را می دانستیم.

از این رو هر گره جدیدی که تولید می شود، باید کنترل کنیم که آیا هزینه f این گره از هزینه f پدرش کمتر است یا خیر. اگر کمتر باشد هزینه f پدر به جای فرزند می نشیند.

f(n’) = max(f(n), g(n) + h(n))

از این طریق، ما مقادیر گمراه کننده را که ممکن است با یک کشف کنندگی یکنوا پدیدار شوند، حذف می کنیم. این معادل سازی معادله Pathmax نامیده می شود. اگر آن را به کار ببریم، سپس f همیشه در طول هر مسیری از ریشه غیر کاهشی خواهد بود، مشروط بر اینکه h امکان پذیر باشد

مطالب مرتبط :

جستجوی آگاهانه (2)

جستجوی آگاهانه (1)

نوشته شده توسط حسین | موضوع: سیستم های جستجو | لینک ثابت | | | |

مثال :

امیدوارم نقشه رومانی رو یادتون نرفته باشه! یک تابع کشف کننده خوب برای مسائل مسیریابی، مانند این مسئله، تابع مسافت مستقیم تا هدف است.

h_SLD(n) : مسافت مستقیم بین n و مکان هدف.

فاصله مستقیم بین شهر های نقشه  و هدف :

با محاسبه مقادیر h_SLD در این مسئله، تابع کشف کنندگی حالت مطلوب را ارائه می دهد. زیرا یک مسیر A به B را معمولا در جهت درست هدایت می کند.

با بررسی درخت جستجوی حریصانه برای رسیدن به بخارست، به این نتیجه می رسیم که استراتژی ترجیح می دهد که راه بزرگتر را برای رسیدن به هدف پیدا کند(زیرا راهی که انتخاب کرده 32 کیلومتر طولانی تر از راه  Rimnicuاست.)، بدون اینکه نگرانی ای در مورد طولانی بودن آن داشته باشد. از این رو نام حریصانه برای این استراتژی کاملا مناسب است.

گرچه حرص یکی از هفت گناه کبیره است!! ولی الگوریتم های حریص اغلب کارآیی خوبی دارند. آن ها تمایل به یافتن راه حل های سریع دارند.

اگر چه همانطور که در این مثال نشان داده شد، آن ها همیشه راه حل بهینه را پیدا نمی کنند.

با یک تابع کشف کنندگی خوب، پیچیدگی زمان و فضای این جستجو می تواند کاهش اساسی پیدا کند. میزان کاهش به مسئله و کیفیت تابع h بستگی دارد.

ویژگی ها

از شناسایی های مشابه گریزان است.

بهینه نیست.

کامل نیست.

پیچیدگی فضای آن O(b^m) است. (m = حداکثر عمق فضای جستجو)

پیچیدگی زمان آن O(b^m) است.

·   حداقل سازی مجموع هزینه مسیر : جستجوی A*

جستجوی حریصانه هزینه تخمین زده شده h(n) به سمت هدف را به حداقل می رساند و به موجب آن، هزینه جستجو را به مقدار قابل ملاحظه ای کاهش می دهد. ولی نه بهینه و نه کامل است.

همچنین جستجو با هزینه یکسان، هزینه مسیر g(n) را به حداقل می رساند و علاوه بر آن بهینه و کامل نیز هست.

اگر بتوانیم دو استراتژی را (برای دست یابی به مزایای آن ها) ترکیب کنیم، بهترین کار را انجام داده ایم.

این کار به این صورت انجام می شود :

f(n) = g(n) + h(n)

در نتیجه :

هزینه تخمین زده شده ارزانترین راه حل از طریق n = f(n)

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

این استراتژی جستجو را جستجوی A* می گویند.

نوشته شده توسط حسین | موضوع: سیستم های جستجو | لینک ثابت | | | |

CSP (Constraint Satisfaction Problem)

نوعی خاصی از مسئله است که تعدادی از خواص ساختاری اضافی را، اضافه بر درخواست های پایه ای برای مسئله در حالت کلی، نیاز دارد. در یک CSP، حالات توسط مقادیر مجموعه ای از متغیر ها تعریف می شوند. همچنین آزمون هدف، مجموعه ای از محدودیت ها را به آن ها اختصاص می دهد که متغیر ها ملزم به پیروی از آن ها هستند.

روش های جستجوی آگاهانه

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

کشف کنندگی(Heuristic)

کلمه کشف کنندگی از فعل یونانی Heuriskein که به معنی پیدا کردن یا کشف کردن است، مشتق شده است.

برخی کشف کنندگی را متضاد حالت الگوریتمیک به کار می برند.

تکنیک های کشف کنندگی بر کاربرد های اولیه هوش مصنوعی حکم فرما بود. اولین آزمایشگاه سیستم های خبره، که توسط Ed Fergenbaum، Bruce Buchanan، Joshua Lederberg در دانشگاه استنفورد آغاز به کار کرد، پروژه برنامه نویسی کشف کننده (HPP) نامیده شد.

کشف کنندگی ها به عنوان راه تجربی مطرح می شوند که خبره دان ها از آن برای تولید راه حل های خوب بدون جستجوی بی نتیجه استفاده می کردند.

در حال حاضر، کشف کنندگی اغلب به عنوان یک صفت برای تکنیکی که کارایی حالت متوسط روی عمل حل مسئله را گسترش می دهد، به کار می رود. اما لزوما کارآیی بدترین حالت را گسترش نمی دهد. در حیطه ویژه از الگوریتم های جستجو، کشف کنندگی به یک تابع رجوع می کند که تخمینی از هزینه حل را به دست می آورد.

1- جستجوی بهترین (Best-First Search)

همانطور که می دانید، الگوریتم جستجوی عمومی با استفاده از صف ها دانش مسئله را به کار می برد. اگر با استفاده از یک تابع ارزیابی (Evaluation)، که توضیحاتی مبنی بر مطلوب بودن یا نبودن گره را در بر دارد، صف را مرتب کنیم، ابتدا گره ای که بهترین رتبه را در ارزیابی داشته باشد، بسط داده می شود. این استراتژی را جستجوی بهترین می گویند.

نام «جستجوی بهترین» نادرست است. زیرا اگر ما می توانستیم واقعا بهترین گره را در ابتدا بسط دهیم، دیگر نمی توانستیم نام این عمل را جستجو بگذاریم.

به دلیل وجود توابع ارزیابی گوناگون، خانواده بزرگی از الگوریتم های جستجوی بهترین وجود دارد. همان گونه که الگوریتم جستجوی بهترین نیز عضوی از خانواده بزرگ الگوریتم جستجوی عمومی است.

نوشته شده توسط حسین | موضوع: سیستم های جستجو | لینک ثابت | | | |

4-     جستجوی عمقی محدود شده (Depth-limited Search)

این استراتژی جستجو از به دام افتادن جستجوی عمقی جلوگیری می کند. این استراتژی عمق را محدود می کند. بنابراین اگر تا عمق معین شده، راه حل پیدا نشد، به شاخه های بالاتر باز می گردد.

مثال :در نقشه رومانی 20 شهر وجود دارد. بنابراین می توان گفت که اگر در شهر A است، باید مسیری با حداکثر طول 19 پیدا کند.

ولی مهم ترین عیب این استراتژی این است که اگر عمق تعیین شده آن قدر کوچک باشد که راه حل بهینه در آن عمق وجود نداشته باشد، جستجو ناقص می ماند.

5-     جستجوی عمیق کننده تکراری (Iterative Deepening Search)

فهمیدیم که دشوار ترین قسمت در طراحی جستجوی عمقی محدود شده، انتخاب محدوده خوب است. برای مثال اگر به نقشه رومانی خوب دقت کنیم، در می یابیم که بیشتری فاصله بین 2 شهر، 9 مرحله است. این تعداد را قطر فصای حالت می گویند.

جستجوی عمیق کننده تکراری (همانند جستجوی سطحی) ابتدا تمامی حالات عمق 0 را بررسی کرد و سپس به سراغ عمق 1 و الی آخر می رود.

بنابراین جستجوی عمیق کننده تکراری مزایای جستجوی سطحی و عمقی را با هم ترکیب می کند.

ویژگی های مثبت

·         کامل است.

·         بهینه است.

·         حافظه اندکی را مورد استفاده قرار می دهد.

این استراتژی از نظر زمانی همانند جستجوی عمقی است.

6-     جستجوی دو طرفه (Bidirectional Search)

در این نوع جستجو، بسط دادن هم از طرف حالت اولیه و هم از طرف حالت هدف صورت می گیرد. بدین صورت که از حالت هدف به سمت عقب و از حالت اولیه به سمت جلو حرکت می کند.

سخت ترین کار در این استراتژی، یافتن والد های حالت ها(در حرکت رو به عقب) است. مسئله دیگر این است که آیا این گره که ایجاد شده قبلا در درخت جستجوی طرف دیگر ظاهر شده یا نه.

جستجوی سطحی زمانی موفق می شود که شاخه ای از حالت اولیه، شاخه ای از حالت هدف را ملاقات کند. این جستجو در همه ي موارد قابل اجرا نیست.

حال به ارزیابی این شش استراتژی جستجو می پردازیم:

b = فاکتور انشعاب (در هر مرحله چند حالت جدید به وجود می آید؟)

d = عمق پاسخ

m = ماکزیمم عمق درخت جستجو

l = محدودیت عمق

نوشته شده توسط حسین | موضوع: سیستم های جستجو | لینک ثابت | | | |

استراتژی های جستجو

استراتژی های جستجو با چهار ویژگی زیر سنجیده می شوند :

·         کامل بودن(Completeness) : در صورت وجود راه حل، آیا استراتژی می تواند آن را پیدا کند؟

·         پیچیدگی زمان (Time Complexity) : چقدر طول می کشد که یک راه حل پیدا کند؟

·         پیچیدگی فضا (Space Complexity) : چه میزان حافظه باید برای ارائه جستجو صرف شود؟

·         بهینه سازی (Optimality) : آیا استراتژی راه حلی با کیفیت بالا را می تواند پیدا کند؟(زمانی که راه حل های متفاوتی وجود دارند.)

استراتژی های جستجو به دو نوع آگاهانه(Informed) و ناآگاهانه(Uninformed) تقسیم می شوند.

در ابتدا چند استراتژی جستجوی ناآگاهانه را مورد بررسی قرار می دهیم.

1-     جستجوی سطحی (Breadth-first Search)

در این نوع جستجو ابتدا گره ریشه گسترش می یابد، سپس تمام گره هایی که توسط ریشه تولید شده اند، خودشان گسترش می یابند و سپس مولد های آن ها و این عمل تکرار می شود.

ویژگی های مثبت :

• اگر راه حلی وجود داشته باشد، جستجوی سطحی حتما آن را می یابد.
• اگر چندین راه حل وجود داشته باشند، جستجوی سطحی ابتدا کم عمق ترین وضعیت هدف را پیدا می کند.

 ویژگی های منفی :

• فضای زیادی را اشغال می کند.
• زمان زیادی صرف می کند.

 ویژگی های منفی به این دلیل به وجود می آیند که این استراتژی تمامی راه ها را امتحان می کند.

برای مثال هنگامی که بخواهد به عمق 12 گره برسد و هر گره 1 میلی ثانیه زمان ببرد، بر فرض اینکه در هر مرحله 10 گره جدید ایجاد شود، به 35 سال زمان نیاز دارد!(10¹²)

2-     جستجو با هزینه یکسان(Uniform cost Search)

همانطور که مشاهده کردید ، جستجوی سطحی، کم عمق ترین حالت هدف را پیدا می کند. اما همیشه کم هزینه ترین حالت را پیدا نمی کند.

در مواقعی که هزینه مسیر برای گره کم عمق، زیاد باشد، جستجوی سطحی کم هزینه ترین حالت را پیدا نمی کند.

جستجو با هزینه یکسان، استراتژی جستجوی سطحی را توسط گسترش کم هزینه ترین گره (که توسط تابع هزینه مسیر g اندازه گیری می شود)، بهبود می بخشد.

زمانی که شرایط عمومی برقرار باشد، اولین راه حل پاسخ، ارزانترین راه نیز هست. زیرا اگر مسیر ارزانتری وجود داشته باشد، که راه حل نیز باشد، زود تر بسط داده شده است.(زیرا ابتدا کم هزینه ترین گره گسترش می یابد.)

جستجو با هزینه یکسان، کم هزینه ترین راه حل را پیدا می کند. در نتیجه نباید هزینه مسیر با ادامه مسیر کاهش پیدا کند. هزینه مسیر یک گره، مجموع عملگر هایی است که مسیر را می سازند. بنابراین برای جستجو با هزینه یکسان هیچ عملگری نباید ارزش منفی داشته باشد.

ولی بعضی از عملگرها هزینه منفی دارند. بنابراین یک جستجوی خسته کننده از تمام گره ها باید صورت گیرد تا راه حل بهینه پیدا شود. زیرا ما هرگز نمی دانیم که چه زمانی یک مسیر (بدون توجه به طول و هزینه) به مرحله ای با هزینه منفی بالا وارد شده و به بهترین مسیر تبدیل می شود.(مانند مسئله 8 وزیر)

3-     جستجوی عمقی (Depth-first Search)

جستجوی عمقی همیشه یکی از پایین ترین گره ها را بسط می دهد. فقط زمانی که جستجو به بن بست می رسد، برگشت داده می شود و به سراغ گره هایی در سطوح کم عمق تر می رود.

ویژگی های مثبت :

• جستجوی عمقی نیاز به حافظه نسبتا کمی دارد.(جستجوی عمقی به 12 کیلوبایت در عمق 12 دارد. بر خلاف جستجوی سطحی که نیاز به 111 ترابایت دارد!)
• جستجوی عمقی در مسائلی که راه حل های زیادی دارند، بسیار سریع تر از جستجوی سطحی عمل می کند.

ویژگی های منفی :

• جستجو همیشه به سمت پایین حرحت می کند و به بالا باز نمی گردد.(مگر در مواقعی که به بن بست می رسد.) بنابراین اگر راه حل کوتاه تری نیز وجود داشته باشد، نمی تواند آن را پیدا کند.(جستجو کامل نیست.)
• ممکن است راه حلی پیدا کند که طولانی تر از راه حل بهینه باشد.(جستجو بهینه نیست.)

۳ روش جستجوی ناآگاهانه دیگه مونده که می مونه برای دفعه بعد. ولی جون هر کی دوست دارید نظر بذارین. آخه من چه گناهی کردم؟ نه بازدید ها زیاده و نه نظر ها.

نوشته شده توسط حسین | موضوع: سیستم های جستجو | لینک ثابت | | | |

ساختار داده برای درخت های جستجو

یک گره، یک ساختار داده با پنج عنصر است:

·         وضعیتی که گره در فضای حالت دارد.

·         گره والد(گره ای که در جستجو، گره جدیدی را تولید کند.)

·         عملگری که برای تولید گره به کار رفته است.

·         تعداد گره های مسیر از ریشه تا گره مورد نظر (عمق گره)

·         هزینه مسیر، از حالت اولیه تا گره.

یک گره با یک حالت متفاوت است. زیرا :

·         یک گره، یک ساختار داده نگهدارنده است که برای بازنمایی درخت جستجو در یک مسئله ویژه با الگوریتم ویژه است.

·         یک حالت بیانگر پیکره بندی دنیا است.

در نتیجه گره ها عمق و والد دارند ولی حالت ها چنین ویژگی هایی ندارند.

برای مثال امکان دارد یک حالت توسط دو دنباله مختلف از عملیات تولید بشود. (یعنی گره های متفاوت، حالت های مشابهی پیدا می کنند.)

سپس باید گره هایی که قرار است توسعه یابند، جمع آوری شوند. این مجموعه را Fringe یا Frontier می گویند.

استراتژی جستجو باید گره بعدی را که قرار است گسترش یابد، از میان این مجموعه، انتخاب کند. برای انجام این عمل می بایست یک تابع تمامی عناصر مجموعه را بررسی کند. بنابراین فرض می گیریم که عناصر به صورت یک صف پیاده سازی می شوند. مجموعه اعمالی که باید روی عناصر انجام شود به صورت زیر است (برای فهمیدن مطالب زیر باید کمی برنامه نویسی کار کرده باشید.):

·         Make-Queue(Elements) : یک صف با عناصر داده شده تشکیل می دهد.

·         Check-Empty(Queue) : اگر صف خالی است، "شکست"(Failure) را باز می گرداند.

·         Remove-Front(Queue) : عنصر جلویی صف را حذف کرده و آن را باز می گرداند.

·         Queuing-Fn(Elements, Queue) : مجموعه ای از عناصر را به داخل صف اضافه می کند.

مجموع این توابع را تابع صف می نامند. تابع های متفاوت، گونه های متفاوتی از الگوریتم جستجو را تولید می کنند.

نوشته شده توسط حسین | موضوع: سیستم های جستجو | لینک ثابت | | | |

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

تا کنون به تعریف یک مسئله و تشخیص راه حل آن پرداختیم. حال به چگونگی یافتن یک راه حل توسط جستجو می پردازیم.

تولید دنباله های عمل

برای حل مسئله رفتن از آراد به بخارست، حالت اول آراد است. قدم اول، کنترل حالت برای تست هدف است. واضح است که این حالت هدف نیست، اما باید کنترل شود. زیرا امکان دارد مسئله «شروع در آراد، رسیدن به آراد» باشد. بنابرین تست هدف بسیار مهم است.

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

برای وضعیت، سه حالت جدید وجود دارد : {Sibiu – Timisoara - Zerind} . هنگامی که فقط یک امکان وجود داشته باشد ما مجبوریم که همان را ادامه دهیم. اما هنگامی که چند حالت وجود دارد، باید یکی را انتخاب کنیم و دوباره فرآیند گسترش حالت را انجام دهیم. سپس حالت های جدید را کنترل کرده و نتایج را ذخیره می کند. سپس یکی دیگر از حالت های ایجاد شده در مرحله قبل (والد) رفته و همین اعمال را با آن نیز انجام می دهیم.

سپس استراتژی جستجو با مقایسه نتایج تعیین می کند که کدام یکی از مسیر ها باید ادامه داده شوند.

ریشه یک درخت جستجو، یک گره جستجو است که با حالت آغازین مطابقت دارد.

گره های برگی درخت، مطابق با حالاتی هستند که درخت دارای فرزندی نباشد. که این حالت به دو دلیل ایجاد می شود:

1-      درخت گسترش پیدا نکرده است.

2-      فرآیند گسترش انجام شده ولی مجموعه تهی باز گردانده است.(حالت جدیدی به وجود نیاورده است.)

در هر مرحله، الگوریتم جستجو، یک گره برگی  را برای گسترش انتخاب می کند.

در یک حالت تعداد نامحدودی مسیر وجود دارد. برای مثال شاخه Arad-Sibiu-Arad می تواند به Arad-Sibiu-Arad-Sibiu-Arad ادامه پیدا کند و مدام گسترش یابد. یک الگوریتم جستجوی خوب از چنین حالت هایی اجتناب می ورزد.

نوشته شده توسط حسین | موضوع: سیستم های جستجو | لینک ثابت | | | |

ورودی های مسئله

هر مسئله شامل اطلاعاتی است که عامل از آن ها برای تصمیم گیری در مورد انتخاب عمل مناسب برای رسیدن به هدف استفاده می کند.

عناصر اولیه تعریف یک مسئله، وضعیت ها و اعمال هستند. بنابراین اطلاعات مسئله شامل موارد زیر است:

·         وضعیت آغازین(Initial state)

·         مجموعه اعمالی که برای عامل قابل دسترسی هستند.(عامل می تواند آن ها را انجام دهد.)

عملگر(Operator) : بر انجام یک عمل دلالت می کند.

عامل پس از انجام یک عمل در یک وضعیت خاص، در وضعیت دیگری قرار می گیرد.

تابع S(successor) : در وضعیت ویژه ي X، S(x) برابر است با مجموعه ای از وضعیت های قابل دسترسی با انجام هر عمل.

به مجموع این موارد فضای وضعیت (Space state) مسئله را تعریف می کنند.

مسیر : یک مسیر در فضای وضعیت، دنباله ای از اعمال است که از یک وضعیت به وضعیت دیگر می رود.

·         تست هدف(Goal test) : عامل باید بداند که وضعیتی که در آن قرار دارد، وضعیت هدف است یا خیر. که این عمل نیازمند یک تعریف از وضعیت هدف است.

·         تابع هزینه – مسیر : تابعی است که برای هر مسیر، هزینه ای را در نظر می گیرد. هزینه یک مسیر، مجموع هزینه های اعمال مربوط به مسیر است. تابع هزینه مسیر اغلب با حرف G مشخص می شود.

اندازه گیری کارایی حل مسئله

کارایی یک جستجو ، حداقل از سه طریق می تواند اندازه گیری شود.

·         آیا این جستجو را حلی پیدا می کند؟

·         آیا راه حلی مناسبی است؟(هزینه مسیر آن کم است؟)

·         هزینه جستجو از نظر زمانی و حافظه مورد نیاز برای یافتن راه حل چیست؟

(هزینه کل = هزینه جستجو+هزینه مسیر)

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

برای یافتن راه حل یک مسئله فقط باید به یک یا چند عمل مورد نظر بپردازیم. برای مثال برای رفتن از آراد به بخارست، عمل مورد نظر، رفتن از آراد به بخارست در کمترین زمان است. در حالی که این کار می تواند با کار های دیگری همراه باشد. مانند روشن بودن ضبط صوت، بنزین زدن، اطاعت از قوانین راهنمایی و رانندگی و... .

مطالب مرتبط:

حل مسئله (1)

حل مسئله (2)

نوشته شده توسط حسین | موضوع: سیستم های جستجو | لینک ثابت | | | |

انواع مسأله

در این بخش عملکرد یک جاروبرقی هوشمند را مورد بررسی قرار می دهیم.

فرض می کنیم که دو اتاق وجود دارد که هر کدام از آن ها ممکن است شامل خاک باشد یا نباشد و عامل ممکن است در محیط 1 یا 2 باشد. عامل می تواند مستقیم برود و یا به چپ یا راست بپیچد. بنابراین هشت حالت ممکن، به عنوان عمل بعدی، وجود دارد.

1-      جارو در محیط 1 – هر دو محیط خاکی

2-      جارو در محیط 1 – محیط 1 خاکی

3-      جارو در محیط 1 – محیط 2 خاکی

4-      جارو در محیط 1 – هیچکدام از محیط ها خاکی نیست

5-      جارو در محیط 2 – هر دو محیط خاکی

6-      جارو در محیط 2 – محیط 1 خاکی

7-      جارو در محیط 2 – محیط 2 خاکی

8-      جارو در محیط 2 – هیچکدام از محیط ها خاکی نیست

·         ابتدا تصور کنید که حسگر های عامل به او اطلاعات کافی می دهند.(دنیا قابل دسترسی است.) و همچنین عامل می داند هر کدام از اعمالش چه تغییری در محیط ایجاد می کنند و سپس می تواند محاسبه کند با کدام وضعیت پس از انجام عمل رو به رو خواهد شد. این ساده ترین حالت مسئله است که به آن مسئله تک حالته می گویند.

·         حالا تصور کنید که عامل تمام اثرهای عمل هایش را می داند، اما دسترسی به محیط محدود است. برای مثال، عامل هیچ حسگری ندارد. در این حالت فقط می داند که وضعیت اولیه اش یکی از اعضای مجموعه (1،2،3،4،5،6،7،8) است. ممکن است فکر کنید که وضعیت عامل ناامید کننده است! اما در حقیقت اینقدر ها هم که به نظر می آید ناگوار نیست. زیرا عامل می داند که هر کدام از اعمالش چه اثری دارند. برای مثال می تواند محاسبه کند که عمل راست موجب می شود تا در یکی از حالات (2،4،6،8) باشد. بنابراین می تواند با انتخاب یک دنباله عملیاتی، به هدف برسد. به طور خلاصه هنگامی که محیط تماما قابل دسترسی نیست، عامل باید در مورد مجموعه حالت هایی که ممکن است هدف برسد، استدلال کند. به این نوع از مسئله مسئله چند حالته می گویند.

·         اگر عامل اثر اعمال خودش را نادیده بگیرد می تواند به مشکلات دیگری دچار شود. برای مثال تصور کنید که محیط غیر قطعی باشد از این رو باید از قانون مورفی(Murphy) تبعیت کند.

برای مثال عامل می داند که در یکی از وضعیت های 1 یا 3 است. با انجام هر عمل در یک حالت دیگر قرار می گیرد که امکان دارد آن را به هدف برساند و یا با شکست مواجه شود. در چنین مواردی عامل تمام درخت عملیات را محاسبه کند. به طور کلی هر شاخه درخت با یک امکان احتمالی که از آن ناشی می شود، بررسی می شود. به همین علت به آن مسئله احتمالی می گویند.

·         حال تصور کنید که عامل هیچ اطلاعی در مورد اثرات اعمالش و اینکه در کجا قرار دارد، ندارد.(بدبخت تر از این عامل سراغ ندارید!؟) مانند کسی که در یک کشور غریب و بدون هیچ نقشه ای گم شده است. در ای حالت عامل باید تجربه کند و به تدریج کشف کند که چه عملی باید انجام شود و چه وضعیت هایی وجود دارند. این روش یک نوع جستجو است که بر خلاف جستجو در دنیای فرضی، می تواند عامل را با خطرات جدی مواجه کند. به مسائلی از این قبیل، مسئله اکتشافی می گویند.

مطالب مرتبط:

حل مسئله (۱)

نوشته شده توسط حسین | موضوع: سیستم های جستجو | لینک ثابت | | | |

خب تا الان در مورد عامل ها و محیط ها نوشتم. در ادامه در مورد حل مسائل توسط جستجو می نویسم.

عامل ها حل مساله

قبلا گفتم که عملیات ها به گونه ای ساده سازی می شوند که عامل قادر باشد تا هدفی را انتخاب کرده و به آن برسد. مانند قبل از یک مثال برای توضیح مطالب استفاده می کنم.

عامل ما در شهر آراد در کشور رومانی در حال گذراندن تعطیلات است. عامل بلیطی برای روز بعد از بخارست دارد. بلیط غیر قابل استرداد است، ویزای عامل در حال انقضا است و از پس فردا تا 6 هفته بعد جای خالی وجود ندارد.

در این صورت معیار های کارآیی عامل ، شامل عوامل زیادی علاوه بر قیمت بلیط و نامطلوب بودن دستگیری یا اخراج از کشور است. برای مثال، می خواهد پوستش برنزه تر شود! و نظرها را به خود جلب کند.(احتمالا این عامل، زن است!!)

تمامی این عوامل ممکن است که آرایه وسیعی از عملیات را پیشنهاد کنند. عملیاتی که منجر به شکست رفتن به بخارست می شوند می توانند بدون در نظر گرفته شدن، رد شوند.

فوموله سازی هدف، که مبتنی بر شرایط جاری است، اولین قدم در حل مسأله است.

اکنون عامل هدف رفتن به بخارست را انتخاب کرده است. حال می خواهد جاده مورد نظر را برای رفتن از بخارست انتخاب کند. 3 جاده وجود دارد که یکی به طرف Sibiu، یکی به طرف Timisoara و دیگری به سمت Zerind می رود. هیچ کدام از اینها به بخارست متصل نیستند و عامل به دلیل ندانستن نقشه راه های رومانی، نمی داند که کدام جاده را باید انتخاب کند.(عامل نمی داند کدام راه بهتر است.) در اینجا اگر عامل اطلاعات دیگری نداشته باشد، متوقف خواهد شد و بهترین کار برای ادامه راه، انتخاب یکی از راه ها به صورت تصادفی است.

تصور می کنیم که عامل نقشه ای از راه های کشور رومانی در اختیار دارد. هدف از نقشه تولید اطلاعاتی در مورد حالت هایی است که  عامل می تواند توسط آن خودش را به بخارست برساند. عامل توسط آزمایش مراحل ممکن عملیات، که منتهی به حالت شناخته شده(در اینجا بخارست)، و سپس انتخاب بهترین آن ها، قادر به تصمیم گیری خواهد بود. این پردازش برای یافتن راه حل مسأله را جستجو (Search) می نامند.

یک عامل با عملیاتش و حالتی که در آن وجود دارد، می تواند با مقادیر مختلف دانش ارتباط پیدا کند.

فرموله سازی مسأله

چهارنوع اساسی از مسائل وجود دارند:

·         مسائل تک حالته (Single-state)

·         مسائل چند حالته (Multi-State)

·         مسائل احتمالی (Contingency)

·         مسائل اکتشافی (Exploration)

نوشته شده توسط حسین | موضوع: سیستم های جستجو | لینک ثابت | | | |

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

1 - State Space Search ( جستجوی فضا حالت )

2 - Problem Reduction ( کاهش مساله )

3 - Games

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

در روش فضا حالت ما یک مساله داریم که سیستم هوشمند آن را دریافت می کند و فضای حالت آن مساله را می سازد و در فضای حالت آن جستجو می کند و جواب یا جواب های مساله را پیدا کرده و بر می گرداند.

فضای حالت مساله چیست ؟ فضای حالت در برگیرنده تمام حالت هایی است که ممکن است جواب مساله نیز در آن باشد.

برای مثال فضای حالت حرکت موس شما تمام صفحه نمایش است ولی جواب مساله آنجایی است که شما کلیک می کنید.

حال می خواهیم بدانیم فضای حالت از چه ساختاری تشکیل شده است:

ساختار فضای حالت گرافی است که از نودها تشکیل شده است.

مثال : فرض کنید که روبات x می خواهد به خانه شماره 2 برود.

روبات از خانه های 1 و 5 و 4 می تواند وارد شود و هدف این است که به خانه 2 برود.گراف فضا حالت بدین شکل می شود.

s نقطه شروع و G نقطه پایان می باشد. فضای حالت مساله شامل جواب ها و همینطور آنهایی که جواب نیستند نیز هست. نودهای این گراف متناظر با حالات مساله است و لبه ها عملگر تغییر حالت مساله هستند و هدف ما پیداکردن راه های S به G است.

جواب ها از نوع مسیر ( Path ) هستند. برای مثال داریم:

S –> 4 –> 3 –> 2

زمانی که برای یک حالت حالت بعدی وجود نداشته باشد به آن بسط ناپذیر می گویند . نود های پایانی یا بسط ناپذیرند یا جواب مساله هستند. در اصل ما دنبال جوابی هستیم که یک سر آن S است و طرف دیگر آن G می باشد.

سوالی دیگر که در اینجا مطرح می شود این است که تمام گراف را جستجو کنیم یا بخشی از آن را و چگونه؟

نوشته شده توسط حسین | موضوع: سیستم های جستجو | لینک ثابت | | | |