‫هوش مصنوعي

1.

‫هوش مصنوعي‬
‫فصل سوم‬
‫حل مسئله با جستجو‬
‫‪1‬‬

2.

‫هوش مصنوعي‬
‫فهرست‬
‫‪Artificial Intelligence‬‬
‫‪ ‬عاملهای حل مسئله‬
‫‪ ‬اندازه گيری کارايي حل مسئله‬
‫‪ ‬جستجوی ناآگاهانه‬
‫‪ ‬اجتناب از حالتهای تکراری‬
‫‪ ‬جستجو با اطالعات ناقص‬
‫‪2‬‬

3.

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

4.

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

5.

‫شبه کد عاملهای ساده حل مسئله‬
Function SIMPLE-PROBLEM-SOLVING-AGENT(percept)returns an action
• Inputs:percept,a percept
• Static:seq,an action sequence,initially empty
state,some descripetion of the current world state
goal,a goal,initially null
problem,a problem formulation
• State
UPDATE-STATE(state,percept)
• If seq is empty then do
goal
FORMULATE-GOAL(state)
problem
FORMULATE-PROBLEM(state,goal)
SEQ SEARCH(problem)
• action
FIRST()seq)
• Seq
REST(seq)
• return action
5

6.

‫مفروضات شبه کد عاملهای ساده حل مسئله‬
‫‪ ‬در طرا حي عا مل ارا ئه شده‪ ،‬فرمو له کردن و حل م سئله‬
‫بدون توجه به تغييرات در محيط صورت مي گيرد پس فرض‬
‫بر اين است که محيط ايستا است‪.‬‬
‫‪ ‬فرض مي شود حالت اوليه مشخص است اگر محيط قابل‬
‫مشاهده باشد‪ ،‬دانستن حالت اوليه ساده تر است‪.‬‬
‫‪ ‬فرض مي شود محيط گسسته است‪.‬‬
‫‪ ‬فرض مي شود محيط قطعي است‪.‬‬
‫‪6‬‬

7.

‫حل مسئله با جستجو(مسيريابي در نقشه‬
‫‪7‬‬
‫روماني)‬

8.

‫حل مسئله با جستجو(مسيريابي در نقشه‬
‫روماني)‬
‫‪ ‬صورت مسأله‪ :‬رفتن از آراد به بخارست‬
‫‪ ‬فرموله کردن هدف‪ :‬رسيدن به بخارست‬
‫‪ ‬فرموله کردن مسئله‪:‬‬
‫‪ ‬وضعيتها‪ :‬شهرهای مختلف‬
‫‪ ‬فعاليتها‪ :‬حرکت بين شهرها‬
‫‪ ‬جستجو‪ :‬دنباله ای از شهرها مثل‪:‬آراد‪ ،‬سيبيو‪ ،‬فاگارس‪ ،‬بخارست‬
‫‪8‬‬
‫‪ ‬اين جستجو با توجه به کم هزينه ترين مسير انتخاب ميشود‬

9.

