حل مسئله با جستجو PDF

‫حل مسئله با جستجو‬ ‫جستجوی ناآگاهانه‬ ‫‪‬ناآگاهی اين است که الگوريتم هيچ اطالعاتی غير از تعريف مسلله در اختيار ندارد‬ ‫‪‬اين الگوريتمها فقط ميتواند جانشينهايي را توليد و هدف را از غير هدف تشخيص دهند‬ ‫‪ ‬راهبردهايي که تشخيص ميدهد يک حالمت غيمر همدف نسمبت بمه گمر...

‫حل مسئله با جستجو‬ ‫جستجوی ناآگاهانه‬ ‫‪‬ناآگاهی اين است که الگوريتم هيچ اطالعاتی غير از تعريف مسلله در اختيار ندارد‬ ‫‪‬اين الگوريتمها فقط ميتواند جانشينهايي را توليد و هدف را از غير هدف تشخيص دهند‬ ‫‪ ‬راهبردهايي که تشخيص ميدهد يک حالمت غيمر همدف نسمبت بمه گمره غيمر همدف ديگمر‪ ،‬اميمد‬ ‫بخش تر است‪ ،‬جست و جوی آگاهانه يا جست و جوی اکتشافي ناميده ميشود‪.‬‬ ‫راهبردها‬ ‫‪‬جست و جوی هزينه يکنواخت‬ ‫‪‬جست و جوی عرضی‬ ‫‪‬جست و جوی عمقی محدود‬ ‫‪‬جست و جوی عمقی‬ ‫‪‬جست و جوی دو طرفه‬ ‫‪‬جست و جوی عميق کننده تکراری‬ ‫‪77‬‬  ‫حل مسئله با جستجو‬ ‫جستجوی عرضی‬ ‫در اين استراتژي که بسيار سيستماتيک است‪ ،‬ابتدا گره ريشه‪ ،‬و سپس تمام‬ ‫گرههاي ديگر گسترش داده ميشوند‪.‬‬ ‫به عبارت کليتر‪ ،‬تمام گرههاي عميق ‪ ،d‬قبل از گرههاي عميق ‪ d+1‬گسترش‬ ‫داده ميشوند‪.‬‬ ‫مزايا‪:‬جستجوي سطحي‪ ،‬کامل و بهينه ميباشد زيرا هزينه مسير‪ ،‬يک تابع‬ ‫کاهشنيابنده از عمق گره است‪.‬‬ ‫معايب‪:‬مرتبه زماني )‪ O(bd+1‬مي باشد که نمايي است‪.‬‬ ‫نياز به حافظه زياد‪.‬‬  ‫حل مسئله با جستجو‬ ‫جستجوی عرضی‬ ‫‪A‬‬ ‫‪B‬‬ ‫‪C‬‬ ‫‪D‬‬ ‫‪E‬‬ ‫‪F‬‬ ‫‪G‬‬ ‫‪H‬‬ ‫‪I‬‬ ‫‪J‬‬ ‫‪K‬‬ ‫‪L‬‬ ‫‪M‬‬ ‫‪N‬‬ ‫‪O‬‬ ‫‪P‬‬ ‫‪Q‬‬ ‫‪79‬‬  ‫حل مسئله با جستجو‬ ‫جستجوی عرضی‬ ‫کامل بودن‪ :‬بله‬ ‫بله (مشروط)‬ ‫بهينگی‪ :‬بله (مشروط)‬ ‫در صورتی بهينه است که هزينه مسير‪ ،‬تابعی غير نزولی از عمق‬ ‫گره باشد‪(.‬مثل وقتي که فعاليتها هزينه يکسانی دارند)‬ ‫‪d+1‬‬ ‫‪O(b‬‬ ‫)‬ ‫پيچيدگي زماني‪:‬‬ ‫) ‪O(b d+1‬‬ ‫پيچيدگی فضا‪:‬‬ ‫‪80‬‬  ‫حل مسئله با جستجو‬ ‫جستجوی هزينه يکنواخت‬ ‫در اين روش گره اي بسط داده مي شود كه هزينه رسيدن به آن حداقل بوده است‪.‬‬ ‫در اين استراتژي‪ ،‬در شرايط عمومي‪ ،‬اولين راه حل‪ ،‬ارزانترين راه نيز هست‪.‬‬ ‫اگر هزينه مسير توسط تابع )‪ g(n‬اندازهگيري شود‪ ،‬در اين صورت جستجوي‬ ‫سطحي همان جستجوي با هزينه يکسان است با‪:‬‬ ‫)‪g(n)=DEPTH(n‬‬  ‫حل مسئله با جستجو‬ ‫جستجوی هزينه يکنواخت‬ ‫اين جستجو گره ‪ n‬را با کمترين هزينه مسير بسط ميدهد‬ ‫‪A‬‬ ‫‪1‬‬ ‫‪3‬‬ ‫‪1‬‬ ‫‪B‬‬ ‫‪C‬‬ ‫‪D‬‬ ‫‪E‬‬ ‫‪F‬‬ ‫‪G‬‬ ‫‪H‬‬ ‫‪I‬‬ ‫‪J‬‬ ‫‪K‬‬ ‫‪L‬‬ ‫‪M‬‬ ‫‪N‬‬ ‫‪O‬‬ ‫‪P‬‬ ‫‪Q‬‬ ‫‪82‬‬  ‫حل مسئله با جستجو‬ ‫جستجوی هزينه يکنواخت‬ ‫کامل بودن‪ :‬بله‬ ‫هزينه هر مرحله بزرگتر يا مساوی يک مقدار ثابت و مثبت ‪ε‬‬ ‫باشد‪(.‬هزينه مسير با حرکت در مسير افزايش مي يابد)‬ ‫بهينگی‪ :‬بله‬ ‫هزينه هر مرحله بزرگتر يا مساوی ‪ ε‬باشد‬ ‫] ‪[C*/‬‬ ‫‪O(b‬‬ ‫)‬ ‫پيچيدگي زماني‪:‬‬ ‫] ‪[C*/‬‬ ‫‪O(b‬‬ ‫)‬ ‫پيچيدگی فضا‪:‬‬ ‫‪83‬‬  ‫حل مسئله با جستجو‬ ‫جستجوی عمقی‬ ‫اين استراتژي‪ ،‬يکي از گرهها را در پالينترين سطح درخت بسط ميدهد؛ اما اگر به‬ ‫نتيجه نرسيد‪ ،‬به سراغ گرههايي در سطوح کم عميقتر ميرود‪.‬‬ ‫مزايا‪:‬‬ ‫اين جستجو‪ ،‬نياز به حافظه نسبتا ً کمي فقط براي ذخيره مسير واحدي از ريشه به يک‬ ‫گره برگي‪ ،‬و گرههاي باقيمانده بسط داده نشده دارد‪.‬‬ ‫پيچيدگي زماني )‪ O(bm‬ميباشد‪.‬به طوريکه ‪ b‬فاکتور انشعاب فضاي حالت‪ ،‬و ‪m‬‬ ‫حداکثر عمق درخت باشد‪.‬‬ ‫معايب‪:‬اگر مسيري را اشتباه طي کند‪ ،‬هنگام پالين رفتن گير ميکند‪.‬‬ ‫جستجوي عمقي نه کامل و نه بهينه است‪.‬‬ ‫در درختهاي با عمق نامحدود و بزرگ اين استراتژي کار نميکند‪.‬‬  ‫حل مسئله با جستجو‬ ‫جستجوی عمقی‬ ‫‪A‬‬ ‫‪2‬‬ ‫‪B‬‬ ‫‪C‬‬ ‫‪D‬‬ ‫‪3‬‬ ‫‪E‬‬ ‫‪F‬‬ ‫‪6‬‬ ‫‪G‬‬ ‫‪H‬‬ ‫‪I‬‬ ‫‪7‬‬ ‫‪4‬‬ ‫‪J‬‬ ‫‪K‬‬ ‫‪L‬‬ ‫‪M‬‬ ‫‪N‬‬ ‫‪O‬‬ ‫‪P‬‬ ‫‪Q‬‬ ‫‪5‬‬ ‫‪85‬‬  ‫حل مسئله با جستجو‬ ‫جستجوی عمقی‬ ‫کاملبودن‪:‬‬ ‫بودن‪:‬خير‬ ‫کامل‬ ‫اگر زير درخت چپ عمق نامحدود داشت و فاقد هر گونه راه حل‬ ‫باشد‪ ،‬جستجو هرگز خاتمه نمي يابد‪.‬‬ ‫بهينگي‪ :‬خير‬ ‫بهينگی‬ ‫‪m‬‬ ‫) ‪O(b‬‬ ‫پيچيدگي زماني‪:‬‬ ‫)‪O(bm‬‬ ‫پيچيدگی فضا‪:‬‬ ‫‪86‬‬  ‫حل مسئله با جستجو‬ ‫جستجوی عمقی محدود‬ ‫اين استراتژي‪ ،‬براي رهايي از دامي که جستجوي عمقي در آن گرفتار ميشد‪ ،‬از‬ ‫يک برش استفاده ميکند‪.‬جستجوي عمقي محدود شده کامل است اما بهينه نيست‪.‬‬ ‫زمان و پيچيدگي فضاي جستجوي عمقي محدودشده‪ ،‬مشابه جستجوي عمقي است‪.‬‬ ‫اين جستجو پيچيدگي زماني )‪ O(bL‬و فضاي )‪ O(bL‬را خواهد داشت‪ ،‬که ‪L‬‬ ‫محدودة عمق است‪.‬‬ ‫در يک درخت جستجوي نمايي‪ ،‬تقريبا ً تمام گرهها در سطح پالين هستند‪ ،‬بنابراين‬ ‫موردي ندارد که سطوح بااليي چندين مرتبه بسط داده شوند‪.‬تعداد بسطها در يک‬ ‫جستجوي عمقي محدود شده با عمق ‪ d‬و فاکتور انشعاب ‪ b‬به قرار زير است‪:‬‬ ‫‪1+b+b^2+…+b^(d-2)+b^(d-1)+b^d‬‬  ‫حل مسئله با جستجو‬ ‫جستجوی عمقی محدود‬ ‫مسلله درختهای نامحدود ميتواند به وسيله جست و جوی عمقي با عمق محدود‬ ‫‪ L‬بهبود يابد‬ ‫‪A‬‬ ‫‪B‬‬ ‫‪C‬‬ ‫‪D‬‬ ‫‪E‬‬ ‫‪F‬‬ ‫‪G‬‬ ‫‪H‬‬ ‫‪I‬‬ ‫‪J‬‬ ‫‪K‬‬ ‫‪L‬‬ ‫‪M‬‬ ‫‪N‬‬ ‫‪O‬‬ ‫‪P‬‬ ‫‪Q‬‬ ‫‪88‬‬  ‫حل مسئله با جستجو‬ ‫جستجوی عمقی محدود‬ ‫کاملبودن‪:‬‬ ‫بودن‪:‬خير‬ ‫کامل‬ ‫اگر ‪ L= y‬يک جمله اما ‪ x2+y‬جمله نيست‬ ‫‪ X+2 >= y‬در جهان درست است اگر ‪ x=7‬و ‪y =1‬‬ ‫‪ X+2 >= y‬در جهان غلط است اگر ‪ x=0‬و ‪y =6‬‬ ‫‪185‬‬  ‫عاملهای منطقی‬ ‫استلزام‬ ‫‪‬استلزام منطقي بين جمالت اين است که جمله ای بطور منطقي از جمله ديگر‬ ‫پيروی ميکند‬ ‫‪a╞b‬‬ ‫‪‬جمله ‪ a‬استلزام جمله ‪ b‬است‬ ‫‪‬جمله ‪ a‬جمله ‪ b‬را ايجاد ميکند‬ ‫‪‬اگر و فقط اگر‪ ،‬در هر مدلي که ‪ a‬درست است‪ b ،‬نيز درست است‬ ‫‪‬اگر ‪ a‬درست باشد‪ b ،‬نيز درست است‬ ‫‪‬درستی ‪ b‬در درستي ‪ a‬نهفته است‬ ‫‪‬مثال‪ :‬جمله ‪ x+y=4‬مستلزم جمله ‪ 4=x+y‬است‬ ‫‪186‬‬  ‫عاملهای منطقی‬ ‫منطق گزاره ای‬ ‫‪‬نحو منطق گزاره ای‪ ،‬جمالت مجاز را تعريف ميکند‬ ‫‪‬جمالت اتميک(عناصر غير قابل تعميم) تشکيل شده از يک نماد گزاره‬ ‫‪‬هر يک از اين نمادها به گزاره ای درست يا نادرست اختصاص دارد‬ ‫‪‬نمادها از حروف بزرگ مثل ‪ R,Q,P‬استفاده ميکنند‬ ‫‪‬جمالت پيچيده با استفاده از رابطهای منطقي‪ ،‬از جمالت ساده تر ساخته ميشوند‬ ‫‪ )not( ┐‬جمله ای مثل ‪ ┐W1,3‬نقيض ‪ W1,3‬است‬ ‫‪‬ليترال يک جمله اتميک(ليترال مثبت)‪ ،‬يا يک جمله اتميک منفي(ليترال منفي) است‬ ‫‪ )and( ^‬مثل ‪ W1,3 ^ P1,3‬ترکيب عطفی نام دارد‪.‬هر بخش آن يک عطف ناميده ميشود‬ ‫‪ )or( ν‬مثل ‪ )W1,3 ^ P3,1( ν W2,2‬ترکيب فصلي مربوط به فصل های ‪ W2,2‬و ‪W1,3 ^ P3,1‬‬ ‫‪( =>‬استلزام)‪ )W1,3 ^ P3,1( => ┐ W2,2 :‬استلزام يا شرطی ناميده ميشود‪.‬مقدمه يما مقمدم‬ ‫آن ‪ W1,3 ^ P3,1‬و نتيجه يا تالي آن ‪ ┐ W2,2‬است‬ ‫‪ ‬جمله ‪ W1,3  W2,2‬دو شرطی نام دارد‬ ‫‪187‬‬  ‫عاملهای منطقی‬ ‫منطق گزاره ای‬ ‫‪188‬‬  ‫عاملهای منطقی‬ ‫جدول درستی پنج رابطه منطقی‬ P Q ┐P P ^ Q P ν Q P=>Q PQ F F T F F T T F T T F T T F T F F F T F F T T F T T T T 189  ‫عاملهای منطقی‬ ‫منطق گزاره ای در دنيای ‪Wumpus‬‬ ‫در ‪ B1,1‬نسيمي وجود دارد‬ ‫‪B1,1  (P1,2 ν‬‬ ‫)‪P2,1‬‬ ‫در ]‪ [1,1‬گودالی وجود ندارد‬ ‫‪R1: ┐P1,1‬‬ ‫‪190‬‬  ‫عاملهای منطقی‬ ‫الگوهای استدالل در منطق گزاره ای‬ ‫‪‬قوانين استنتاج‪ :‬الگوهايي استاندارد که زنجيره ای از نتايج را برای رسيدن به‬ ‫هدف ايجاد ميکند‬ ‫‪‬قياس استثنايي‪ :‬با استفاده از ترکيب عطفی‪ ،‬ميتوان هر عطف را استنتاج‬ ‫کرد(يعنی هر وقت جمله ای به شکل ‪ a=>b‬داده شود‪ ،‬جمله ‪ b‬را ميتوان استنتاج کرد‪).‬‬ ‫‪   ,‬‬ ‫▪ميتوان از‬ ‫)‪(WumpusAhead ^ WumpusAlive‬‬ ‫و‬ ‫‪‬‬ ‫‪(WumpusAhead ^ WumpusAlive) => Shoot‬‬ ‫‪ Shoot‬را استنتاج کرد‬ ‫‪191‬‬  ‫عاملهای منطقی‬ ‫‪‬حذف ‪ :and‬هر عطف را ميتوان از ترکيب عطفی استنتاج کرد‬ ‫‪ ‬‬ ‫مثال‪ WumpusAlive :‬را ميتوان از جمله زير استناج کرد‬ ‫)‪(WumpusAhead ^ WumpusAlive‬‬ ‫‪‬‬ ‫خاصيت يکنواختی‬ ‫مجموعه ای از جمالت استلزامی که فقط ميتواند در صورت اضافه شدن‬ ‫اطالعات به پايگاه دانش رشد کند‪.‬‬ ‫‪KB |=   KB   |= ‬‬ ‫برای جمالت ‪ a‬و ‪ b‬داريم‪:‬‬ ‫‪192‬‬