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

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

10000 تومان
پکیج ویژه پروژه پایانی و پایان نامه رشته کامپیوتر

پکیج ویژه پروژه پایانی و پایان نامه رشته کامپیوتر

148000 تومان
دانلود سورس اپلیکیشن اندروید پیانو سنتی

دانلود سورس اپلیکیشن اندروید پیانو سنتی

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

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

10000 تومان
دانلود سورس پروژه TSP با الگوریتم مورچگان Ants

دانلود سورس پروژه TSP با الگوریتم مورچگان Ants

10000 تومان

الگوریتم جست وجوی محلی در CSPها

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

الگوریتم جست وجوی محلی در CSPها

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

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

روش کمترین تناقض ها برای بسیاری از CSP ها بطور کارآمد عمل میکند. در مسئله n وزیر اگر محل اولیه وزیرها را در نظر بگیرید، زمان اجرای روش کمترین تناقض ها، مستقل از اندازه مسئله است. این روش، حتی مسئله یک میلیون وزیر را بطور میانگین در 50 مرحله حل میکند (پس از انتساب اولیه). این مشاهده قابل توجه به تحقیقات زیادی در دهه 1990 بر روی جست وجوی محلی و توزیع بین مسئله های آسان و سخت شد. بعبارت ساده تر مسئله n وزیر به راحتی به روش کمترین تناقض ها حل میشود، زیرا جوابها بطور متراکم در سراسر فضای حالت توزیع شده اند. روش کمترین تناقض ها برای مسئله های سخت نیز به خوبی کار میکند. برای مثال، برای زمانبندی مشاهدات "تلسکوپ فضایی هابل" به کار رفت، بطوریکه زمان لازم برای برنامه ریزی را از سه هفته به 10 دقیقه کاهش داد.

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

 

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

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

 

شبه کد الگوریتم جست وجوی محلی در CSPها

 

function  MIN-CONFLICTS (csp, max_steps)  returns  a  solution or  failure

     inputs : csp, a constraint  satisfaction  problem

                  max_steps, the number  of  steps  allowed  before giving up

 

     current <-- an  initial  complete  assignment  for  csp

     for  i = 1  to  max_steps   do

              if  current  is a  solution  for  csp  then  return  current

             var <-- a randomly  chosen  con flicted  variable  from  csp.VARIABLES

             value <--  the  value  v  for  var  that  minimizes  CONFLICTS (var, v, current, csp)

             set  var = value  in  current

     return  failure

 

 



0
نظرات

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



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


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

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

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