advertise laitec sharif univercity
دانلود پروژه فروشنده دوره گرد با الگوریتم ازدحام ذرات PSO در #C

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

10000 تومان
دانلود آپلود سنتر پیشرفته با PHP و Ajax

دانلود آپلود سنتر پیشرفته با PHP و Ajax

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

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

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

دانلود PDF مجموعه 300 نکته جالب برنامه نویسی در سی شارپ #C

10000 تومان
دانلود سورس پروژه فروشگاه کیف با asp.net و sql express

دانلود سورس پروژه فروشگاه کیف با asp.net و sql express

10000 تومان

الگوریتم عقبگرد هوشمند در CSPها

در الگوریتم عقبگرد هوشمند(نگریستن به عقب) CSP ها آنقدر به عقب برگردیم تا به متغیری برسیم که مسئله را حل کند و یکی از مقادیر ممکن دامنه را غیرممکن سازد
الگوریتم عقبگرد هوشمند در CSPها

الگوریتم عقبگرد هوشمند در CSPها

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

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

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

توجه داشته باشید که بررسی پیشرو میتواند "مجموعه تناقض" را بدون کار اضافی تولید کند بطوریکه هر وقت بررسی پیشرو براساس انتساب X=x ، مقداری را از دامنه Y حذف میکند، باید X=x را به مجموعه تناقض Y اضافه کند. اگر آخرین مقدار از دامنه Y حذف شود، آنگاه انتسابهای موجود در مجموعه تناقض Y، به مجموعه تناقض X اضافه میشوند. سپس وقتی به Y میرسیم، فورا میدانیم که در صورت نیاز به کجا باید برگردیم.

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

بطور خلاصه فرض کنید Xj متغیر فعلی و conf(Xj)مجموعه تناقض آن باشد. اگر هر مقدار ممکن برای Xj با شکست مواجه شد، به جدیدترین متغیر Xi پرش کنید . قرار دهید:

Conf(Xj) <-- conf(Xi) U conf(Xj) – { Xi }

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

 

 



0
نظرات

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



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


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

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

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