Prolog

  • November 2019
  • PDF

This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA


Overview

Download & View Prolog as PDF for free.

More details

  • Words: 2,737
  • Pages: 51
‫برنامه نويسی‬ ‫پرولوگ‬ ‫& ‪Fol‬‬

‫صابر اميرنوين‬

‫مقدمه‬ ‫• اشياء داده ای ساده‬ ‫– اتم ها ( ثابت های غير عددی)‬ ‫– اعداد‬ ‫– متغيرها‬

‫•‬ ‫•‬ ‫•‬ ‫•‬ ‫•‬ ‫•‬ ‫‪2‬‬

‫اشياء ساخت يافته‬ ‫تطابق‬ ‫معنای توصيفی يک برنامه‬ ‫معنای رويه ای يک برنامه‬ ‫ارتباط معنای توصيفی و رويه ای يک برنامه‬ ‫تغيي ر معنای روي ه ای توس ط تغيي ر دادن ترتيب‬ ‫فراکردها و اهداف‬

‫مقدمه‬ ‫• مکانيزم های پايه ای در پرولوگ‬ ‫– فراکردهای پرولوگ (‪)Clauses‬‬ ‫– حقايق (‪)Facts‬‬ ‫– قوانين(‪)Rules‬‬ ‫– رويه ها (‪)procedures‬‬

‫• مکانيزم عقبگرد در پرولوگ (‪)backtracking‬‬ ‫• تفاوت معنای توصيفی و رويه ای يک برنامه‬

‫تعريف روابط بوسيله حقايق‬ ‫• پرولوگ يک زبان برنامه نويسی برای محاسبات نمادين و‬ ‫غير عددی می باشد‪.‬‬ ‫• پرولوگ برای حل مسائلی که شامل اشياء و روابط ميان‬ ‫آنها می باشند بسيار مناسب می باشد‪.‬‬ ‫• مثال ‪ :‬روابط خانوادگی‬ ‫– اين حقيقت که ‪ Tom‬پدر ‪ Bob‬است را در پرولوگ به صورت‬ ‫زير نمايش می دهيم‪:‬‬

‫‪parent(tom, bob).‬‬ ‫در اينجا ‪ parent‬نام رابطه و ‪ Tom‬و ‪ Bob‬آرگومانهای رابطه می‬ ‫باشند‪.‬‬ ‫توجه‪ :‬اسامی خاص مانند ‪ tom‬بايد با يک حرف کوچک الفبا نوشته‬ ‫شوند‪.‬‬

