[...] اگر 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)

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