الگوریتم برنامه ریزی جست وجوی پیشرو در فضای حالت
الگوریتم برنامه ریزی جست وجوی پیشرو در فضای حالت
توصیف مسئله ی برنامه ریزی، اینگونه یک مسئله جست وجو را تعریف می کند: میتوانیم فضای حالت را از حالت شروع برای یافتن هدف، جست وجو کنیم. یکی از امتیازات جالب نمایش اعلانی شِمای حالت این است که با شروع از هدف می توان به عقب جست وجو کرد، تا حالت شروع پیدا شود.
جست وجوی پیشرو در فضای حالت
اکنون که دیدید مسئله برنامه ریزی چگونه به مسئله جست وجو تبدیل می شود، می توان مسئله های برنامه ریزی را با استفاده از هر یک از الگوریتم های ابتکاری یا الگوریتم جست وجوی محلی که تاکنون بررسی کرده ایم (در پست های قبلی این بخش دیدید) ،حل کرد البته به شرطی که فعالیت های مورد استفاده برای رسیدن به هدف، نگهداری شوند.
از روزهای اولیه پژوهش درباره برنامه ریزی (در حدود 1961) تا 1998 ،فرض شد که جست وجوی پیشرو در فضای حالت، در عمل بسیار ناکارآمد بود. پی بردن به علت آن دشوار نیست.
اولا، جست وجوی پیشرو، مستعد بررسی فعالیت های نامرتبط است. خرید کتاب AI: A Modern Approach را بصورت اینترنتی در نظر بگیرید. فرض کنید یک شمای فعالیت به نام Buy(isbn) با اثر Own(isbn) وجود دارد. ثانیا مسئله های برنامه ریزی غالبا فضاهای حالت بزرگی دارند.
مسئله ی حمل بار هوایی با 10 فرودگاه را در نظر بگیررید، که در آن هر فرودگاه 5 هواپیما و 20 قطعه بار دارد. هدف، انتقال تمام بارها از فرودگاه A به فرودگاه B است. راه حل ساده ای برای این مسئله وجود دارد: 20 قطعه بار را در یکی از هواپیماها در A بارگیری کنید، این هواپیما را به B پرواز دهید و بار را تخلیه کنید. یافتن راه حل میتواند دشوار باشد، زیرا میانگین ضریب انشعاب زیاد است. هر یک از 50 هواپیما میتواند به 9 فرودگاه دیگر پرواز کند و هر 200 بسته ی بار میتواند تخلیه شود (اگر بارگیری شده باشد) یا به هر هواپیمایی به فرودگاه بارگیری شود (اگر تخلیه شده باشد). بنابراین در هر حالت، حداقل 450 فعالیت وجود دارد (وقتی تمام بسته ها در فرودگاه های بدون هواپیما باشند) . بطور میانگین فرض میکنیم در هر حالت در حدود 2000 فعالیت ممکن وجود دارد و در نتیجه گراف جست وجو تا عمق جواب بدیهی در حدود 200041 گره دارد.
روشن است که حتی این نمونه ی نسبتا کوچک از مسئله، بدون یک ابتکار دقیق ناامیدکننده است. گرچه بسیاری از کاربردهای برنامه ریزی در دنیای واقعی، به ابتکارات خاص دامنه متکی هستند، نتیجه میشود ابتکارات قوی مستقل از دامنه میتوانند بطور خودکار به دست آیند، به این ترتیب جست وجوی پیشرو امکان پذیر می شود.