‫تعريف روابط بوسيله حقايق‬ .‫• اين برنامه از شش فراکرد تشکيل شده است‬ .‫ می باشد‬parent ‫• هر فراکرد يک نمونه از رابطه‬ parent)tom, bob(.

pam

tom

parent)pam, bob(. bob

parent)tom, liz(.

liz

parent)bob, ann(. parent)bob, pat(. parent)pat, jim(.

ann

pat

jim

‫تعريف روابط بوسيله حقايق‬ ‫آيا ‪ Bob‬پدر ‪ Pat‬می باشد؟‬ ‫‪?- parent)bob, pat(.‬‬ ‫‪yes‬‬ ‫اين به صورت يک حقيقت در برنامه ذکر شده است‪.‬‬ ‫‪?- parent)liz, pat(.‬‬ ‫‪no‬‬ ‫در برنامه چنين رابطه ای بيان نشده است‪.‬‬ ‫‪?- parent)tom, ben(.‬‬ ‫‪no‬‬ ‫برنامه نام ‪ Ben‬را نشنيده است‪.‬‬

‫تعريف روابط بوسيله حقايق‬ ‫چه کسی والد ‪ Liz‬می باشد؟‬ ‫‪?- parent)X, liz(.‬‬ ‫پرولوگ در پاسخ به اين پرسش سعی می کند برای ‪X‬‬ ‫مقداری بيابد که عبارت بال درست باشد‪.‬‬ ‫‪X = tom‬‬ ‫فرزندان ‪ Bob‬چه کسانی می باشند؟‬ ‫‪?- parent)bob, X(.‬‬ ‫;‪X = ann‬‬ ‫مکانيزمی برای درخواست‬ ‫;‪X = pat‬‬ ‫پاسخهای بيشتر‬ ‫‪no‬‬

‫تعريف روابط بوسيله حقايق‬ ‫چه کسانی والد چه کسانی می باشند؟‬ ‫‪?- parent)X, Y(.‬‬ ‫‪X = pam‬‬ ‫;‪Y = bob‬‬ ‫‪X = tom‬‬ ‫;‪Y = bob‬‬ ‫‪X = tom‬‬ ‫;‪Y = liz‬‬ ‫…‬

‫تعريف روابط بوسيله حقايق‬ ‫جد ‪ Jim‬چه کسی است؟‬

‫‪?- parent)Y, jim(, parent)X, Y(.‬‬ ‫‪X = bob‬‬ ‫‪Y = pat‬‬ ‫اگر ترتيب دو درخواست را در پرسش بال عوض کنيم‬ ‫معنای منطقی ثابت باقی می ماند و بنابراين پرسش‬ ‫زير همان پاسخ بال را توليد می کند‪.‬‬ ‫‪?- parent)X, Y(, parent)Y, jim(.‬‬

‫تعريف روابط بوسيله حقايق‬ ‫نوه های ‪ Tom‬چه کسانی هستند؟‬ ‫‪?- parent)tom, X(, parent)X, Y(.‬‬ ‫‪X = bob‬‬ ‫;‪Y = ann‬‬ ‫‪X = bob‬‬ ‫‪Y = pat‬‬

‫تعريف روابط بوسيله حقايق‬ ‫آيا ‪ Ann‬و ‪ Pat‬والد مشترکی دارند؟‬ ‫کنيم ‪ X‬باشد)‬ ‫‪?- parent)X, ann(, parent)X, pat(.‬‬ ‫‪X = bob‬‬

‫تعريف روابط بوسيله حقايق‬ ‫•‬ ‫•‬ ‫•‬ ‫•‬ ‫•‬ ‫•‬

‫در پرولوگ تعريف روابط به سادگی توسط يک ‪-n‬تايي‬ ‫از اشياء که رابطه را ارضاء می کنند‪،‬انجام می شود‪.‬‬ ‫کاربر به سادگی می تواند از پرولوگ در باره روابط‬ ‫تعريف شده در برنامه پرس و جو کند‪.‬‬ ‫يک برنامه پرولوگ از فراکردها تشکيل می شود‪.‬‬ ‫پرسش ها شامل يک يا چند هدف می باشند‪ ،‬مانند‪:‬‬ ‫(‪parent)X, ann(, parent)X, pat‬‬ ‫اگر پاسخ پرولوگ به يک پرسش مثبت باشد در اين‬ ‫صورت می گوييم پرسش قابل ارضاء و گرنه غير‬ ‫قابل ارضاء می باشد‪.‬‬ ‫اگر پرسشی دارای پاسخهای متعددی باشد‪ ،‬پرولوگ‬ ‫هر تعداد پاسخی را که کاربر بخواهد پيدا می کند‪.‬‬

‫تعريف روابط بوسيله قوانين‬ ‫برنام ه رواب ط خانوادگ ی را ب ا افزودن اطلعاتی مثل‬ ‫درباره جنسيت افراد می توان تعميم داد‪:‬‬ ‫‪female)pam(.‬‬ ‫‪male)tom(.‬‬ ‫‪male)bob(.‬‬ ‫‪female)liz(.‬‬ ‫‪female)pat(.‬‬ ‫‪female)ann(.‬‬ ‫‪male)jim(.‬‬ ‫روابط يکتايي و دوتايي‪.‬‬

‫تعريف روابط بوسيله قوانين‬ ‫• تعريف رابطه ‪ ( offspring‬عکس رابطه ‪)parent‬‬ ‫اضافه کنيم‪ :‬مثل‬ ‫‪offspring)liz, tom(.‬‬ ‫‪offspring)Y, X( :- parent)X, Y(.‬‬ ‫يعنی بازاء هر ‪ X‬و ‪ ، Y‬اگر ‪ X‬والد ‪ Y‬باشد‪ ،‬آنگاه‬ ‫‪ Y‬فرزند ‪ X‬می باشد‪.‬‬

‫تعريف روابط بوسيله قوانين‬ ‫• تفاوت ميان حقايق و قوانين‪:‬‬ ‫– ي ک حقيق ت چيزی اس ت ک ه همواره و بدون هي چ قيد و‬ ‫شرطی درست می باشد‪.‬‬ ‫– از طرف ديگر يک قانون چيزهايی را بيان می کند که برای‬ ‫درستی آنها بايد برخی از شرايط ارضاء شوند‪.‬‬

‫• بنابراين قوانين از دوقسمت تشکيل می شوند‪:‬‬ ‫– بخش شرط (‪ )condition part‬و‬ ‫– بخش نتيجه (‪.)conclusion part‬‬ ‫‪offspring)Y, X( :- parent)X, Y(.‬‬ ‫‪head‬‬ ‫‪body‬‬

‫تعريف روابط بوسيله قوانين‬ ‫آيا ‪ Liz‬فرزند ‪ Tom‬است؟‬ ‫‪?- offspring) liz, tom(.‬‬ ‫نحوه پاسخ دهی پرولوگ‪:‬‬ ‫چون قانون اسليد قبل بازاء هر ‪ X‬و ‪ Y‬قابل اعمال است‪ ،‬پس بر‬ ‫اشياء خاص ‪ Liz‬و ‪ Tom‬نيز قابل اعمال می باشد‪ .‬برای اعمال‬ ‫اين قانون بر اين اشياء خاص‪ ،‬بايد ‪ Y‬را با ‪ Liz‬و ‪ X‬را با ‪Tom‬‬ ‫در قانون فوق جايگزين کنيم( نمونه دهی)‬ ‫‪X = tom , Y = liz‬‬ ‫پس از جايگذاری‪ ،‬ي ک نمون ه خاص از قانون را ب ه شک ل زير‬ ‫بدست می آوريم‪:‬‬ ‫(‪offspring)liz, tom( :- parent)tom, liz‬‬ ‫اکنون پرولوگ سعی می کند که دريابد آيا بخش شرط قانون بال‬ ‫درست است يا خير‪ .‬چون بخش شرط درست است ( با توجه‬ ‫به حقايق موجود در برنامه)‪ ،‬بنابراين پاسخ پرولوگ ‪ yes‬خواهد‬ ‫بود‪.‬‬

‫تعريف روابط بوسيله قوانين‬ :‫تعريف رابطه مادری‬ mother)X, Y( :- parent)X, Y(, female)X(. ‫ در قانون فوق علمت ويرگول به معنای ترکيب‬:‫توجه‬ .‫) شرايط می باشد‬And( ‫عطفی‬ female

parent

offspring Y

X

X

X

parent

mother

parent Y

Y

parent grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

Z

grandparent

‫تعريف روابط بوسيله قوانين‬ ‫نحوه قالب بندی برنامه ها‬ ‫‪grandparent(X, Z) :- parent(X, Y), parent(Y, Z).‬‬

‫نحوه مناسب نوشتن قوانين‪:‬‬ ‫‪grandparent(X, Z) :‬‬‫‪parent(X, Y),‬‬ ‫‪parent(Y, Z).‬‬

‫تعريف روابط بوسيله قوانين‬ )sister(‫تعريف رابطه خواهری‬ sister)X, Y( :parent)Z, X(, parent)Z, Y(, female)X(.

Z

female

?- sister)ann, pat(. yes ?- sister)X, pat(. X = ann; X = pat

parent

parent X

sister

Y

‫تعريف روابط بوسيله قوانين‬ ‫تصحيح رابطه خواهری‬ sister)X, Y( :parent)Z, X(, parent)Z, Y(, female)X(, different(X, Y).

‫تعريف روابط بوسيله قوانين‬ ‫• نکات مهم‪:‬‬ ‫– تعميم برنامه های پرولوگ با افزودن فراکردهای جديد‪.‬‬ ‫– انواع فراکردها‪:‬‬ ‫• حقاي ق ‪ :‬بيانگ ر چيزهاي ي ک ه همواره و بدون شرط درس ت می‬ ‫باشند‪.‬‬ ‫• قوانين‪ :‬بيانگر چيزهايي که درستی آنها بستگی به برخی شرايط‬ ‫دارد‪.‬‬ ‫• پرسش ها‪ :‬وسيله ای که کاربر با آن می تواند از برنامه بپرسد چه‬ ‫چيزهايي درست هستند‪.‬‬

‫– فراکردها از دوقسمت تشکيل می شوند ( سرآيند و بدنه)‬ ‫• حقايق‪ :‬قسمت بدنه آنها تهی‬ ‫• پرسش ها‪ :‬فقط دارای بدنه‬ ‫• قوانين‪ :‬دارای هر دو قسمت‬

‫قوانين بازگشتی‬ )predecessor( ‫تعريف رابطه اجدادی‬ X

X

parent

predecessor

parent

Z

parent

predecessor

parent Z

‫قوانين بازگشتی‬ :predecessor ‫تعريف رابطه‬ predecessor)X, Z( :parent)X, Z(. predecessor)X, Z( :parent)X, Y(, parent)Y, Z(. predecessor)X, Z( :parent)X, Y1(, parent)Y1, Y2(, parent)Y2, Z(. …

‫قوانين بازگشتی‬ :‫ به صورت بازگشتی‬predecessor ‫تعريف‬ predecessor)X, Z( :parent)X, Z(.

%pr1

predecessor)X, Z( :parent)X, Y(, predecessor)Y, Z(.

%pr2

?- predecessor)pam, X(. X = bob; X = ann; X = pat; X = jim

‫قوانين بازگشتی‬ ‫تعريف رويه (‪:)procedure‬‬ ‫مانن د رابط ه ‪ predecessor‬در مثال روابط‬ ‫خانوادگ ی ک ه توس ط دو فراکرد تعريف شده‬ ‫است‪.‬‬ ‫انواع توضيحات (‪ )comment‬در پرولوگ‪:‬‬ ‫‪/* this is a comment */‬‬ ‫‪% this is also a comment‬‬

‫نحوه پاسخ گويی به پرسشها در‬ ‫پرولوگ‬ ‫در پرولوگ ه ر پرس ش شام ل ي ک ي ا چن د هدف می‬ ‫باشد‪.‬‬ ‫پرولوگ برای پاسخ گويی به پرسشها سعی می کند اين‬ ‫اهداف را ارضاء کند‪.‬‬ ‫ارضاء هدف يعنی اينکه نشان دهيم هدف درست است‬ ‫( با اين فرض که روابط موجود در برنامه درست می‬ ‫باشند)‪.‬‬ ‫ارضاء هدف يعنی اينکه نشان دهيم هدف مورد نظر به‬ ‫طور منطق ی از حقاي ق و قواني ن موجود در برنامه‬ ‫می کند‪.‬‬ ‫اگر پرسشی شامل متغير باشد‪ ،‬پرولوگ بايد دريابد که‬ ‫کدام اشياء خاص ( به جای متغيرها) اهداف را برآورده‬

‫نحوه پاسخ گويی به پرسشها در‬ ‫پرولوگ‬ :‫مثال‬ fallible)X( :- man)X(. man)socrates(. ?- fallible)socrates(. yes

‫نحوه پاسخ گويی به پرسشها در‬ ‫پرولوگ‬ ‫(‪predecessor)tom, pat‬‬ ‫‪predecessor)X, Z( :- parent)X, Z(.‬‬ ‫‪X = tom, Z= pat‬‬ ‫هدف جديد‪:‬‬ ‫(‪parent)tom, pat‬‬ ‫چون هي چ فراکردی در برنام ه وجود ندارد ک ه بخش‬ ‫سرآيند آن با اين هدف تطابق (‪ )match‬داشته باشد‪،‬‬ ‫بنابراين اين هدف مردود می شود‪.‬‬ ‫اکنون پرولوگ به سمت هدف اول عقبگرد می کند تا‬ ‫روش ديگری برای ارضای آن پيدا کند‪ .‬بنابراين قانون‬ ‫دوم ‪ predecessor‬را امتحان می کند‪.‬‬

‫نحوه پاسخ گويی به پرسشها در‬ ‫پرولوگ‬ ‫‪predecessor)X, Z( :‬‬‫‪parent)X, Y(,‬‬ ‫‪predecessor)Y, Z(.‬‬ ‫مانند قبل متغيرهای ‪ X‬و ‪ Z‬با ‪ tom‬و ‪ pat‬نمونه دهی می شوند‪:‬‬ ‫‪X = tom, Z = pat‬‬ ‫اکنون هدف اص لی يعن ی ‪ )predecessor)tom, pat‬با دوهدف جديد‬ ‫زير جايگزين می شود‪:‬‬ ‫‪parent)tom, Y(,‬‬ ‫(‪predecessor)Y, pat‬‬ ‫اکنون پرولوگ سعی می کند اين دو هدف را به ترتيب نوشتن‬ ‫آنها ارضاء کند‪.‬‬

‫نحوه پاسخ گويی به پرسشها در‬ ‫پرولوگ‬ ‫هدف اول يعنی ‪ )parent)tom, Y‬به راحتی با يک حقيقت برنامه‬ ‫يعن ی ‪ )parent)tom, bob‬تطاب ق م ی ياب د‪ ،‬بنابراين هدف اول‬ ‫بانمونه دهی ‪ Y=bob‬ارضاء می شود و هدف دوم به هدف زير‬ ‫تبديل می شود‪:‬‬ ‫(‪predecessor)bob, pat‬‬ ‫دوباره برای ارضاء اين هدف قانون اول ‪ predecessor‬امتحان می‬ ‫شود‪ ،‬يعنی قانون زير‪:‬‬ ‫‪predecessor)X’, Z’( :‬‬‫‪parent)X’, Z’(.‬‬ ‫از تطابق هدف و بخش سرآيند اين قانون نمونه دهی زير بدست‬ ‫می آيد‪:‬‬ ‫‪X’ = bob, Z’ = pat‬‬ ‫و هدف فعلی با هدف جديد زير جايگزين می شود‪:‬‬ ‫(‪parent)bob, pat‬‬ ‫اين هدف بلفاصله قابل ارضاء می باشد‪ .‬و بنابراين هدف اصلی‬

‫نحوه پاسخ گويی به پرسشها در‬ ‫پرولوگ‬ predecessor(tom, pat) by rule pr1 parent(tom, pat) no

by rule pr2 parent(tom, Y) predecessor(Y, pat) Y = bob

by fact parent(tom, bob)

predecessor(bob, pat) by rule pr1 parent(bob, pat) yes

‫اشياء داده ای‬ data objects

simple objects

constants

atoms

structures

variables

numbers 32

‫اشياء داده ای‬ ‫• در پرولوگ نوع يک شيء توسط ساختار گرامری آن‬ ‫مشخص می شود‪.‬‬ ‫– متغيرها با يک حرف الفبايی بزرگ شروع می شوند‪.‬‬ ‫– اتم ها با يک حرف الفبايی کوچک شروع می شوند‪.‬‬

‫• در پرولوگ ات م ه ا و متغي ر ه ا رشت ه هايي از‬ ‫کاراکترهای زير می باشند‪:‬‬ ‫–‬ ‫–‬ ‫–‬ ‫–‬ ‫‪33‬‬

‫حروف بزرگ ‪A ،B ، ... ،Z‬‬ ‫حروف کوچک ‪a ،b ، ... ،z‬‬ ‫ارقام ‪9 ، ... ،1 ،0‬‬ ‫کاراکتر های خاص مانند ‪~ _ & . : = > < / * - +‬‬

‫ساختارها‬ P1 = point)1, 1( P2 = point)2, 3( S = seg)P1, P2( = seg)point)1, 1(, point)2, 3( ( T = triangle)point)4, 2(, point)6, 4(, point)7, 1( ( triangle

point

point

4

2

6

point

4

7

1

34

‫تطابق‬ ‫• عم ل تطاب ق مهمتري ن عمل ی اس ت ک ه برروی عبارت ها در‬ ‫پرولوگ انجام می گيرد‪.‬‬ ‫• گوييم دو عبارت داده شده‪ ،‬باهم تطابق دارند اگر‪:‬‬

‫شوند که بعد از جايگزينیعبارت ها با هم يکسان شوند‪ .‬مثل‪:‬‬ ‫‪date)D, M, 2001( ,‬‬ ‫(‪date)D1, may, Y1‬‬ ‫‪D = D1‬‬ ‫دو عبارت بال با هم تطابق دارند اگر‪:‬‬ ‫‪M = may‬‬ ‫‪Y1 = 2001‬‬ ‫‪35‬‬

‫تطابق‬ ‫• توججه ‪ :‬عم ل تطاب ق در پرولوگ هميش ه منج ر به‬ ‫می شود‪.‬‬ ‫عمومی ترين نمونه دهی ها‬ ‫‪?- date)D, M, 2001( = date)D1, may, Y1(,‬‬ ‫‪date)D, M, 2001( = date)15, M, Y(.‬‬ ‫‪D = 15‬‬ ‫‪M = may‬‬ ‫‪D1 = 15‬‬ ‫‪Y1 = 2001‬‬ ‫‪Y = 2001‬‬ ‫‪36‬‬

‫تطابق‬ ‫• الگوريتم تطابق دو عبارت ‪:S, T‬‬ ‫تطابق هستند که هر دو شیء يکسانی باشند‪.‬‬ ‫انطباق هستند و ‪ S‬با ‪ T‬نمونه دهی می شود و‬ ‫برعکس‪.‬‬ ‫تطابق می يابند که‪:‬‬ ‫‪ 37‬و‬

‫تطابق‬ ‫ تعريف خاصيت عمودی و افقی برای پاره خط ها‬: ‫مثال‬ vertical(seg(point(X, Y), point(X, Y1) ) ). horizontal(seg(point(X, Y), point(X1, Y) ) ).



?- vertical)seg)point)1, 1(, point)1, 2( ( (. yes ?- vertical)seg)point)1, 1(, point)2, Y( ( (. no ?- horizontal)seg)point)1, 1(, point)2, Y( ( (. Y=1 ?- vertical)seg)point)2, 3(, P(. P = point)2, H53( ?- vertical)S(, horizontal)S(. S = seg)point)X, Y(, point)X, Y( ( 38

‫معنای توصيفی برنامه ها‬ ‫‪• P :- Q, R.‬‬ ‫معنای توص يفی‪ P :‬درس ت اس ت اگر ‪ Q‬و ‪R‬‬ ‫درست باشند‪.‬‬ ‫معنای رويه ای‪:‬‬

‫زير مسأله ‪ R‬را حل کن‪.‬‬ ‫بنابراين تفاوت در اهميت ترتيب بخش شرايط‬ ‫‪ 39‬می باشد‪.‬‬

‫معنای توصيفی برنامه ها‬ ‫‪• P :- Q; R.‬‬ ‫معنای توصيفی‪ P :‬درست است اگر ‪ Q‬درست باشد يا ‪ R‬درست‬ ‫باشد‪.‬‬ ‫معادل با‪:‬‬ ‫‪P :- Q.‬‬ ‫‪P :- R.‬‬ ‫اولويت کاما از سمی کالن بيشتر است‪:‬‬ ‫‪P :- Q, R; S, T, U.‬‬ ‫معادل است با‪:‬‬ ‫‪P :- )Q, R(; )S, T, U(.‬‬ ‫يا‪:‬‬ ‫‪P :- Q, R.‬‬ ‫‪P :- S, T, U.‬‬ ‫‪40‬‬

‫معنای رويه ای برنامه ها‬ ‫• معنای رويه ای چگونگی پاسخ گويی پرولوگ‬ ‫به پرسشها را مشخص می کند‪.‬‬ ‫• بنابراين معنای رويه ای پرولوگ‪ ،‬يک رويه برای‬ ‫اجرای ليستی از اهداف ( پرسش) در رابطه با‬ ‫‪.‬‬ ‫باشد‬ ‫می‬ ‫برنامه‬ ‫يک‬ ‫‪program‬‬ ‫‪failure\success indicator‬‬

‫‪execute‬‬ ‫‪instantiation of variables‬‬ ‫‪41‬‬

‫‪goal list‬‬

‫مسأله ميمون و موز‬ ‫• مسجأله ‪ :‬يک ميمون در کنار در ورودی اتاقی قرار‬ ‫دارد‪ .‬در وس ط اتاق ي ک موز از سقف آويزان‬ ‫است‪.‬ميمون گرسنه است و می خواهد خودش را به‬ ‫موز برس اند‪ ،‬ام ا دس تش ب ه آ ن نم ی رسد‪ .‬در کنار‬ ‫پنجره يک جعبه وجود دارد که ميمون می تواند از آن‬ ‫اس تفاده کند‪ .‬ميمون م ی توان د اعمال زير را انجام‬ ‫دهد‪:‬‬ ‫–‬ ‫–‬ ‫–‬ ‫–‬

‫کف اتاق راه برود‪.‬‬ ‫از جعبه بال برود‪.‬‬ ‫جعبه را به اين طرف و آن طرف جابجا کند‪.‬‬ ‫موز رابگيرد به شرطی که روی جعبه باشد و جعبه نيز در‬ ‫وسط اتاق و زير موز باشد‪.‬‬

‫• سوال اي ن ا ست ک ه آي ا ميمون م ی توان د به موزش‬ ‫برسد يا خير و اگر می تواند کدام دنباله از اعمال را‬ ‫بايد انجام دهد؟‬

‫مسأله ميمون و موز‬ ‫• فرموله سازی مسأله ‪ :‬در اين مسأله می توان دنيا را در‬ ‫هر لحظ ه توس ط حالت ی بيان کرد ک ه درآ ن موقعيت اشياء‬ ‫مشخ ص شده باشند‪ .‬حال ت م ی توان د ب ا زمان ( انجام عمل)‬ ‫تغيير کند‪.‬‬ ‫(‪state)P1, P2, P3, H‬‬ ‫موقعيت جعبه موقعيت عمودی موقعيت افقی ميمون‬ ‫داشتن‪/‬نداشتن موز‬ ‫ميمون‬

‫• حالت اوليه‪:‬‬ ‫(‪state)atdoor, onfloor, atwindow, hasnot‬‬ ‫• فرموله سازی هدف‪:‬‬ ‫(‪state)_, _, _, has‬‬

‫مسأله ميمون و موز‬ : ‫• فرموله سازی عمليات‬ move)State1, Move, State2(

move)state)middle, onbox, middle, hasnot(, grasp, state)middle, onbox, middle, has( (.

‫مسأله ميمون و موز‬ : ‫• فرموله سازی عمليات‬ move)State1, Move, State2(

move)state)Pos1, onfloor, Box, Has(, walk)Pos1, Pos2(, state)Pos2, onfloor, Box, Has( (.

‫مسأله ميمون و موز‬ : ‫• فرموله سازی عمليات‬ move)State1, Move, State2(

move)state)Pos1, onfloor, Pos1, Has(, push)Pos1, Pos2(, state)Pos2, onfloor, Pos2, Has( (.

‫مسأله ميمون و موز‬ : ‫• فرموله سازی عمليات‬ move)State1, Move, State2(

move)state)Pos, onfloor, Pos, Has(, climb, state)Pos, onbox, Pos, Has( (.

‫مسأله ميمون و موز‬ ‫• پرسش اصلی که برنامه بايد پاسخ دهد اين است که‬ ‫آيا دنباله ای از عمليات وجود دارند که ميمون را از‬ ‫( نهايي)‬ ‫حال ت اولي ه مس أله ب ه حال ت هدف‬ ‫برسانند‪.‬‬ ‫(‪canget)State‬‬ ‫که می تواند به صورت زير بيان شود‪:‬‬ ‫‪canget)state)_, _, _, has( (.‬‬ ‫‪canget)State1( :‬‬‫‪move)State1, Move, State2(,‬‬ ‫‪canget)State2(.‬‬

‫)مسأله ميمون و موز( برنامه کامل‬ move)state)middle, onbox, middle, hasnot(, grasp, state)middle, onbox, middle, has( (. move)state)Pos, onfloor, Pos, Has(, climb, state)Pos, onbox, Pos, Has( (. move)state)Pos1, onfloor, Pos1, Has(, push)Pos1, Pos2(, state)Pos2, onfloor, Pos2, Has( (. move)state)Pos1, onfloor, Box, Has(, walk)Pos1, Pos2(, state)Pos2, onfloor, Box, Has( (. canget)state)_, _, _, has( (. canget)State1( :move)State1, Move, State2(, canget)State2(.

‫مسأله ميمون و موز‬ :‫• حل مسأله‬ ?- canget)state)atdoor, onfloor, atwindow, hasnot( (. yes :‫دنباله عمليات‬ walk)atdoor, atwindow(, push)atwindow, middle(, climb, grasp

‫ترتيب فراکردها و اهداف‬ ‫• خطر حلقه بی پايان‬ ‫‪P :- P.‬‬ ‫اي ن فراکرد از لحاظ معنای توص يفی کامل درس ت است ( ‪P‬‬ ‫درست است اگر ‪ P‬درست باشد)‪.‬‬ ‫اما از لحاظ رويه ای مشکل ايجاد می کند ( حلقه بی پايان)‬ ‫در برنام ه ميمون و موز عمليات را ب ه ترتي ب زي ر در برنامه‬ ‫نوشتيم‪:‬‬ ‫گرفتن موز‪ ،‬بالرفتن‪ ،‬جابه جا کردن جعبه و راه رفتن‬ ‫اين ترتيب اولويت اعمال مختلف را برای ميمون مشخص می‬ ‫کنند‪ ،‬يعنی مثل ميمون بين راه رفتن و گرفتن موز دومی را‬ ‫ترجيح می دهد‪ .‬اين اولويت ها به ميمون در حل مسأله کمک‬ ‫می کنند‪ .‬حال اگ ر ترتي ب عمليات را عوض کني م و عمل راه‬ ‫رفتن را بالتر از بقيه اعمال در برنامه قراردهيم ميمون تا ابد‬ ‫در اتاق قدم خواهد زد و هيچگاه به موز نمی رسد ( اگر زنده‬ ‫بماند!) ‪.‬‬

Related Documents

Prolog
October 2019 28
Prolog
November 2019 24
Prolog
June 2020 14
Prolog
November 2019 28
Subprogramacion Prolog
December 2019 21
Prolog Intro
May 2020 8