گراف های برنامه ریزی برای تخمین ابتکاری

گراف های برنامه ریزی برای تخمین ابتکاری

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

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

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

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

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

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

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

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