advertise laitec sharif univercity
دانلود سورس اپلیکیشن اندروید پیانو سنتی

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

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

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

148000 تومان
سورس پروژه پایانی وب سایت و نرم افزار کلینیک در ASP.net

سورس پروژه پایانی وب سایت و نرم افزار کلینیک در ASP.net

48000 تومان
سورس پروژه دفترچه تلفن ساده در سی شارپ #c و بانک Access

سورس پروژه دفترچه تلفن ساده در سی شارپ #c و بانک Access

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

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

10000 تومان

الگوریتم جست وجوی محلی WALKSAT

الگوریتم WALKSAT خانواده ای از الگوریتم های کارآمد در استنتاج گزاره ای مبتنی بر بازرسی مدل است که در هر تکرار یک کلاز ارضا نشده را انتخاب میکند و نمادی را از کلاز انتخاب میکند تا تغییر دهد.
الگوریتم جست وجوی محلی WALKSAT

الگوریتم جست وجوی محلی WALKSAT

الگوریتم WALKSAT خانواده ای از الگوریتم های کارآمد در استنتاج گزاره ای مبتنی بر بازرسی مدل است که به جست وجوی تپه نوردی مربوط میشود و بخشی از "فناوری" منطق گزاره ای می باشد.

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

 

یکی از ساده ترین و کارآمدترین الگوریتم ها WALKSAT است که شبه کد آن را نیز در ادامه خواهید دید. در هر تکرار، الگوریتم یک کلاز ارضا نشده را انتخاب میکند و نمادی را از کلاز انتخاب میکند تا تغییر دهد.

بطور تصادفی یکی از روشها را برای انتخاب نماد جهت تغییر برمیگزیند: (1) مرحله "کمترین تناقض" که تعداد کلازهای ارضا نشده در حالت جدید را مینیمم میکند. (2) مرحله "پیمایش تصادفی" که نماد را بطور تصادفی انتخاب میکند.

وقتی WALKSAT مدلی را برمی گرداند، جمله ورودی ارضاپذیری است، اما وقتی  failure را برمیگرداند دو علت ممکن وجود دارد : یا جمله ارضانشدنی است یا باید زمان بیشتری به الگوریتم بدهیم. اگر قرار دهیم max_flips =   و  p>0 ، آنگاه WALKSAT سرانجام یک مدل را برمیگرداند (در صورت وجود) ، زیرا مراحل پیمایش تصادفی سرانجام منجر به جواب میشوند. اگر max_flips  بی نهایت و جمله ارضاناپذیر باشد، آنگاه الگوریتم هرگز خاتمه نمی یابد.

به همین دلیل ، وقتی انتظار داریم جوابی وجود داشته باشد، WALKSAT مفیدتر خواهد بود. از طرف دیگر WALKSAT همیشه نمیتواند ارضاپذیری را تشخیص دهد، که برای تصمیم گیری راجع به ایجاب منطقی ضروری است.

 

شبه کد الگوریتم WALKSAT 

 

function   WALKSAT(clauses, p , max_flips)  returns  a  satisfying  or  failure

         inputs:   clauses,  a  set  of  clauses  in  propositional  logic

                       p,  the  probability  of  choosing  to do  a “random  walk”  move, typically  around  0.5

                       max_flips,  number  of  flips  allowed  before  giving  up

 

         model <-- a  random  assignment  of  truel  false  to  the  symbols  in  clauses

         for   i = 1  to   max_flips  do

                       if  model   satisfies  clauses  then  return  model

                       clause <-- a randomly  selected  clause  from  clauses  that   is  false  in  model

                        with  probability  p  flip  the  value  in  model  of  a  randomly  selected  symbol  from  clause

                       else   flip  whichever  symbol  in  clause  maximizes  the  number  of   satisfied   clauses

         return  failure

 

 



1
نظرات
  • user avatar فاطمه:
    ۲۰:۳۸:۵۶ __ ۱۳۹۵/۰۶/۱۶

    سلام ممنون از توضیح خوبتون..میشه لطفا یه مثال هم ازش بگذارید؟متشکرم

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



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


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

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

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