عکس های تیم مارفتار جستجوی 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 امکان پذیر باشد
مطالب مرتبط :
