موضوع مقاله: برنامه‌نویسی مجموعه جواب | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # برنامه‌نویسی مجموعه جواب | مقدمه: برنامه‌نویسی مجموعه جواب با کوته‌نوشت ASP نوعی برنامه‌نویسی اعلانی است که به سمت مسائل جستجوی مشکل (در اصل ان‌پی سخت) گرایش دارد. | ## بخش 1: برنامه‌نویسی مجموعه جواب | در ASP مسائل جستجو به محاسبه مدل‌های پایدار کاهش می‌یابد، و از حل‌کننده‌های مجموعه جواب (برنامه‌های تولیدکننده مدل‌های پایدار) برای انجام جستجو استفاده می‌شود. فرایند محاسباتی استفاده شده در طراحی بسیاری از حل‌کننده‌های مجموعه جواب، نوعی بهبود الگوریتم DPLL هستند، و در اصل همیشه خاتمه می‌یابند (برخلاف ارزیابی پرسمان در پرولوگ، که می‌تواند منجر به حلقه بی‌پایان شود). در مفهوم عمومی‌تر، ASP شامل همه کاربردهای مجموعه جواب در نمایش دانش است، as PDF و از ارزیابی پرسمان شبه-پرولوگ برای حل مسائلی که در این کاربردها بروز می‌کند، استفاده می‌کند. استفاده از حل‌کننده‌های مجموعه جواب برای جستجو توسط مارک و تروشسینسکی به عنوان یک پارادایم برنامه‌نویسی، اولین بار در مقاله ای که چشم‌انداز ۲۵ ساله دربارهٔ پارادایم برنامه‌نویسی منطقی در سال ۱۹۹۹ منتشر شد، و در [Niemelä 1999] شناسایی شد. در واقع اصطلاح‌شناسی جدید «مجموعه جواب» به جای «مدل پایدار» اولین بار توسط لیفشیتس In در یک مقاله که نمایش دهنده مجلدهای پیش‌نگرانه در مقاله مارک-تروشچینسکی بود، پیشنهاد شد. برای مثال، قاعده گزینه {p,q,r}.می‌گوید: به صورت دلخواه انتخاب کنید که کدامیک از اتم‌های در مدل پایدار شامل بشود. برنامه Lparse ای که شامل این قاعده انتخاب است و هیچ قاعده دیگری ندارد، به تعداد ۸ عدد مدل پایدار دارد-که زیرمجموعه‌های دلخواه هستند. as Postscript برای مثال، قاعده گزینه بالا را می‌توان به صورت نوع مختصری برای عطف سه فرمول «اصل طرد ثالث» در نظر گرفت: زبان Lparse به ما امکان نوشتن قواعد گزینه «محدودشده» را نیز می‌دهد، مثل 1{p,q,r}2.این قاعده می‌گوید: حداقل یکی از اتم‌های ، اما نه بیشتر از ۲ تا اتم را انتخاب کنید. معنای این قاعده تحت معناشناسی مدل پایدار توسط فرمول گزاره‌ای زیر نمایش می‌یابد: محدوده‌های کاردینالیتی (تعدادی)، در بدنه یک قاعده هم قابل استفاده اند، برای مثال :- 2{p,q,r}.اگر این محدودیت را به برنامه Lparse اضافه کنیم، مدل‌های پایداری که حداقل دو اتم را حذف می‌کند. معنی این قاعده را می‌توان توسط توسط فرمول گزاره‌ای زیر نمایش داد: در Lparse از متغیرها (که مثل پرولوگ بزرگ هستند) برای مختصرنویسی مجموعه قاعده‌هایی استفاده می‌شود که از الگوی مشابهی پیروی می‌کنند، همچنین برای مختصرنویسی مجموعه اتم‌ها در داخل یک قاعده مشابه نیز استفاده می‌شود. | ## بخش 2: برنامه‌نویسی مجموعه جواب | یک محدوده یک میانبر نمادین است که در اصل برای تعریف دامنه‌های عددی، به روش سازگار، از آن استفاده می‌شود. ما می‌خواهیم از ASP استفاده کنیم تا یک رنگ‌آمیزی تایی از یک گراف داده شده را پیدا کنیم (یا تعیین کنیم که چنین رنگ‌آمیزی وجود ندارد). محدودیت موجود در خط ۳ از انتساب رنگ مشابه به راس‌های و ، موقعی که یک یال آن‌ها را به هم متصل کند، جلوگیری می‌کند. برنامه موجود در این مثال نمایش‌دهنده سازمان «تولید-و-آزمون» است که معمولاً در برنامه‌های ASP ساده یافت می‌شود. قاعده گزینه یک مجموعه از «جواب‌های بالقوه» را تعریف می‌کند- که یک فرامجموعه ساده از مجموعه جواب‌ها برای مسئله جستجوی معین است. در ادامه، یک محدودیت آمده‌است، که همه جواب‌های بالقوه که قابل قبول نیستند را حذف می‌کند. با این حال، فرایند جستجوی استفاده شده در smodels و دیگر حل‌کننده‌های مجموعه جواب براساس سعی و خطا نیستند. دور همیلتونی یک دور همیلتونی در یک گراف جهت‌دار یک دور است که از هر راس گراف دقیقاً یکبار عبور می‌کند. برنامه Lparse زیر را می‌توان برای یافتن یک دور همیلتونی در یک گراف جهت‌دار معین استفاده کرد (اگر موجود باشد)؛ فرض می‌کنیم که ۰ یکی از راس‌ها باشد. آخرین آن‌ها از گزارهٔ کمکی ( قابل دستیابی از ۰ است) استفاده می‌کند تا راس‌هایی که این شرط را برآورده نمی‌کنند را ممنوع‌سازی کند. | ## بخش 3: برنامه‌نویسی مجموعه جواب | این برنامه یک مثال از سازمان کلی‌تر «تولید، تعریف، و آزمون» است: شامل تعریف یک گزاره کمکی است که به ما کمک می‌کند تا همه راه‌حل‌های بالقوه «بد» را حذف کند. تجزیه‌کننده وابستگی در پردازش زبان‌های طبیعی، «تجزیه‌کننده مبتنی بر وابستگی» را می‌توان توسط یک برنامه ASP فرمول‌دهی کرد. درخت نحوی توسط گزاره‌های «arc» بیان می‌شوند، که نمایش‌دهنده وابستگی‌های بین کلمات موجود در جمله است. ASP-Core-2 زبان مرجع برای مسابقه برنامه‌نویسی مجموعه جواب است، که در آن حل‌کننده‌های ASP به صورت دوره‌ای، دربرابر تعدادی از مسائل مرجع، محک‌زنی می‌شدند. کاربردها در برخی محیط‌های میزبانی وب که از معماری Nginx و Apache پشتیبانی می‌کنند، عملکرد رشد یافته‌ای برای بارگذاری صفحات دینامیک فراهم ساخته‌اند؛ بنابراین برنامه‌نویسی اعلانی (مانند ASP) در این زیرساخت‌ها اغلب با ثبات و سرعت پردازش بالاتری اجرا می‌شود. مقایسه پیاده‌سازی‌ها سامانه‌ای قدیمی، مثل Smodels برای یافتن جواب‌ها از پس‌گرد استفاده می‌کردند. سامانه‌های جدیدتر، مثل Clasp، از یک دیدگاه ترکیبی استفاده می‌کند، که از الگوریتم‌های مغایرت‌گرای الهام‌گرفته از SAT استفاده می‌کرد، و در آن نیازی به تبدیل کامل به یک حالت بولی-منطقی نبود. این دیدگاه‌ها به ما امکان بهبود کارایی قابل توجهی را می‌دهد، که معمولاً با یک مرتبه بزرگی بهتر از الگوریتم‌های پس‌گرد قدیمی بود. | ## جمع‌بندی | نیاز به زمینه می‌تواند منجر به یک انفجار ترکیبیاتی از بندها شود؛ از این رو سامانه‌هایی که از زمینه‌های on-the-fly استفاده می‌کنند، می‌توانند یک مزیت داشته باشند.