Power Point

Report
‫عامل هاي منطقي‬
‫تهيه کننده‪ :‬عبدالرضا ميرزايي‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫سرفصل مطالب‬
‫عامل هاي مبتني بر دانش‬
‫محيط‪Wumpus‬‬
‫منطق – مدل ها و استلزام‬
‫منطق گزاره اي (بولين)‬
‫هم ارزي‪ ،‬اعتبار و صدق پذيري‬
‫قوانين استنتاج و اثبات تئوري‬
‫– زنجيره استنتاج رو به جلو )‪(forward chaining‬‬
‫– زنجيره استنتاج رو به عقب )‪(backward chaining‬‬
‫– رزولوشن‬
‫‪2‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫پايگاه دانش‬
‫• پايگاه دانش = مجموعه اي از جمالت در يك زبان رسمي‬
‫• مي توان عامل ها را در سطح دانش در نظر گرفت‪:‬‬
‫• يعني‪ ،‬چه مي دانند‪ ،‬بدون توجه به چگونگي پياده سازي‬
‫• • يا در سطح پياده سازي‪:‬‬
‫• يعني‪ ،‬ساختارهاي داده اي در ‪ KB‬و الگوريتم هايي كه بر روي آنها كار‬
‫مي كنند‪.‬‬
‫‪3‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫پايگاه دانش‬
‫• براي ايجاد يك عامل ( يا سيستم هاي ديگر)‪:‬‬
‫• رهيافت رويه اي‬
‫• رفتارهاي مطلوب را به طور مستقيم و به صورت کد برنامه رمزگذاري‬
‫مي کند‪ .‬در نتيجه با کاهش نقش بازنمايي و استدالل صريح به سامانه بسيار‬
‫کاراتري مي انجامد‪.‬‬
‫• رهيافت توصيفي‬
‫• به عامل آنچه را كه نياز دارد بداند‪ ،‬بگو )‪(TELL‬‬
‫• آنگاه عامل مي تواند از خود بپرسدكه چه عملي انجام دهد (‪)ASK‬‬
‫• پاسخ ها بايد از ‪ KB‬پيروي کند‬
‫• يک عامل زماني موفق خواهد بود که دو جزء رويه اي و توصيفي‬
‫در طراحي اش ترکيب شده باشند‪.‬‬
‫‪4‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫يك عامل ساده مبتني بر دانش‬
‫• عامل بايد قادر باشد‪:‬‬
‫–‬
‫–‬
‫–‬
‫–‬
‫‪5‬‬
‫حاالت و اعمال و ‪ ...‬را بازنمايي كند‪.‬‬
‫ادراك جديد دريافت كند‪.‬‬
‫بازنمايي داخلي دنيا را بهنگام سازد‪.‬‬
‫خواص پنهان دنيا و اعمال مناسب را نتيجه گيري كند‪.‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫دنياي‪Wumpus‬‬
‫• معيار كارآيي‬
‫– طال ‪ ، + 10000‬مرگ ‪-1000‬‬
‫• محيط‬
‫– خانه هاي مجاور ومپوس داراي بو هستند‬
‫– خانه هاي مجاور چاله ها داراي نسيم هستند‬
‫– در خانه حاوي طال‪ ،‬درخشش وجود دارد‬
‫– شليك ومپوس را مي كشد‪ ،‬اگر عامل رو به ومپوس باشد‬
‫– تنها يك شليك موثر است‬
‫– اگر در خانه عامل طال باشد‪ ،‬مي تواند آنرا بردارد‬
‫– عامل مي تواند طال را در خانه فعلي رها كند‬
‫‪6‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫دنياي‪Wumpus‬‬
‫• حسگرها‬
‫– نسيم‪ ،‬درخشش‪ ،‬بو‪ ،‬ضربه و جيغ‬
‫• عملگرها‬
‫– چرخش به چپ و راست‬
‫– حركت به جلو‬
‫– برداشتن و رها كردن و شليك تير‬
‫‪7‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مشخصات دنياي‪Wumpus‬‬
‫• دسترس پذير؟‬
‫خير – تنها ادراك محلي ميسر مي باشد‬
‫• قطعي؟‬
‫بله– نتيجه اعمال كامال مشخص است‬
‫• اپيزوديك؟‬
‫خير – در سطح اعمال ترتيبي است‬
‫• ايستا؟‬
‫بله – ومپوس و چاله ها حركت نمي كنند‬
‫• گسسته؟‬
‫بله‬
‫• تك‪ -‬عاملي؟‬
‫بله – ومپوس اساسا ً يك ويژگي طبيعي است‬
‫‪8‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫كاوش دنياي ‪Wumpus‬‬
‫كاوش دنياي ‪Wumpus‬‬
‫كاوش دنياي ‪Wumpus‬‬
‫كاوش دنياي ‪Wumpus‬‬
‫كاوش دنياي ‪Wumpus‬‬
‫كاوش دنياي ‪Wumpus‬‬
‫كاوش دنياي ‪Wumpus‬‬
‫كاوش دنياي ‪Wumpus‬‬
‫منطق‬
‫• منطق يك زبان رسمي براي بازنمايي دانش بطوري كه بتوان از آن‬
‫نتيجه گيري نمود‪.‬‬
‫• نحو (‪)Syntax‬ساختار جمالت زبان را تعريف مي كند‬
‫• معنا (‪ )Semantic‬معناي جمالت را تعريف مي كند‬
‫• يعني‪ ،‬تعريف درستي يك جمله در يك دنيا‬
‫• مثال‪ :‬زبان رياضي‬
‫جمله‬
‫‪• x+2≥y‬‬
‫جمله نيست‬
‫≥ ‪• x2 + y‬‬
‫• جمله ‪ x + 2 ≥ y‬در دنيايي با ‪ x = 7, y = 1‬درست و در دنيايي با‬
‫‪ x = 0, y = 6‬نادرست مي باشد‪.‬‬
‫‪17‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫ايجاب ‪Entailment‬‬
‫• ايجاب بدين معناست كه چيزي از چيز ديگري استنباط شود‪:‬‬
‫‪KB ╞ α‬‬
‫• پايگاه دانش ‪ KB‬جمله ‪ α‬را ايجاب مي کند اگر و فقط اگر در تمام‬
‫دنياهايي كه در آن ‪ KB‬درست است ‪ α‬درست باشد‪.‬‬
‫مثال ‪x + y =4 entails 4=x + y‬‬
‫• ايجاب رابطه ايست كه بين جمالت (‪ )syntax‬و بر مبناي معناي‬
‫جمالت (‪ )semantic‬تعريف مي شود‪.‬‬
‫‪18‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مدل ها‬
‫• منطق دانان عموما ً بر حسب مدل ها فكر مي كنند‪ ،‬كه بطور رسمي‬
‫دنياهاي ساخت يافته اي مي باشند كه درستي را مي توان نسبت به‬
‫آنها ارزيابي كرد‪.‬‬
‫مي گوييم ‪ m‬مدلي از جمله ‪ α‬مي باشد‬
‫اگر ‪ α‬در ‪ m‬درست باشد‪.‬‬
‫)‪ M(α‬مجموعه تمام مدل هاي ‪ α‬مي‬
‫باشد‪.‬‬
‫)‪KB ╞ α iff M(KB)  M(α‬‬
‫‪19‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫ايجاب در دنياي ‪Wumpus‬‬
‫• موقعيت پس از دريافت ادراک تهي‬
‫در ]‪ ،[1,1‬رفتن به راست‪ ،‬دريافت‬
‫نسيم در ]‪[2,1‬‬
‫• مدلهاي ممكن براي ? ها را تنها با‬
‫فرض چاله ها در نظر بگيريد‪.‬‬
‫• سه انتخاب بولين ‪ . :‬هشت مدل‬
‫مختلف‬
‫‪20‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
Wumpus ‫مدل هاي‬
Wumpus ‫مدل هاي‬
KB = wumpus-world rules + observations
Wumpus ‫مدل هاي‬
KB = wumpus-world rules + observations
α1 = "[1,2] is safe", KB ╞ α1, proved by model
checking
Wumpus ‫مدل هاي‬
KB = wumpus-world rules + observations
Wumpus ‫مدل هاي‬
KB = wumpus-world rules + observations
α2 = "[2,2] is safe", KB ╞ α2
‫استنتاج )‪(Inference‬‬
‫• ‪ : KB ├i α‬جمله ‪ α‬از ‪ KB‬بوسيله رويه ‪ i‬قابل استخراج مي باشد‪.‬‬
‫• نتايج ‪ KB‬مانند يك انبار كاه مي باشدو ‪ α‬مانند يك سوزن‬
‫• ايجاب = سوزن در انبار كاه؛ استنتاج = يافتن سوزن‬
‫• صحت و کامل بودن رويه استنتاج‬
‫الگوريتم استنتاجي که فقط جمالت ايجابي را به دست آورد صحيح است‬
‫الگوريتم استنتاجي که بتواند هر جمله ايجاب شدني را به دست آورد کامل است‪.‬‬
‫‪Soundness:‬‬
‫‪i is sound if whenever KB ├i α, it is also true that KB╞ α‬‬
‫‪Completeness:‬‬
‫‪i is complete if whenever KB╞ α, it is also true that KB ├i α‬‬
‫مثال‪ :‬در منطق مرتبه اول (‪ )First Order Logic‬يك رويه اسنتاج كامل و‬
‫صحيح وجود دارد‪.‬‬
‫‪26‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫ نحو‬: ‫منطق گزاره اي‬
‫• منطق گزاره اي ساده ترين نوع منطق است – براي بيان‬
‫ايده هاي ساده و پايه اي‬
‫ هر كدام يك جمله مي‬... ‫ و‬P2 ،P1 ‫• سمبولهاي گزاره اي‬
‫باشند‬
• If S is a sentence, S is a sentence (negation)
• If S1 and S2 are sentences, S1  S2 is a sentence (conjunction)
• If S1 and S2 are sentences, S1  S2 is a sentence (disjunction)
• If S1 and S2 are sentences, S1  S2 is a sentence (implication)
• If S1 and S2 are sentences, S1  S2 is a sentence (biconditional)
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
27
‫ معنا‬:‫منطق گزاره اي‬
‫غلط بودن سمبول هاي گزاره اي را مشخص مي كند‬/‫• هر مدل درست بودن‬
E.g. P1,2
false
P2,2
true
P3,1
false
‫ مدل از طريق برشماري قابل ايجاد است‬8 ‫• با اين سمبولها‬
m ‫• قوانين ارزيابي درستي نسبت به يك مدل‬
S
S1  S2
S1  S2
S1  S2
i.e.,
S1  S2
is
is
is
is
is
is
true iff
true iff
true iff
true iff
false iff
true iff
S is false
S1 is true and
S2 is true
S1is true or
S2 is true
S1 is false or
S2 is true
S1 is true and
S2 is false
S1S2 is true and S2S1 is true
.‫• يک رويه بازگشتي ساده مي تواند هر جمله دلخواهي را ارزيابي کند‬
P1,2  (P2,2  P3,1) = true  (true  false) = true  true = true
‫جدول درستي براي رابط هاي منطقي‬
‫‪29‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫جمالت دنياي ‪Wumpus‬‬
‫• فرض کنيد ‪ Pi,j‬درست باشد‪ ،‬اگر و فقط اگر در خانه ]‪ [i, j‬چاه باشد‬
‫• فرض کنيد ‪ Bi,j‬درست باشد‪ ،‬اگر و فقط اگر در خانه ]‪ [i, j‬نسيم‬
‫باشد‬
‫‪ P1,1‬‬
‫‪B1,1‬‬
‫‪B2,1‬‬
‫• ”چاله ها باعث وزش نسيم در خانه هاي مجاور مي شوند“‪.‬‬
‫)‪(P1,2  P2,1‬‬
‫)‪(P1,1  P2,2  P3,1‬‬
‫‪B1,1 ‬‬
‫‪B2,1 ‬‬
‫• ” در يك خانه نسيم مي وزد اگر و فقط اگر چاله اي مجاور آن باشد“‬
‫‪30‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫استفاده از جدول درستي براي استنتاج‬
‫• سطرهاي مختلف (انتسابهاي مختلف به سمبولها) را برشماري نماييد‬
‫• اگر ‪ KB‬در يک سطر صحيح بود بررسي نماييد که ‪ α‬هم باشد‪.‬‬
‫‪31‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫استنتاج بوسيله شمارش‬
‫• شمارش تمام مدل ها به روش اول – عمق صحيح و كامل است‬
‫‪For n symbols, time complexity is‬‬
‫)‪O(2n), space complexity is O(n‬‬
‫‪32‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫هم ارزي منطقي‬
‫• دو جمله هم ارز منطقي مي باشند‪ ،‬اگر و فقط اگر هر دو در مدلهاي يكساني‬
‫درست باشند‪.‬‬
‫‪33‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫اعتبار و صدق پذيري‬
‫• يك جمله معتبر ‪ valid‬است اگر در تمام مدل ها درست باشد‬
‫–مثال‬
‫• ارتباط معتبر بودن با استنتاج‪:‬‬
‫• يك جمله صدق‬
‫درست باشد‬
‫–مثال‬
‫• يك جمله صدق ناپذير ‪ unsatisable‬است اگر در هيچ مدلي درست‬
‫نباشد‬
‫• ارتباط صدق پذيري با استنتاج‪( :‬اثبات با برهان خلف)‬
‫پذير‪satisfiable‬‬
‫‪34‬‬
‫است اگر در بعضي از مدل ها‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫روش هاي اثبات‬
‫• روش هاي اثبات به دو نوع تقسيم مي شوند‪:‬‬
‫• اعمال قوانين استنتاج‪:‬‬
‫ توليد صحيح جمالت جديد از جمالت قديمي‬‫ اثبات = دنباله اي از اعمال قوانين استنتاج‬‫ مي توان از قوانين استنتاج به عنوان عملگرها در الگوريتم استاندارد‬‫جستجو استفاده كرد‪.‬‬
‫ اغلب نياز به تبديل جمالت به يك شكل نرمال دارند‪.‬‬‫• بررسي مدل‪model checking :‬‬
‫ شمارش جدول درستي (بر حسب ‪n‬نمايي)‬‫ عقبگرد بهبود يافته مانند) ‪Davis Putnam Logemann Loveland‬‬‫ جستجوي هيوريستيك در فضاي مدل ( صحيح اما نا كامل) مانند الگوريتم‬‫هاي ‪min-conicts-like hill-climbing‬‬
‫‪35‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫استنتاج رو به جلو و رو به عقب‬
‫ شكل نرمال‪(HNF) Horn‬‬‫• ‪ = KB‬تركيب عطفي عبارت هاي ‪Horn‬‬
‫• عبارت‪Horn‬‬
‫ سمبول گزاره اي‬‫‪ ( -‬سمبول گزاره اي( ⇒(تركيب عطفي سمبول هاي گزاره اي)‬
‫‪ -‬قانون استنتاج ‪Modes Ponens‬براي شكل‪Horn‬‬
‫ مي تواند در هر دو روش روبه جلو و روبه عقب بكار رود‪.‬‬‫ اين روشها بسيار طبيعي هستند و در زمان خطي (برحسب‬‫اندازه ‪ )KB‬اجرا مي شوند‪.‬‬
‫‪36‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫استنتاج روبه جلو‬
‫ايده ‪ :‬هر قانوني كه بخش شرط آن در‪ KB‬ارضاء شده را ‪ fire‬كن و‬
‫نتيجه قانون را به ‪ KB‬اضافه كن‪ ،‬تا زمانيكه پاسخ پيدا شود و يا‬
‫استنتاج ديگري ممكن نباشد‪.‬‬
‫‪37‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫استنتاج روبه جلو‬
‫• استنتاج روبه جلو براي پايگاه دانش در شكل ‪ Horn‬کامل و صحيح‬
‫است‪.‬‬
‫استنتاج روبه جلو‬
‫استنتاج روبه جلو‬
‫استنتاج روبه جلو‬
‫استنتاج روبه جلو‬
‫استنتاج روبه جلو‬
‫استنتاج روبه جلو‬
‫استنتاج روبه جلو‬
‫استنتاج روبه جلو‬
‫اثبات کامل بودن ‪FC‬‬
‫‪47‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫استنتاج رو به عقب‬
‫ايده‪ :‬براي اثبات ‪ q‬به سمت عقب حركت كن‬
‫براي اثبات ‪ q‬از طريق ‪BC‬‬
‫• چک كن كه آيا ‪ q‬قبال ثابت شده است‪ ،‬يا‬
‫• بوسيله ‪ BC‬تمام شرايط برخي از قوانين را كه نتيجه آنها ‪ q‬است‬
‫اثبات كن‬
‫• اجتناب از حلقه‪ :‬بررسي قرار داشتن زيرهدف جديد روي‬
‫پشته هدف‬
‫اجتناب از اعمال تكراري‪ :‬بررسي اينكه آيا زيرهدف جديد‬
‫‪48‬‬
‫‪ )1‬قبال درستي اش اثبات شده‪ ،‬يا‬
‫‪ )2‬قبال شكست خورده است )‪(fail‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫استنتاج رو به عقب‬
‫استنتاج رو به عقب‬
‫استنتاج رو به عقب‬
‫استنتاج رو به عقب‬
‫استنتاج رو به عقب‬
‫استنتاج رو به عقب‬
‫استنتاج رو به عقب‬
‫استنتاج رو به عقب‬
‫استنتاج رو به عقب‬
‫استنتاج رو به عقب‬
‫مقايسه دو روش‬
‫• ‪FC‬‬
‫‪ -‬بر مبناي داده )‪(data driven‬‬
‫ تصميم گيريهاي اتوماتيک و ناخودآگاه مانند تشخيص اشياء‪،‬‬‫تصميم هاي روزمره‬
‫ ممكن است كارهاي بسياري انجام دهد كه به هدف مربوط نمي‬‫شوند‬
‫• ‪BC‬‬
‫‪ -‬بر مبناي هدف )‪(goal driven‬‬
‫ کليدهاي من کجا هستند؟ چگونه وارد دوره دکتري شوم؟‬‫خطي نسبت به اندازه ‪KB‬‬
‫‪ - 59‬پيچيدگي ‪ BC‬مي تواند بسيار بهتر از‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫‪Resolution‬‬
‫• شكل نرمال عطفي )‪(CNF‬‬
‫• قانون استنتاج رزولوشن (براي ‪ )CNF‬صحيح وكامل براي منطق‬
‫گزاره اي‬
‫که ‪ li‬و ‪ mj‬نقيض يكديگرند‬
‫‪60‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫‪Resolution‬‬
‫• رزولوشن براي منطق گزاره اي صحيح و كامل مي باشد‪.‬‬
‫‪61‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
Resolution
‫• صحت قانون استنتاج رزولوشن‬
(li  …  li-1  li+1  …  lk)  li
mj  (m1  …  mj-1  mj+1 ...  mn)
(li  …  li-1  li+1  …  lk)  (m1  …  mj-1  mj+1 ...  mn)
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
62
‫تبديل به ‪CNF‬‬
‫‪63‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫الگوريتم‪Resolution‬‬
‫• اثبات بوسيله تناقض‪ ،‬يعني نشان بده ‪ KBα‬صدق ناپذير‬
‫است‬
‫‪64‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مثال براي رزولوشن‬
‫‪• KB = (B1,1  (P1,2 P2,1))  B1,1‬‬
‫‪• α = P1,2‬‬
‫‪65‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫الگوريتم هاي استنتاج كارا در منطق گزاره اي‬
‫• دو خانواده از الگوريتم هاي استنتاج كارآ براي منطق‬
‫گزاره اي‬
‫• الگوريتم هاي كامل جستجوي عقبگرد‬
‫• الگوريتم‪(Davis, Putnam, Logemann, Loveland) DPLL‬‬
‫• الگوريتم ناكامل جستجوي محلي‬
‫• الگوريتم ‪WalkSAT‬‬
‫‪66‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫الگوريتم‪DPLL‬‬
‫• تعيين كن كه آيا يك جمله ورودي در زبان منطق گزاره اي (در شكل نرمال ‪) CNF‬‬
‫صدق پذير است يا خير‪.‬‬
‫• بهبودها نسبت به روش شمارش جدول درستي‪:‬‬
‫• خاتمه زود هنگام‬
‫• يک بند (‪ )clause‬درست است اگر هر يك از ليترال ها درست باشد‪.‬‬
‫• )‪ (A  B)  (A  C‬در صورت درست بودن ‪ A‬صرف نظر از مقادير ‪ B‬و ‪ C‬درست‬
‫است‬
‫• يك جمله نادرست است اگر هر يك از بندهاي آن نادرست باشد‪.‬‬
‫• هيوريستيك سمبول محض‬
‫•‬
‫•‬
‫•‬
‫•‬
‫•‬
‫‪67‬‬
‫سمبول محض‪ :‬سمبولي كه در تمام بندها با يك عالمت ظاهر شود‪.‬‬
‫مثال‪ :‬در سه بند )‪ (A  B), (B  C), (C  A‬سمبولهاي ‪ A‬و ‪ B‬محض و ‪ C‬غير‬
‫محض است‬
‫سمبولهاي محض را به گونه اي انتساب بده که ليترال آن را ‪ true‬کند‬
‫در تعيين سمبول محض از بندهايي که قبال با مقدار ‪ true‬شناخته شده اند صرف نظر مي‬
‫شود‪.‬‬
‫در عبارت باال با تعيين ‪ B=false‬بندهاي )‪ (B  C‬و )‪ (A  B‬مقدار ‪ true‬پيدا مي‬
‫کند و در نتيجه ‪ C‬سمبول محض خواهد بود‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫الگوريتم‪DPLL‬‬
‫• تعيين كن كه آيا يك جمله ورودي در زبان منطق گزاره اي (در شكل نرمال ‪CNF‬‬
‫) صدق پذير است يا خير‪.‬‬
‫• بهبودها نسبت به روش شمارش جدول درستي‪:‬‬
‫• هيوريستيك بند واحد‬
‫•‬
‫•‬
‫•‬
‫•‬
‫•‬
‫‪68‬‬
‫بند واحد‪ :‬تنها شامل يك ليترال مي باشد‪ .‬يا بندي كه تمام ليترال هاي آن غير از يك‬
‫ليترال‪ ،‬نادرست مي باشند‪.‬‬
‫تنها ليترال موجود در يك بند واحد بايد درست باشد‪.‬‬
‫انتساب به يک بند واحد مي تواند بند واحد ديگري توليد کند ‪Unit propagation .:‬‬
‫هنگامي که به ‪ C‬مقدار ‪ false‬داده شود بند )‪ (C  A‬يک بند واحد مي شود‪.‬‬
‫اگر عبارت ‪ CNF‬فقط شامل بندهاي هورن باشد ‪ DPLL‬با زنجيره پيش رو برابر است‪.‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫الگوريتم‪DPLL‬‬
‫• رفتار ‪ DPLL‬در اين پايگاه دانش متناظر با رفتار ‪ FC‬است‪.‬‬
‫‪69‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫الگوريتم‪DPLL‬‬
‫‪70‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫الگوريتم ‪WalkSAT‬‬
‫• الگوريتم جستجوي محلي و ناكامل‬
‫• در هر تکرار يک بند ارضا نشده را انتخاب مي کند و يک سمبول آن را‬
‫برمي گزيند تا برعکس کند‪.‬‬
‫• براي انتخاب سمبول براي برعکس کردن به صورت تصادفي از يکي از‬
‫دو راه‬
‫• يک گام حداقل تناقض که تعداد بندهاي ارضا نشده در حالت جديد را حداقل ميکند‬
‫• يک گام راه رفتن تصادفي که سمبول را به صورت تصادفي انتخاب ميکند‬
‫• تابع ارزيابي‪ :‬هيوريستيك حداقل تناقض(‪ )min-conflict‬براي كمينه كردن‬
‫تعداد بندهاي ارضاء نشده‬
‫• تعادل ميان ميزان حريصانه بودن و تصادفي بودن‬
‫• اگر الگوريتم مدلي را بازگرداند جمله ورودي ارضا پذير است‬
‫• اگر الگوريتم ‪ failure‬را بازگرداند نمي توانيم تعيين کنيم که ايا جمله‬
‫ارضاناپذير است يا الزم است وقت بيشتري به الگوريتم بدهيم‪.‬‬
‫‪71‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫الگوريتم‬
‫‪72‬‬
‫‪WalkSAT‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مسائل سخت ارضا پذيري‬
‫جمالت ‪ 3-CNF‬تصادفي را در نظر بگيريد‪ ،‬مثال‪:‬‬
‫)‪(D  B  C)  (B  A  C)  (C  B  E)  (E  D  B‬‬
‫)‪ (B  E  C‬‬
‫•‬
‫•‬
‫•‬
‫•‬
‫‪ 32‬انتساب ممکن و ‪ 16‬مدل – به طور متوسط دو حدس كافي‬
‫مي باشد (براي يافتن مدل)‬
‫تعداد بندها= ‪m‬‬
‫تعداد سمبول ها=‪n‬‬
‫به نظر مي رسد مسائل سخت نزديك ‪m/n = 4.3‬باشند (نقطه‬
‫بحراني)‬
‫‪73‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مسائل سخت ارضا پذيري‬
‫‪n=50‬‬
‫‪74‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مسائل سخت ارضا پذيري‬
‫• ميانه زمان اجرا براي ‪ 100‬جمله ‪ 3-CNF‬ارضاء پذير‪،‬‬
‫‪n=5075‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مسائل سخت ارضا پذيري‬
‫• سه نكته واضح در شكل قبل‪:‬‬
‫• مسائل نزديك نقطه بحراني سخت تر از ديگر مسائل تصادفي‬
‫هستند‪.‬‬
‫• حتي در مسائل سخت‪ ،‬الگوريتم ‪ DPLL‬نسبتا كارآمد است – چند‬
‫هزار مرحله به طور ميانگين در مقايسه با ‪1015≈250‬جدول‬
‫درستي‪.‬‬
‫• در اين محدوده‪ ،‬الگوريتم ‪ WalkSAT‬بسيار سريعتر از‪ DPLL‬مي‬
‫باشد‪.‬‬
‫• اين نتايج فقط به مسائلي که به صورت تصادفي ايجاد شده‬
‫اند مربوط مي باشد با اين حال در عمل ‪ WalkSAT‬و‬
‫‪76‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫الگوريتم هاي وابسته در حل مسائل واقعي بسيار مفيد‬
‫عامل هاي مبتني بر استنتاج در دنياي ‪wumpus‬‬
‫• يك عامل دنياي ومپوس با استفاده از منطق گزاره اي‪:‬‬
‫‪P1,1‬‬
‫‪W1,1‬‬
‫)‪Bx,y  (Px,y+1  Px,y-1  Px+1,y  Px-1,y‬‬
‫)‪Sx,y  (Wx,y+1  Wx,y-1  Wx+1,y  Wx-1,y‬‬
‫‪W1,1  W1,2  …  W4,4‬‬
‫حداقل يک ومپوس وجود دارد‬
‫‪W1,1  W1,2‬‬
‫حداکثر يک ومپوس وجود دارد‬
‫‪W1,1  W1,3‬‬
‫براي هر دو مربع يکي از آنها بايد‬
‫…‬
‫خالي از ومپوس باشد‪ n(n-1)/2 .‬جمله‬
‫• ‪ 64‬سمبول گزاره اي متفاوت‬
‫• ‪ 155‬جمله‬
‫‪77‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫عامل هاي مبتني بر استنتاج در دنياي ‪wumpus‬‬
‫‪78‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫محدوديت هاي منطق گزاره اي‬
‫• به طور كلي منطق گزاره اي از قدرت بيان كافي‬
‫برخوردار نيست‪:‬‬
‫– براي هر مربع شامل جمالالت “فيزيكي” آن مربع‬
‫– براي هر زمان ‪ t‬و هر مکان ]‪[x,y‬‬
‫‪Lx,y  FacingRightt  Forwardt  Lx+1,y‬‬
‫– رشد سريع تعداد بندها (‪ )clause‬ها‬
‫‪79‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬

similar documents