advertise laitec sharif univercity تبلیغات در سایت سورس کد تبلیغات در سایت سورس کد
دانلود پروژه وب سایت هتل با HTML و ASP.NET

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

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

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

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

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

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

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

3000 تومان
دانلود پروژه فروشنده دوره گرد با الگوریتم گرانشی در #C

دانلود پروژه فروشنده دوره گرد با الگوریتم گرانشی در #C

4800 تومان

انتشار محدودیت در استنتاج CSP ها

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

 انتشار محدودیت در استنتاج CSP ها

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

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

 

سازگاری گره

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

 

سازگاری یال

اگر هر مقدار موجود در دامنه ی متغیری در CSP، محدودیت های دودویی این متغیر را ارضا کند، میگوییم این متغیر دارای سازگاری یال است. به طور رسمی تر، متغیر Xi نسبت به متغیر دیگر Xj دارای سازگاری یال است اگر برای هر مقدار در دامنه ی فعلی Di مقداری در دامنه Dj وجود داشته باشد که محدودیت دوتایی روی (Xi , Xj) را ارضا کند. هر شبکه در صورتی سازگاری یال دارد که در آن هر متغیر با متغیر دیگری سازگاری یال باشد.

میتوان مفهوم سازگاری یال را تعمیم داد تا محدودیت های n تایی را نیز اداره کند (نه فقط محدودیت های دوتایی) . این تعمیم "سازگاری یال تعمیم یافته" یا سازگاری ابر گراف، نام دارد. اگر برای هر مقدار v در دامنه متغیر Xi یک چندتایی از مقادیر وجود داشته باشد که عضوی از این محدودیت باشد، متغیر Xi دارای "سازگاری یال تعمیم یافته" است و تمام مقادیر این چندتایی از دامنه های متناظر با متغیرها انتخاب میشوند، مولفه های Xi آن برابر با v است.

 

سازگاری مسیر

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

مجموعه دو متغیر {Xi , Xj} را در نظر بگیرید. اگر برای هر انتساب { Xi =a , Xj =b } سازگار با محدودیت های روی  {Xi , Xj} انتسابی به Xm وجود داشته باشد که محدودیت های روی  {Xi , Xm } و  { Xm , Xj} را ارضا کند، مجموعه  {Xi , Xj} سازگاری مسیر دارد. علت اینکه این سازگاری را به نام سازگاری مسیر میخوانیم این است که میتوان آن را مسیری از Xi به Xj دانست که Xm در وسط قرار دارد.

 

سازگاری مرتبه k

شکل های قوی تر "انتشار محدودیت" را میتوان با مفهوم سازگاری مرتبه k تعریف کرد.CSP در صورتی سازگاری مرتبه k دارد که برای هر مجموعه k-1 متغیری و برای هر اتساب سازگار با آن متغیرها، همیشه بتوان یک مقدار سازگار را به هر متغیر k ام نسبت داد. سازگاری مرتبه 1 میگوید که با توجه به یک مجموعه یال میتوان هر مجموعه ی یک متغیری را سازگار کرد، و این همان چیزی است که قبلا آن را سازگاری گره نامیدیم. سازگاری مرتبه 2 مثل سازگاری یال است. برای شبکه هایی با محدودیت های دوتایی سازگاری مرتبه 3 شبیه سازگاری مسیر است.

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

 



0
نظرات

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



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


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

سفارش پروژه در سورس کد

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

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