سایپرز، باشگاه دانش - ارائه دهنده مقالات ژورنالهای خارجی

اطلاعات و مشخصات مقاله

explorer iconلينك‌ها

[ بازگشت | جستجو | فهرست کلمات کلیدی | فهرست موضوعات | فهرست نویسندگان | فهرست ناشران | فهرست ژورنالها ]

info iconاطلاعات مقاله

[ 41 بار مشاهده چكيده]

عنوان مقاله:تجزیه و تحلیل کامل پیچیدگی پارامتر های برنامه ریزی محدود
ناشر: [ Elsevier BV ]
ژورنال
دوره (شماره):81 (7)
سال انتشار:November 2015
شماره صفحات: 131113321311-1332
نشانگر دیجیتالی شیء:[ 10.1016/j.jcss.2015.04.002 ]
شما اینجا هستید:
  1. Scipers, the Knowledge ClubScipers »
  2. Elsevier BV »
  3. Journal Of Computer And System Sciences »
  4. A complete parameterized complexity analysis of bounded planning

report iconنمايش خلاصه مقاله

A Complete Parameterized Complexity Analysis Of Bounded Planning


مقاله: تجزیه و تحلیل کامل پیچیدگی پارامتر های برنامه ریزی محدود

نويسند‌گان:


خلاصه مقاله:


The propositional planning problem is a notoriously difficult computational problem, which remains hard even under strong syntactical and structural restrictions. Given its difficulty it becomes natural to study planning in the context of parameterized complexity. In this paper we continue the work initiated by Downey, Fellows and Stege on the parameterized complexity of planning with respect to the parameter “length of the solution plan.” We provide a complete classification of the parameterized complexity of the planning problem under two of the most prominent syntactical restrictions, i.e., the so called PUBS restrictions introduced by Bäckström and Nebel and restrictions on the number of preconditions and effects as introduced by Bylander. We also determine which of the considered fixed-parameter tractable problems admit a polynomial kernel and which do not.


مشکل برنامه ریزی گزاره مشکل دشوار محاسباتی، که حتی تحت محدودیت های نحوی و ساختاری قوی سخت باقی مانده است. با توجه به سختی آن را طبیعی می شود به مطالعه برنامه ریزی در زمینه پیچیدگی پارامتر. در این مقاله ما کار بر روی پیچیدگی پارامتر های برنامه ریزی با توجه به پارامتر آغاز شده توسط داونی، همکاران و Stege ادامه "طول طرح راه حل است." ما با ارائه یک طبقه بندی کامل از پیچیدگی پارامتر از مشکل برنامه ریزی در دو از ترین محدودیت برجسته نحوی، به عنوان مثال، به اصطلاح محدودیت بارها معرفی شده توسط Bäckström و Nebel و محدودیت در تعداد پیش شرط و اثرات به عنوان Bylander معرفی شده است. ما همچنین مشخص است که از در نظر گرفته ثابت پارامتر مشکلات رام اعتراف یک هسته چند جمله ای و که نمی کنند.


كلمات كليدي:

Complexity of automated planning, Kernelization, Parameterized complexity
پیچیدگی برنامه ریزی خودکار, Kernelization, پیچیدگی پارامتر


موضوعات:

Computational Theory and Mathematics, Computer Networks and Communications, Applied Mathematics, Theoretical Computer Science



[ ]

 

دسترسی بین المللی

اگر شما در داخل کشور (ایران) هستید و این صفحه را مشاهده می کنید، نشان می دهد که IP شما به هر دلیلی در لیست IP های ایران ثبت نشده است. برای رفع این مشکل کافی است IP خود را که در پایین این پیام درج شده از طریق آدرس ایمیل support@scipers.com به ما اطلاع دهید. پس از دریافت درخواست، کارشناسان فنی موضوع را بررسی می نمایند و در صورتی که محل اتصال شما از کشور ایران بوده باشد، به لیست استفاده کنندگان مجاز افزوده می شوید.
IP: 54.226.58.177

اطلاعات استنادی

اطلاعات استنادی این مقاله را به نرم افزارهای مدیریت اطلاعات علمی و استنادی ارسال نمایید و در تحقیقات خود از آن استفاده نمایید.

 

به اشتراک گذاری

این صفحه را با استفاده از انواع شبکه های اجتماعی با دوستان خود به اشتراک بگذارید.

برگشت به بالا
رونمایی از اولین و تنها ربات تلگرامی جستجوی مقالات ژورنالی
×