‫مسئله و راه حل های خوش تعريف‬
‫‪ .1‬حالت اوليه‪ :‬حالتی که عامل از آن شروع ميکند‪.‬‬
‫‪ ‬‬
‫در مثال روماني‪ :‬شهر آراد )‪in(Arad‬‬
‫‪ .2‬تابع جانشين‪ :‬توصيفی از فعاليتهای ممکن که برای عامل مهيا است‪.‬‬
‫متداولترین فرمول بندی از تابع جانشين استفاده می کند‪.‬‬
‫با توجه به حالت خاصی مثل ‪، x‬تابع )‪ successor(x‬مجموعه ای از <جانشين و فعاليت> را بصورت زوج‬
‫مرتب بر ميگرداند که هر فعاليت ‪ ،‬یک فعاليت معتبر در حالت ‪ x‬و هر جانشين ‪ ،‬حالتی است که با انجام‬
‫آن فعاليت از طریق ‪ x‬به آن می رسيم‪.‬‬
‫‪ ‬‬
‫‪9‬‬
‫در مثال روماني‪< GO(Sibiu) , in(Sibiu)> :‬‬
‫‪ ‬با توجه به حالت اوليه و تابع جانشين ‪ ،‬فضای حالت مسئله را می توان تعریف کرد‬
‫‪ ‬فضای حالت ‪ :‬مجموعه ای از حالتهاست که از حالت اوليه می توان به آنها رسيد‬

10.

‫مسئله و راه حل های خوش تعريف(ادامه)‬
‫‪ .3‬آزمون هدف‪ :‬تعيين ميکند که آیا حالت خاصی‪ ،‬حالت هدف است یا‬
‫خير‬
‫‪ ‬هدف صریح‪ :‬در مثال رومانی‪ ،‬رسيدن به بخارست‬
‫‪ ‬هدف انتزاعی‪ :‬در مثال شطرنج‪ ،‬رسيدن به حالت کيش و مات‬
‫‪ .4‬تابع هزینه ی مسير‪ :‬برای هر مسير یک هزینه عددی در نظر می گيرد‪.‬‬
‫‪ ‬‬
‫مسير‪:‬دنباله ای از حالتها که دنباله ای از فعاليتها را به هم متصل ميکند‪.‬‬
‫‪ ‬‬
‫در مثال رومانی‪ Arad, Sibiu, Fagaras :‬یک مسير است‬
‫‪ ‬راه حل مسئله مسيری از حالت اوليه به حالت هدف است‬
‫‪10‬‬
‫‪ ‬راه حل بهينه کمترين هزينه مسير را دارد‬

11.

‫حل مسئله با جستجو(مثال جارو برقی)‬
‫حالتها‪ :‬دو مکان که هر یک ممکن است کثيف یا‬
‫تميز باشند‪.‬لذا ‪2^3 = 8‬حالت در این جهان وجود‬
‫دارد‬
‫حالت اوليه‪ :‬هر حالتی ميتواند به عنوان حالت اوليه‬
‫طراحی شود‬
‫تابع جان شين‪ :‬حالت های معت بر از‬
‫عمليات‪:‬راست‪،‬چپ‪ ،‬مکش(مکش‪,‬چپ‪,‬راست)‬
‫سه‬
‫آزمون هدف‪ :‬بررسی می کند که آیا تمام مربعها‬
‫تميز هستند یا خير‬
‫هزینه مسير‪ :‬تعداد مراحل در مسير‬
‫‪11‬‬
‫( در واقع هزینه ی هر مرحله ‪ 1‬است)‬

12.

‫حل مسئله با جستجو(مثال معمای ‪)8‬‬
‫حالتها‪ :‬مکان هر هشت خانه شماره دار و خانه خالی در یکی از ‪ 9‬خانه‬
‫حالت اوليه‪ :‬هر حالتی را ميتوان به عنوان حالت اوليه در نظر گرفت‬
‫تابع جانشين‪ :‬حالتهای معتبر از چهار عمل را توليد می کند‬
‫( انتقال خانه خالی به چپ‪ ،‬راست‪ ،‬باال یا پایين)‬
‫آزمون هدف‪ :‬بررسی ميکند که آیا اعداد به ترتيب چيده شده اند(طبق‬
‫شکل روبرو) یا خير‬
‫هزینه مسير‪ :‬برابر با تعداد مراحل در مسير‬
‫(هزینه هر مرحله ‪ 1‬است)‬
‫‪12‬‬

13.

‫حل مسئله با جستجو(مثال معمای ‪-8‬ادامه)‬
‫‪ ‬مع مای ‪ 8‬به خانوادهی معما های جاب جایی ب لوک تع لق دارد که برای آز مون ال گوریتم‬
‫های جستجوی جدید در ‪ AI‬بکار می رود‪.‬‬
‫‪ ‬این رده از مسائل را ‪ NP‬کامل می گویند‪.‬‬
‫‪ ‬معمای ‪ 8‬دارای!‪ 9‬حالت قابل رسيدن است‪.‬‬
‫‪ ‬مع مای ‪ (15‬صفحه ی‪ )4*4‬تقری با دارای ‪ 3/1‬تریل يون حا لت ا ست ا ما در چ ند مي لی‬
‫ثانيه حل می شوند‪.‬‬
‫‪ ‬معمای ‪ ( 24‬صفحه ی ‪ )5*5‬تقریبا ‪10^25‬حالت دارد و حل نمونه های آن با بهترین‬
‫الگوریتم ها و ماشين های فعلی دشوار است‪.‬‬
‫‪13‬‬

14.

‫حل مسئله با جستجو(مثال ‪ 8‬وزیر)‬
‫فرمول بندی افزايشي‬
‫حالتها‪ :‬هر ترتيبی از ‪ 0‬تا ‪ 8‬وزیر در صفحه‪ ،‬یک حالت‬
‫است‬
‫حالت اوليه‪ :‬هيچ وزیری در صفحه نيست‬
‫تابع جانشين‪ :‬وزیری را به خانه خالی اضافه ميکند‬
‫آز مون هدف‪8 :‬وز یر در صفحه و جود دار ند و هيچ‬
‫کدام به یکدیگر گارد نميگيرند‬
‫در اين فرمول بندی بايد ‪3*10^14‬‬
‫دنباله ممکن بررسي ميشود‬
‫‪14‬‬

15.

‫حل مسئله با جستجو(مثال ‪ 8‬وزیر‪-‬ادامه)‬
‫فرمول بندی حالت کامل‬
‫حالتها‪ :‬چيدمان ‪ n‬وزیر )‪ ،(0≤ n≤ 8‬بطوریکه در هر ستون از‬
‫‪ n‬ستون سمت چپ‪ ،‬یک وزیر قرار گيرد و هيچ دو وزیری بهم‬
‫گارد نگيرند‬
‫حالت اوليه‪ :‬با ‪ 8‬وزیر در صفحه شروع ميشود‬
‫تابع جانشين‪? :‬‬
‫آز مون هدف‪8 :‬وز یر در صفحه و جود دار ند و هيچ کدام به‬
‫یکدیگر گارد نميگيرند‬
‫اين فرمول بندی فضای حالت را از‬
‫‪ 3*10^14‬به ‪ 2057‬کاهش ميدهد‬
‫‪15‬‬

16.

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

17.

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

18.

‫جستجوی عرضي‬
A
B
E
J
C
F
K
D
G
L
M
H
N
O
P
I
Q
18

19.

‫جستجوی عرضي(ادامه)‬
‫کامل بودن‪ :‬بله‬
‫بهينگی‪ :‬بله (مشروط)‬
‫جستجوی عرضی ابتدا کم عمق ترین وضعيت هدف را پيدا می کند و در صورتی‬
‫بهينه است که هزینه مسير ‪ ،‬تابعی غير نزولی از عمق گره باشد (مثل وقتی که فعاليتها‬
‫هزینه یکسانی دارند)‬
‫پيچيدگی زمانی‪:‬‬
‫)‬
‫‪d 1‬‬
‫‪O(b‬‬
‫پيچيدگی فضا‪:‬‬
‫)‬
‫‪d 1‬‬
‫‪O(b‬‬
‫‪19‬‬

20.

‫زمان و فضای الزم برای جستجوی عرضی‬
‫عمق‬
‫گره ها‬
‫زمان‬
‫حافظه‬
‫‪2‬‬
‫‪1100‬‬
‫‪11 seconds‬‬
‫‪1mb‬‬
‫‪4‬‬
‫‪111،100‬‬
‫‪11 seconds‬‬
‫‪106 mb‬‬
‫‪6‬‬
‫‪10^7‬‬
‫‪19 minutes‬‬
‫‪10gb‬‬
‫‪8‬‬
‫‪10^9‬‬
‫‪31 hours‬‬
‫‪1tb‬‬
‫‪10‬‬
‫‪10^11‬‬
‫‪129 days‬‬
‫‪101 tb‬‬
‫‪12‬‬
‫‪10^13‬‬
‫‪35 years‬‬
‫‪10pb‬‬
‫‪14‬‬
‫‪10^15‬‬
‫‪3،523 years‬‬
‫‪1eb‬‬
‫اعدادی که نشان داده شده اند با فاکتور ‪B=10‬تعداد ‪ 000/10‬گره در هر ثانيه و هر گره‬
‫‪ 1000‬بايت فضا را اشغال مي کند ‪.‬اين اعداد نشان مي دهند که هر هر چند مسئله زمان‬
‫‪20‬‬
‫مسئله ی مهمي است اما مسئله ی فضا مسئله ی جدی تری است‪.‬‬

21.

‫جستجوی با هزينه يکنواخت‬
‫‪ ‬جستجو با هزینه ی یکنواخت ‪ ،‬استراتژی جستجوی عرضی را توسط بسط‬
‫کم هزینه ترین گره و نه کم عمق ترین گره بهبود می بخشد درواقع جستجوی‬
‫عرضی‪ ،‬همان جستجوی یکسان با )‪ g(n)=DEPTH(n‬است‪ g(n)(.‬تابع‬
‫هزینه ی مسير است)‬
‫‪ ‬کامل بودن وقتی تضمين می شود که هزینه ی هر مرحله بزرگتر یا مساوی‬
‫یک مقدار ثابت و مثبت ‪ ξ‬باشد‪ .‬این شرط برای بهينگی نيز کافی است‪.‬‬
‫‪21‬‬

22.

‫جستجوی با هزينه يکنواخت(ادامه‪)1‬‬
‫‪ ‬این استراتژی بجای عمق از هزینه ی های مسير پيروی می کند لذا پيچيدگی‬
‫آن را نمی توان براحتی بر حسب ‪ b‬و ‪ d‬بدست آورد‪.‬‬
‫‪ ‬فرض کنيد هزینه ی راه حل بهينه * ‪ c‬و هزینه هر فعاليت حداقل ‪ ξ‬است‬
‫آنگاه پيچيدگی زمان و فضای الگوریتم در بدترین حالت برابر با‬
‫است‪.‬‬
‫‪ ‬وقتی هزینه تمام مراحل یکسان باشد ‪،‬‬
‫بود‪.‬‬
‫‪22‬‬
‫برابر با ‪ b ^d‬خواهد‬

23.

‫جستجوی با هزينه يکنواخت(ادامه‪)2‬‬
‫این جستجو گره ‪ L‬را با کمترین هزینه مسير بسط ميدهد‬
‫‪A‬‬
‫‪3‬‬
‫‪1‬‬
‫‪D‬‬
‫‪C‬‬
‫‪I‬‬
‫‪B‬‬
‫‪H‬‬
‫‪Q‬‬
‫‪23‬‬
‫‪1‬‬
‫‪P‬‬
‫‪G‬‬
‫‪O‬‬
‫‪N‬‬
‫‪F‬‬
‫‪M‬‬
‫‪L‬‬
‫‪E‬‬
‫‪K‬‬
‫‪J‬‬

24.

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

25.

)1‫جستجوی عمقي(ادامه‬
A
2
3
4
E
B
C
F
6
D
G
H
I
7
J
K
L
M
N
O
P
Q
5
25

26.

‫جستجوی عمقي(ادامه‪)2‬‬
‫کامل بودن‪ :‬خير‬
‫اگر زیر درخت چپ عمق نامحدود داشت و فاقد هر گونه راه حل باشد‪،‬‬
‫جستجو هرگز خاتمه نمی یابد‪.‬‬
‫بهينگی‪ :‬خير‬
‫‪m‬‬
‫پيچيدگی زمانی‪:‬‬
‫) ‪O(b‬‬
‫پيچيدگی فضا‪:‬‬
‫)‪O(bm‬‬
‫‪26‬‬
‫‪ m‬نشان دهنده ی حداکثر عمق است‪.‬‬

27.

‫جستجوی عمقي محدود‬
‫این استراتژی شبيه استراتژی جستجوی عمقی است با این‬
‫تفاوت که فرض می شود گره های سطح‪ L‬فاقد جانشين هستند‬
‫یعنی درخت تا عمق ‪ L‬بسط داده می شود و از آنجا پایين تر نمی‬
‫رود‪.‬‬
‫‪ ‬مسئله درختهای نامحدود ميتواند به وسيله جست و جوی‬
‫عمقی با عمق محدود ‪ L‬بهبود یابد‬
‫‪27‬‬

28.

‫جستجوی عمقي محدود(ادامه‪)1‬‬
‫‪A‬‬
‫‪D‬‬
‫‪C‬‬
‫‪I‬‬
‫‪H‬‬
‫‪Q‬‬
‫‪28‬‬
‫‪B‬‬
‫‪P‬‬
‫‪G‬‬
‫‪O‬‬
‫‪N‬‬
‫‪F‬‬
‫‪M‬‬
‫‪L‬‬
‫‪E‬‬
‫‪K‬‬
‫‪J‬‬

29.

‫جستجوی عمقي محدود(ادامه‪)2‬‬
‫کامل بودن‪ :‬خير‬
‫اگر ‪ L<d‬باشد و سطحی ترین هدف در خارج از عمق‬
‫محدود شده قرار داشته باشد‪ ،‬این راهبرد کامل نخواهد بود‪.‬‬
‫بهينگی‪ :‬خير‬
‫این راهبرد بهينه نخواهد بود‪.‬‬
‫‪L‬‬
‫پيچيدگی زمانی‪O(b ) :‬‬
‫پيچيدگی فضا‪:‬‬
‫‪29‬‬
‫)‪O(bL‬‬

30.

‫جستجوی عميق کننده تکراری‬
‫‪ ‬این استراتژی شبيه به جستجوی عمقی محدود عمل می کند با این تفاوت‬
‫که عمق محدود شده ‪ L‬بتدریج اضافه شده و جستجو از سر گرفته می شود‪.‬‬
‫‪ ‬روند جستجو تا رسيدن به اولين پاسخ ادامه پيدا می کند‪.‬‬
‫‪ ‬جستجوی عميق کننده ی تکراری مزایای جستجوی عمقی و جستجوی‬
‫سطحی را در بردارد‪.‬‬
‫‪ ‬بطور کلی وقتی فضای جستجو بزرگ باشد و عمق راه حل مشخص نباشد‬
‫جستجوی عميق کننده ی تکراری روش ناآگاهانه مناسبی است‪.‬‬
‫‪30‬‬

31.

‫جستجوی عميق کننده تکراری(ادامه‪)1‬‬
‫‪A‬‬
‫‪D‬‬
‫‪C‬‬
‫‪I‬‬
‫‪H‬‬
‫‪Q‬‬
‫‪31‬‬
‫‪B‬‬
‫‪P‬‬
‫‪G‬‬
‫‪O‬‬
‫‪N‬‬
‫‪F‬‬
‫‪M‬‬
‫‪L‬‬
‫‪E‬‬
‫‪K‬‬
‫‪J‬‬

32.

‫جستجوی عميق کننده تکراری(ادامه‪)2‬‬
‫‪A‬‬
‫‪D‬‬
‫‪C‬‬
‫‪I‬‬
‫‪H‬‬
‫‪Q‬‬
‫‪32‬‬
‫‪B‬‬
‫‪P‬‬
‫‪G‬‬
‫‪O‬‬
‫‪N‬‬
‫‪F‬‬
‫‪M‬‬
‫‪L‬‬
‫‪E‬‬
‫‪K‬‬
‫‪J‬‬

33.

‫جستجوی عميق کننده تکراری(ادامه‪)3‬‬
‫‪A‬‬
‫‪D‬‬
‫‪C‬‬
‫‪I‬‬
‫‪S‬‬
‫‪33‬‬
‫‪B‬‬
‫‪H‬‬
‫‪R‬‬
‫‪Q‬‬
‫‪P‬‬
‫‪G‬‬
‫‪O‬‬
‫‪N‬‬
‫‪F‬‬
‫‪M‬‬
‫‪L‬‬
‫‪E‬‬
‫‪K‬‬
‫‪J‬‬

34.

‫جستجوی عميق کننده تکراری(ادامه‪)4‬‬
‫کامل بودن‪ :‬بله‬
‫در صورتی که فاکتور انشعاب محدود باشد‬
‫بهينگی‪ :‬بله‬
‫وقتی که هزینه مسير‪ ،‬تابعی غير نزولی از عمق گره‬
‫باشد‬
‫‪d‬‬
‫پيچيدگی زمانی‪O(b ) :‬‬
‫پيچيدگی فضا‪:‬‬
‫‪34‬‬
‫)‪O(bd‬‬

35.

‫جستجوی دو طرفه‬
‫انجام دو جست و جوی همزمان‪ ،‬یکی از حالت اوليه به هدف و دیگری از‬
‫هدف به حالت اوليه تا زمانی که دو جست و جو به هم برسند‬
‫‪35‬‬

36.

‫جستجوی دو طرفه(ادامه‪)1‬‬
‫‪ ‬جستجو از سمت هدف به چه معناست؟‬
‫‪ ‬تعریف)‪ -‬ما قبل های گره ‪ ، n‬گره هایی هستند که ‪ ، n‬ما بعد آن ها باشد‪.‬‬
‫ جستجو به سمت عقب به این معناست که توليد ما قبل ها از گره هدف آغاز شود‪.‬‬‫‪ ‬اگر تمام عملگرها قابل وارونه شدن باشند محاسبه ی ماقبل ها به سادگی امکان پذیر است‬
‫اما این کار در برخی مسائل بسيار مشکل است‪.‬‬
‫‪ ‬مسئله ی دیگر در جستجوی دوطرفه این است که هدف باید مشخص باشد‪.‬‬
‫‪36‬‬

