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



روش جستجوی*A تلفیقی از روش جستجوی هزینه یکنواخت ( UCS ) و روش جستجوی



حریصانه ( Greedy ) است. در جستجوی هزینه یکنواخت بر اساس هزینه تا گره فعلی ، کم هزینه ترین گره را انتخاب کرده و گسترش می دهیم. جستجوی هزینه یکنواخت بهینه است ، یعنی جواب بهینه مسئله را پیدا می کند ولی در مقابل بسیاز زمانبر است. جستجوی حریصانه نیز بر اساس هزینه تا مقصد ، کم هزینه ترین گره را برای گسترش انتخاب می کند. یافتن جواب با استفاده از جستجوی حریصانه به سرعت انجام می گیرد. ولی این روش نیز از مشکلاتی همچون بهینه نبودن جواب رنج می برد. روش جستجوی *A ، سرعت روش حریصانه در رسیدن به جواب و بیهنگی روش هزینه یکنواخت در پیدا کردن جواب را باهم ترکیب کرده و به جستجوی هدف خود می پردازد.

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

هیوریستیک در روش *A هرینه قابل پرداخت از نقطه فعلی تا نقطه هدف را تخمین می زند. با این توصیف هیوریستیک قابل قبول را چنین تعریف می کنیم : هیوریستیکی قابل قبول ( admissible ) است که هزینه تخمینی آن از نقطه فعلی تا نقطه هدف ، از هزینه واقعی قابل پرداخت از نقطه فعلی تا نقطه هدف کمتر باشد. هیوریستیکی که این شرط را برآورده نکند ، هیوریستیک غیرقابل قبول ( inadmissible ) می نامند.

با توجه به مطالب فوق چنین بیان می کنیم که هزینه هر گره در روش جستجوی *A با استفاده از فرمول زیر محاسبه می شود : F = G + H که در آن F هزینه کل گره ، G هزینه تا گره فعلی و H هزینه تخمینی تا گره هدف را نشان می دهد. در جستجوی *A گره بعدی جهت گسترش گره ای است که کمترین هزینه F را در میان گره های گسترش نیافته دیگر داشته باشد. شبه کد زیر نحوه اجرای الگوریتم *A را نشان می دهد:

 

1. نقطه شروع را به صف fringe اضافه کن
2. مراحل زیر را تکرار کن
     1. گره موجود در سر صف fringe را انتخاب کن.
     2. آن را از صف fringe حذف کرده و فلگ آن را جهت بررسی نکردن دوباره آن ، ست کن
     3. به ازای هر هشت همسایه مربع برداشته شده از صف ( نام مربع را parent فرض کنید ) انجام بده :
          • در صورتی که فلگ مربع ست شده باشد آن را نادیده بگیر ، در غیر اینصورت به مرحله بعد برو
          • اگر این مربع در صف fringe نباشد ، آن را به صف اضافه کن ، مربع parent را پدر مربع اضافه شده به صف قرار بده و هزینه های F ، G و H مربع را محاسبه کن
          • اگر این مربع از قبل در صف باشد ، هزینه G آن را با استفاده از مربع parent محاسبه کن. در صورتی که این هزینه کمتر از هزینه G این مربع در حال حاضر باشد ، مربع parent را ، پدر مربع قرار بده.
     4. صف fringe را به ترتیب صعودی هزینه ها مرتب کن
     5. توقف کن در صورتی که
          • مربع مقصد به صف fringe اضافه شود که در این صورت مسیر پیدا شده است یا
          • صف fringe خالی باشد ( مسیری از مبدا به مقصد وجود ندارد )
 3 . مسیر را ذخیره کن. با حرکت عقبگرد از نقطه پایانی و با استفاده از مربع های پدر هر مربع ، تا رسیدن به مربع شروع ، مربع ها را پیمایش کن.