استفاده از الگوریتم جستجوی پرتو برای حل مسائل برنامه ریزی هوش مصنوعی

با توجه به اینکه اکثر مسائل برنامه ریزی هوش مصنوعی دارای فضای جستجوی بسیار بزرگی هستند بنابراین راه حل (طرح) پیدا شده به احتمال زیاد نمی تواند دقیق بوده و تقریبی خواهد بود. هدف از حل چنین مسائلی، یافتن یک طرح (تقریبا) بهینه است که از حالت ابتدایی شروع شده و به حالت هدف ختم می شود با این شرط که تعداد عمل های بکار رفته کمینه باشد . الگوریتم جستجوی پرتو یکی از مشهورترین الگوریتم های مسیریابی گراف هست که مسیرهای بهینه را در زمان کمی پیدا می کند. در این مقاله، از الگوریتم جستجوی پرتو استفاده کرده تا طرح های بهینه را در مسائل برنامه ریزی که با زبان رسمی تبدیل گراف مدل شده اند در زمان کمتری پیدا کنیم. برای ارزیابی کارایی الگوریتم جستجوی پرتو، آن را در ابزار GROOVE – از ابزارهای وارسی مدل مبتنی بر زبان تبدیل گراف - پیاده سازی کرده و نتایج آن را با نتایج الگوریتم های جستجوی اول-عمق و اول-سطح مقایسه می کنیم .

کلیدواژه ها:

مسائل برنامه ریزی ، طرح ، الگوریتم جستجوی پرتو ، تبدیل گراف