advertise laitec sharif univercity
دانلود پروژه وب سایت اشعار با ASP.NET و SQL

دانلود پروژه وب سایت اشعار با ASP.NET و SQL

10000 تومان
دانلود سورس اندروید اپلیکیشن افزایش سرعت گوشی

دانلود سورس اندروید اپلیکیشن افزایش سرعت گوشی

18000 تومان
دانلود پروژه مهندسی نرم افزار ، نمایندگی ایران خودرو

دانلود پروژه مهندسی نرم افزار ، نمایندگی ایران خودرو

10000 تومان
دانلود مجموعه 70 پروژه مفید و کاربردی سی شارپ #C

دانلود مجموعه 70 پروژه مفید و کاربردی سی شارپ #C

28000 تومان
سیستم اتوماسیون دهیاری ، پروژه مهندسی نرم افزار

سیستم اتوماسیون دهیاری ، پروژه مهندسی نرم افزار

10000 تومان

انواع فرموله کردن مسائل ارضای محدودیت CSP

ساده ترین نوع CSP شامل متغیرهایی است که دامنه های متناهی و گسسته دارند. دامنه گسسته میتواند نامتناهی باشد، مثل مجموعه ای از رشته ها یا مقادیر صحیح.
انواع فرموله کردن مسائل ارضای محدودیت CSP

انواع فرموله کردن مسائل ارضای محدودیت CSP

ساده ترین نوع CSP شامل متغیرهایی است که دامنه های متناهی و گسسته دارند. مسئله های رنگ آمیزی نقشه و زمانبندی در زمانهای محدود، از این نوع هستند. مسئله هشت وزیر نیز میتواند بعنوان یک CSP با دامنه متناهی در نظر گرفته شود، که درآن، متغیرهای Q1, … , Q8 موقعیت های هر وزیر در ستون های 1, …,8 است و هر متغیر دارای دامنه Di = {1, 2, 3, 4, 5, 6, 7, 8} است.

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

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

علاوه بر انواع متغیرهایی که میتوانند در CSP ها ظاهر شوند، نگاهی به انواع محدودیت ها مفید به نظر میرسد. ساده ترین نوع، محدودیت یگانی است که فقط مقدرا یک متغیر را محدود میکند. محدودیت دوتایی (دو دویی) به دو متغیر مربوط میشود. CSP دوتایی فقط دارای محدودیت دوتایی است و میتواند بصورت گراف محدودیت ها نمایش داده شود.

محدودیت های مرتبه بالاتر را نیز میتوان توصیف کرد. محدودیتی که حاوی تعداد دلخواهی از متغیهاست، محدودیت سراسری نام دارد. یکی از متداول ترین محدودیت های سراسری  Alldiff است که میگوید تمام متغیرهای موجود در این محدودیت باید مقادیر متفاوتی داشته باشند. در مسئله های سودوکو تمام متغیرهای موجود در یک سطر یا یک ستون، محدودیت Alldiff را ارضا کنند (براورده میکنند.)

این محدودیت ها میتوانند در ابرگراف محدودیت ها، نمایش داده شوند. ابرگراف شامل گره های معمولی و ابرگره ها است که محدودیت های n تایی را نشان میدهد.

از طرف دیگر، اگر تعداد کافی از متغیرهای کمکی معرفی شوند، هر محدودیت با دامنه متناهی میتواند به مجموعه ای از محدودیت های دوتایی کاهش یابد، و در نتیجه میتوانیم هر CSP را به یک CSP فقط با محدودیت های دوتایی تبدیل کنیم. به این ترتیب الگوریتم ساده تر میشود. روش دیگر برای تبدیل CSP با محدودیت های n تایی به CSP دوتایی تبدیل به گراف دوگان است. یعنی گراف جدیدی ایجاد شود که در آن برای هر محدودیت موجود در گراف اصلی، یک متغیر وجود دارد و برای هر جفت از محدودیت ها در گراف اصلی که متغیرهای مشترکی دارند یک محدودیت دوتایی وجود دارد.

به دو دلیل ممکن است یک محدودیت سراسری مثل Alldiff را نسبت به مجموعه ای از محدودیت های دودویی ترجیح دهیم. اول اینکه، نوشتن توصیف مسئله با استفاده از Alldiff آسانتر است. دوم اینکه میتوان الگوریتم های استنتاج با هدف ویژه را برای محدودیت های سراسری نوشت که برای مجموعه ای از محدودیت های ابتدایی تر وجود ندارد.

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

با این فرموله کردن، CSP های همراه با محدودیت های ترجیحی را میتوان به روش های جست وجوی بهینه سازی حل کرد. چنین مسئله ای را مسئله بهینه سازی محدودیت یا COP مینامند. مسئله های برنامه ریزی خطی این نوع بهینه سازی را انجام میدهند.

 



0
نظرات

نظر خود را ارسال کنید



نام:
ایمیل:
دیدگاه:
captcha
کد امنیتی :


advertise
محدودیت های ترجیحی در CSPانواع فرموله کردن CSPانواع فرموله کردن مسائل ارضای محدودیتانواع دامنه های CSPتنوع فرموله کردن مسائل ارضای محدودیتتبلیغات ارزان سایت آموزش برنامه نویسیتبلیغات مخصوص طراحان وب سایتتبلیغات در سایت برنامه نویسیتبلیغات اینترنتی برای برنامه نویساندر آغوش مینیمالیسممنوی همبرگر با سه خط افقی که روی یکدیگر قرار گرفته اند نشانه چیست؟ سوئیچ به یک ستون واحدتبدیل متن ساده به وبلاگ و سایت های پویا با React.jsکتابخانه sass برای استفاده آسان تر از آنکتابخانه سطح بالا برای اتوماتیک سازی اعمال مرورگر لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

پیشنهادات ویژه سورس کد

پکیج ویژه پروژه پایانی رشته کامپیوتر دانلود مجموعه 70 پروژه کاربردی سی شارپ وب سایت فروشگاه با php