37.

‫جستجوی دو طرفه(ادامه‪)2‬‬
‫کامل بودن‪ :‬بله‬
‫اگر هر دو جستجو‪ ،‬عرضی باشند‬
‫بهينگی‪ :‬بله‬
‫اگر هر دو جستجو‪ ،‬عرضی باشند و هزینه تمام مراحل یکسان باشد‬
‫‪d/2‬‬
‫پيچيدگی زمانی‪O(b ) :‬‬
‫‪d/2‬‬
‫پيچيدگی فضا‪O(b ) :‬‬
‫‪37‬‬

38.

‫ارزيابي راهبردهای جستجو‬
‫‪BFS‬‬
‫‪38‬‬
‫‪DFS‬‬
‫‪DLS‬‬
‫‪IDFS‬‬
‫‪BID‬‬

39.

‫اجتناب از حالتهای تکراری‬
‫‪ ‬وجود حالتهای تکراری در يک مسئله قابل حل ‪ ،‬مي تواند آنرا‬
‫به مسئله غير قابل حل تبديل کند‪.‬‬
‫‪39‬‬

40.

‫دنيای جارو برقي فاقد حسگر‬
‫‪ ‬عامل جارو تمام اثرات فعاليتهایش را ميداند اما فاقد‬
‫حسگر است‪.‬‬
‫کی از اع‬
‫يه آن ی‬
‫‪ ‬حا لت اول‬
‫مجموعه{‪ }1،2،3،4،5،6،7،8‬ميباشد‬
‫‪ ‬فعاليت (( راست‬
‫‪ ‬فعاليت (راست‪,‬مکش)‬
‫ضای‬
‫{‪}2،4،6،8‬‬
‫{‪}4،8‬‬
‫‪ ‬فعال يت (را ست‪,‬م کش‪ ,‬چپ‪,‬م کش) ت ضمين ميک ند‬
‫که صرف نظر از حالت اوليه‪ ،‬به حالت هدف‪ ،‬یعنی ‪7‬‬
‫برسد‬
‫‪40‬‬

41.

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