advertise laitec sharif univercity تبلیغات در سایت سورس کد تبلیغات در سایت سورس کد
دانلود سورس هوش مصنوعی رنگ آمیزی گراف با ژنتیک در #C

دانلود سورس هوش مصنوعی رنگ آمیزی گراف با ژنتیک در #C

4800 تومان
دانلود سورس پروژه پایانی وب سایت بنگاه املاک با php

دانلود سورس پروژه پایانی وب سایت بنگاه املاک با php

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

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

3000 تومان
دانلود پروژه مدیریت کتابخانه با سی شارپ و SQL سرور

دانلود پروژه مدیریت کتابخانه با سی شارپ و SQL سرور

3000 تومان
دانلود برنامه رنگ آمیزی گراف با الگوریتم عقبگرد در سی شارپ

دانلود برنامه رنگ آمیزی گراف با الگوریتم عقبگرد در سی شارپ

3000 تومان

انواع فرموله کردن مسائل ارضای محدودیت 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