حل مسئله توسط جستجو

حل مسئله توسط جستجو

اسلاید 1: حل مسائل توسط جستجورامین اعیان زادهEmail: grandee@ayanzadeh.ir1389

اسلاید 2: 2مقدمهعاملهای حل مسألهانواع مسألهفرموله سازی مسألهمسائل نمونهالگوريتم های ابتدايی جستجو

اسلاید 3: 3عامل حل مسأله عامل حل مسأله يک نوع عامل هدف گرا می باشد. عامل حل مسأله، مسأله داده شده را از طريق يافتن دنباله ای از عمليات که آنرا از حالت اوليه مسأله به يک حالت هدف می برد، حل می کند.مراحل حل مسأله توسط عامل حل مسأله:(1) فرموله سازی هدف(2) فرموله سازی مسأله ( انتخاب حالات و عمليات به دنبال فرموله سازی هدف)(3) جستجو ( برای يافتن دنباله عمليات مورد نظر يا راه حل مسأله)(4) اجرا

اسلاید 4: 4مشخص کردن وضعيت هاهر وضعيت را به صورت (X, Y) نشان مي دهيم به طوريکه:X : مقدار آب موجود در تنگ 4 ليتري مي باشد وY : مقدار آب موجود در تنگ 3 ليتري مي باشد.43

اسلاید 5: 5تعيين وضعيت هدفهدف : در اين مسأله هدف اين است که به وضعيتي برسيم که در آن تنگ 4 ليتري حاوي 2 ليتر آب و تنگ 3 ليتري خالي باشد. بنابراين مي توان وضعيت هدف را به شکل زير فرموله نمود: 2(2, 0)

اسلاید 6: 6تعيين وضعيت اوليهوضعيت اوليه : در اين مسأله از وضعيتي شروع مي کنيم که در آن هر دو تنگ خالي مي باشند. بنابراين مي توان وضعيت اوليه را به شکل زير فرموله نمود: (0, 0)

اسلاید 7: 7تعيين عملگرهاعملگرها پر کردن تنگ 4 ليتري پرکردن تنگ 3 ليتري خالي کردن مقداري از تنگ 3 ليتري در تنگ 4 ليتري تا پرشدن آن خالي کردن مقداري از تنگ 4 ليتري در تنگ 3 ليتري تا پرشدن آن خالي کردن تمام آب تنگ 4 ليتري در 3 ليتري خالي کردن تمام آب تنگ 3 ليتري در 4 ليتري خالي کردن تنگ 4 ليتري خالي کردن تنگ 3 ليتري در صفحه بعد اين عملگرها فرموله سازي شده اند

اسلاید 8: 8عملگرها(X,Y | X < 4)  (4, Y)(X,Y | Y < 3)  (X, 3)(X,Y | X + Y >=4, Y > 0)  (4, Y – (4 – X))(X,Y | X + Y >=3 , X > 0)  (X – (3 – Y), 3)(X,Y | X + Y <= 3 , X >0)  ( 0, X + Y)(X,Y | X + Y <= 4 , Y >0)  (X + Y, 0)(X,Y | X > 0)  (0, Y)(X,Y | Y > 0)  (X, 0)

اسلاید 9: 9تابع آزمون هدف و هزينه مسيرتابع آزمون هدف: اگر وضعيت فعلي برابر (2,0) باشد مقدار درست و در غير اين صورت مقدار نادرست را بر مي گرداند.تابع هزينه مسير: هزينه هر عمل برابر يک مي باشد. بنابراين هزينه يک مسير برابر با طول آن مسير ( تعداد عمليات) مي باشد.

اسلاید 10: 10يک راه حل نمونه(0, 0)(4, 2)(2, 0)(3, 0)(0, 2)(0, 3)(3, 3)262763حالت اوليه ( شروع)دنباله عمليات: {2, 6, 2, 3, 7, 6}حالت هدف ( نهايی)

اسلاید 11: 11عامل های حل مسألهشکل محدود شده عامل های عمومیfunction SIMPLE-PROBLEM-SOLVING-AGENT( p) returns an action inputs: p, a percept static: s, an action sequence, initially empty state, some description of the current world state g, a goal problem, a problem formulation state  UPDATE-STATE( state, p) if s is empty then g  FORMULATE-GOAL( state) problem  FORMULATE-PROBLEM( state, g) s  SEARCH( problem) action  RECOMMENDATION( s, state) s  REMAINDER( s, state) return action

اسلاید 12: 12مثال: رومانیيک روز تعطيل در رومانی؛ مکان فعلی شهرآرادپرواز فردا بخارست را ترک می کند.فرموله سازی هدف:بودن در بخارستفرموله سازی مسأله:حالت ها: شهرهای مختلفعمليات: رفتن از شهری به شهر ديگريافتن پاسخ:دنباله ای از شهرها، مانند:Arad  Sibiu  Fagaras  Bucharest

اسلاید 13: 13مثال: رومانی

اسلاید 14: 14انواع مسألهقطعی، کاملا دسترس پذير مسائل تک – حالتهعامل دقيقا می داند در چه حالتی خواهد بود؛ راه حل يک دنباله می باشد.قطعی، غير دسترس پذير مسائل چند-حالتهممکن است عامل ايده ای درباره اينکه کجاست نداشته باشد؛ راه حل ( در صورت وجود) يک دنباله است.غير قطعی و/يا دسترس پذير جزئی مسائل احتمالیادراک اطلاعات جديدی درباره حالت فعلی فراهم می کند.در حين اجرا بايد از حسگرها استفاده کند.راه حل به صورت يک درخت اغلب جستجو و اجرا به صورت interleave فضای حالت ناشناخته مسائل اکتشافی (online)

اسلاید 15: 15مثال: دنيای مکشتک-حالته، شروع #5. پاسخ؟؟

اسلاید 16: 16مثال: دنيای مکشتک-حالته، شروع #5. پاسخ؟؟[Right, Suck]چند-حالته، شروع در {1, 2, 3, 4, 5, 6, 7, 8}مثال عمل Right به {1, 2, 3, 4}. پاسخ؟؟

اسلاید 17: 17مثال: دنيای مکشتک-حالته، شروع #5. پاسخ؟؟[Right, Suck]چند-حالته، شروع در {1, 2, 3, 4, 5, 6, 7, 8}مثال عمل Right به {1, 2, 3, 4}. پاسخ؟؟[Right, Suck, Left, Suck]احتمالی، شروع در #5.قانون مورفی: مکش می تواند يک فرش تميز را کثيف کند.درک محلی: گرد و خاک و محل پاسخ؟؟[Right, if dirt then Suck]

اسلاید 18: 18فرموله سازی مسائل تک-حالتهيک مسأله بوسيله چهار مورد تعريف می شود:حالت اوليهمثلا بودن در شهر Aradتابع حالت بعدی (Successor function S( x) )S( x)= مجموعه ای از زوج های عمل-حالتS( Arad) = {<Arad  Zerind, Zerind>, …}تابع تست هدف (Goal test function) صريح: x = “at Bucharest”ضمنی: NoDirt( x)تابع هزينه مسير (Path cost function)مثلا: مجموع فواصل، تعداد عمل های انجام شده و ...هزينه گام (Step cost): c( x, a, y) ≥ 0راه حل:دنباله ای از عمليات که از حالت اوليه شروع و به حالت هدف ختم می شود.

اسلاید 19: 19انتخاب يک فضای حالت دنيای واقعی به شدت پيچيده می باشدبنابراين، برای حل مسأله بايد فضای حالت انتزاعی باشد.حالت ( انتزاعی) = مجموعه ای از حالت های واقعیعمل ( انتزاعی) = ترکيبی پيچيده از عمل های واقعیمثلا عمل Arad  Zerind می تواند مجموعه ای پيچيده از اعمال باشد.راه حل ( انتزاعی) = مجموعه ای از مسيرهای واقعی که در دنيای واقعی راه حل می باشند.هر عمل انتزاعی بايد از مسأله اصلی ساده تر باشد!

اسلاید 20: 20مثال: گراف فضای حالت دنيای مکش حالات؟؟ اعمال؟؟ تست هدف؟؟ هزينه مسير؟؟

اسلاید 21: 21مثال: گراف فضای حالت دنيای مکش حالات؟؟ وجود گرد و خاک و مکان های عامل ( بدون در نظر گرفتن مقدار گرد و خاک) اعمال؟؟ Left, Right, Suck تست هدف؟؟ نبودن گرد و خاک هزينه مسير؟؟ بازاء هر عمل 1

اسلاید 22: 22مثال: معمای هشت حالات؟؟ اعمال؟؟ تست هدف؟؟ هزينه مسير؟؟

اسلاید 23: 23مثال: معمای هشت حالات؟؟ اعداد صحيح بيانگر محل کاشی ها اعمال؟؟ حرکت خانه خالی به چپ، بالا، راست و پايين تست هدف؟؟ حالت هدف ( داده شده) هزينه مسير؟؟ بازاء هر حرکت 1

اسلاید 24: 24مسأله هشت وزير قراردادن هشت وزير در صفحه شطرنج به طوريکه هيچ وزيری نتواند به وزير ديگری حمله کند. آزمون هدف: 8 وزير روی صفحه شطرنجکه با هم برخورد ندارند.هزينه مسير: صفرحالات: ترتيب 8 وزير هر کدام در يک ستونمثال روبرو: {8, 6, 4, 2, 7, 5, 3, 1} عملگرها: انتقال يک وزير دارای برخورد بهمربع ديگری در همان ستون

اسلاید 25: 25رياضيات رمزی حالات: يک معمای رمزی که درآن تعدادی حرف با رقم جايگزين شده باشد.عملگرها: جايگزينی يک حرف با رقمی که قبلا در معما ظاهر نشده باشد.آزمون هدف: معما فقط شامل ارقام است و مجموعصحيح باشد. هزينه مسير: صفر29786 850 850--------31486FORTY+ TEN+ TEN---------- SIXTYراه حل

اسلاید 26: 26مسأله کشيش ها و آدمخوارهاحالات : يک سه تايي مرتب که شامل تعداد کشيشها و تعداد آدمخوارها در ساحلی از رودخانه که مسأله از آنجا شروع شده و محل قايق ( شمال/جنوب)– مثلا حالت شروع (3, 3, 1)عملگرها: جابه جايی يک کشيش، دو کشيش، يک کشيش و يک آدمخوار، يک آدمخوار و دو آدمخوار توسط قايق به سمت ديگر رودخانه.آزمون هدف : (0, 0, 0)هزينه مسير: تعداد دفعات عبور قايق از عرض رودخانه

اسلاید 27: 27الگوريتمهای جستجوی درخت ايده اصلی: کاوش offline و شبيه سازی شده فضای حالت بوسيله توليد حالات بعدی حالت هايی که تا کنون توليد شده اند. function GENERAL-SEARCH( problem, strategy) returns a solution , or failure initialize the search tree using the initial state of problem loop do if there are no candidates for expansion then return failure choose a leaf node for expansion according to strategy if the node contains the goal state then return the corresponding solution else expand the node and add the resulting node to the search tree end

اسلاید 28: 28مثال جستجوی درخت

اسلاید 29: 29مثال جستجوی درخت

اسلاید 30: 30مثال جستجوی درخت

اسلاید 31: 31پياده سازی: حالت و گره يک حالت ( بيانگر) يک پيکره بندی فيزيکی می باشد يک گره يک ساختار داده ای تشکيل دهنده بخشی از درخت جستجو شامل: پدر، فرزندان، عمق و هزينه مسير g( x) است. حالت ها :پدر، فرزند، عمق و هزينه مسير ندارند!تابع EXPAND گره های جديد ايجاد می کند، فيلدهای مختلف را مقدار می دهد و با استفاده از تابع SUCCESSORSFN مسأله، حالت های مربوطه ايجاد می شود.

اسلاید 32: 32پياده سازی: جستجوی درخت کلیfunction TREE-SEARCH( problem, QUEUING-FN) returns a solution or failure nodes  MAKE-QUEUE( MAKE-NODE(INITIAL-STATE[ problem] ) loop do if nodes is empty then return failure node  REMOVE-FRONT( nodes) if GOAL-TEST[problem] applied to STATE( node) succeeds, then return node nodes  QUEUING-FN( nodes, EXPAND( node, problem) ) end

اسلاید 33: 33پياده سازی: تابع گسترش گره هاfunction EXPAND( node, problem) returns a set of nodes successors  the empty list for each action, result in SUCCESSORS-FN[ problem]( STATE[ node]) s  a new node PARENT-NODE[ s]  node; ACTION[ s]  action; STATE[ s]  result PATH-COST[ s]  PATH-COST[ node] + STEP-COST( node, action, s) DEPTH[ s]  DEPTH[ node] + 1 add s to successors return successors

اسلاید 34: 34استراتژی های جستجو يک استراتژی بوسيله ترتيب گسترش گره ها تعريف می شود. ابعاد ارزيابی استراتژي ها:کامل بودن– آيا در صورت وجود راه حل، هميشه راه حلی پيدا می کند؟پيچيدگی زمانی – تعداد گره های توليد شده/گسترش يافتهپيچيدگی حافظه – حداکثر تعداد گره ها در حافظهبهينگی – آيا هميشه کم هزينه ترين راه حل را پيدا می کند؟ پيچيدگی زمان و فضا برحسب پارامترهای زير سنجيده می شوند:b – حداکثر فاکتور انشعاب درخت جستجو d – عمق کم هزينه ترين راه حلm – حداکثر عمق فضای حالت ( ممکن است ∞ باشد)

اسلاید 35: 35استرتژی های جستجوی ناآگاهانه استراتژی های ناآگاهانه تنها از اطلاعات موجود در تعريف مسأله استفاده می کنند.جستجوی اول-سطح (BFS)جستجوی هزينه-يکسان (UCS)جستجوی اول-عمق ( عمقی) (DFS)جستجوی با عمق محدود (DLS)جستجوی عميق کننده تکراری (IDS)

اسلاید 36: 36جستجوی سطحی هربار سطحی ترين گره گسترش نيافته را گسترش می دهد. پياده سازی:fringe يک صف FIFO می باشد. Queuing-Fnفرزندان جديد را به انتهای صف اضافه می کند.

اسلاید 37: 37جستجوی سطحی هربار سطحی ترين گره گسترش نيافته را گسترش می دهد. پياده سازی:fringe يک صف FIFO می باشد. فرزندان جديد به انتهای صف اضافه می شوند.

اسلاید 38: 38جستجوی سطحی هربار سطحی ترين گره گسترش نيافته را گسترش می دهد. پياده سازی:fringe يک صف FIFO می باشد. فرزندان جديد به انتهای صف اضافه می شوند.

اسلاید 39: 39جستجوی سطحی هربار سطحی ترين گره گسترش نيافته را گسترش می دهد. پياده سازی:fringe يک صف FIFO می باشد. فرزندان جديد به انتهای صف اضافه می شوند.

اسلاید 40: 40AradLugojAradOradeaFagarasRimnicuVilceaAradOradeaZerindSibiuTimisoaraمثال: جستجوی سطحیArad

اسلاید 41: 41 خصوصيات جستجوی سطحی کامل؟؟ پيچيدگی زمانی؟؟ پيچيدگی حافظه؟؟ بهينه؟؟ بله ( اگر هزينه هر عمل يک باشد)؛ در حالت کلی خير1 + b + b2 + … + bd = O( bd)O(bd) چون همه گره ها را در حافظه نگه می داردبله ( به شرط محدود بودن b)مشکل اصلی حافظه می باشد.

اسلاید 42: 42ميزان مصرف حافظه و زمان در BFSb=101000 گره در ثانيههر گره 100 بايت

اسلاید 43: 43جستجوی هزينه-يکسان هربار کم هزينه ترين گره گسترش نيافته را گسترش می دهد. پياده سازی:fringe = صفی که براساس هزينه مسير مرتب شده باشد. معادل جستجوی سطحی اگر هزينه گام ها مساوی باشند.کامل؟؟ بله اگر هزينه گامها ≤ ε پيچيدگی زمانی؟؟ تعداد گره هايي که هزينه مسير آنها کوچکتر يا مساوی هزينه راه حل بهينه باشد. پيچيدگی حافظه؟؟ مانند پيچيدگی زمانی بهينه؟؟ بله ( گره ها به ترتيب صعودی g( n) گسترش می يابند).

اسلاید 44: 44AradOradeaFagarasRimnicuVilcea1401519980AradLugoj118111AradOradea7571مثال: جستجوی هزينه يکسانAradZerindSibiuTimisoara75140118

اسلاید 45: 45مثال: جستجوی هزينه يکسانASBCG110155550SABC1515G11G10

اسلاید 46: 46جستجوی عمقی هربار عميق ترين گره گسترش نيافته را گسترش می دهد.پياده سازی: fringe = پشته LIFO، فرزندان جديد را در ابتدا درج می کند.

اسلاید 47: 47جستجوی عمقی هربار عميق ترين گره گسترش نيافته را گسترش می دهد.پياده سازی: fringe = پشته LIFO، فرزندان جديد را در ابتدا درج می کند.

اسلاید 48: 48جستجوی عمقی هربار عميق ترين گره گسترش نيافته را گسترش می دهد.پياده سازی: fringe = پشته LIFO، فرزندان جديد را در ابتدا درج می کند.

اسلاید 49: 49جستجوی عمقی هربار عميق ترين گره گسترش نيافته را گسترش می دهد.پياده سازی: fringe = پشته LIFO، فرزندان جديد را در ابتدا درج می کند.

اسلاید 50: 50جستجوی عمقی هربار عميق ترين گره گسترش نيافته را گسترش می دهد.پياده سازی: fringe = پشته LIFO، فرزندان جديد را در ابتدا درج می کند.

اسلاید 51: 51جستجوی عمقی هربار عميق ترين گره گسترش نيافته را گسترش می دهد.پياده سازی: fringe = پشته LIFO، فرزندان جديد را در ابتدا درج می کند.

اسلاید 52: 52جستجوی عمقی هربار عميق ترين گره گسترش نيافته را گسترش می دهد.پياده سازی: fringe = پشته LIFO، فرزندان جديد را در ابتدا درج می کند.

اسلاید 53: 53جستجوی عمقی هربار عميق ترين گره گسترش نيافته را گسترش می دهد.پياده سازی: fringe = پشته LIFO، فرزندان جديد را در ابتدا درج می کند.

اسلاید 54: 54جستجوی عمقی هربار عميق ترين گره گسترش نيافته را گسترش می دهد.پياده سازی: fringe = پشته LIFO، فرزندان جديد را در ابتدا درج می کند.

اسلاید 55: 55جستجوی عمقی هربار عميق ترين گره گسترش نيافته را گسترش می دهد.پياده سازی: fringe = پشته LIFO، فرزندان جديد را در ابتدا درج می کند.

اسلاید 56: 56جستجوی عمقی هربار عميق ترين گره گسترش نيافته را گسترش می دهد.پياده سازی: fringe = پشته LIFO، فرزندان جديد را در ابتدا درج می کند.

اسلاید 57: 57جستجوی عمقی هربار عميق ترين گره گسترش نيافته را گسترش می دهد.پياده سازی: fringe = پشته LIFO، فرزندان جديد را در ابتدا درج می کند.

اسلاید 58: 58ZerindSibiuTimisoaraAradOradeaZerindSibiuTimisoaraمثال: جستجوی عمقیAradحلقه بی پايان !در اين جستجو نياز به فضای حالت محدود و بدون چرخه داريم،يا بايد حالات تکراری چک شوند.

اسلاید 59: 59 خصوصيات جستجوی عمقی کامل؟؟ خير (در فضاهای حالت با عمق نامحدود، دارای حلقه) برای اجتناب از حالات تکرای در طول مسير نياز به اصلاح دارد.بنابراين، در فضای حالت محدود کامل است. پيچيدگی زمانی؟؟ O( bm)اگر m خيلی بيشتر از d باشد، بسيار زياداما اگر تعداد راه حل ها زياد باشد، سريعتر از جستجوی سطحی پيچيدگی حافظه؟؟ O( bm)، به صورت خطی! بهينه؟؟ خير

اسلاید 60: 60جستجوی با عمق محدود = جستجوی عمقی با محدوده عمقی l يعنی،فرزندان گره های واقع در عمق l توليد نخواهند شد. در اين استراتژی با در نظر گرفتن يک محدوده عمقی مانند l از به دام افتادن جستجوی عمقی در يک حلقه بی پايان جلوگيری می شود.( برش روی درخت جستجو)مثلا در نقشه رومانی چون 20 شهر وجود دارد بنابراين طول راه حل بايد حداکثر 19 باشد.بنابراين هيچ وقت گره ای با عمق بيش از 19 بررسی نخواهد شد.اگر در محدوده عمقی l راه حلی وجود داشته باشد، بالاخره پيدا خواهد شد، اما هيچ تضمينی برای يافتن راه حل بهينه وجودندارد.

اسلاید 61: 61جستجوی با عمق محدود کامل؟؟بله ( اگر l ≥ d)پيچيدگی زمانی؟؟O(bl)پيچيدگی حافظه؟؟O(bl)بهينه؟؟ خير

اسلاید 62: 62جستجوی با عمق محدودfunction DEPTH-LIMITTED-SEARCH( problem, limit) returns soln/fail/cutoff RECURSIVE-DLS(MAKE-NODE(INITAIL-STATE[ problem]), problem, limit)function RECURSIVE-DLS( node, problem, limit) returns soln/fail/cutoff cutoff occurred?  false if GOAL-TEST[ problem]( STATE[ node]) then return node else if DEPTH[ node] = limit then return cutoff else for each successor in EXPANDE( node, problem) do result  RECURSIVE-DLS( successor, problem, limit) if result = cutoff then cutoff occurred?  true else if result ≠ failure then return result if cutoff occurred? then return cutoff else return failure

اسلاید 63: 63جستجوی عميق کننده تکراری مشکل اصلی در جستجوی عمقی با عمق محدود شده (DLS) انتخاب يک محدوده عمقی مناسب است. در نقشه رومانی طول بزرگترين مسير بين دو شهر 9 می باشد(قطر)، و اين محدوده عمقی مناسب تر از 19 می باشد. اما در بيشتر فضاهای حالت انتخاب محدوده مناسب قبل از حل مسأله ميسر نمی باشد. جستجوی عميق کننده تکراری روشی برای تعيين محدوده عمقی مناسب با امتحان کردن تمامی محدوده ها ( از صفر به بالا) می باشد. يعنی اول عمق صفر، بعد عمق 1، بعد عمق 2 و ...

اسلاید 64: 64جستجوی عميق کننده تکراریfunction ITERATIVE-DEEPENING-SEARCH( problem) returns a solution inputs: problem, a problem for depth  0 to ∞ doresult  DEPTH-LIMITTED-SEARCH( problem, depth)if result ≠ cutoff then return result end

اسلاید 65: 65جستجوی عميق کننده تکراری جستجوی عميق کننده تکراری مزايای جستجوی سطحی و عمقی را با هم ترکيب می کند:جستجوی سطحی کامل و بهينه است.جستجوی عمقی دارای مصرف حافظه خطی می باشد. اين جستجو از نظر پيچيدگی زمانی مانند جستجوی سطحی می باشد به جز اينکه برخی حالات چند بار بسط داده می شوند.

اسلاید 66: 66جستجوی عميق کننده تکراری (l = 0)

اسلاید 67: 67جستجوی عميق کننده تکراری (l = 1)

اسلاید 68: 68جستجوی عميق کننده تکراری (l = 2)

اسلاید 69: 69جستجوی عميق کننده تکراری (l = 3)

اسلاید 70: 70خواص جستجوی عميق کننده تکراری کامل؟؟ بله پيچيدگی زمانی ؟؟(d + 1) b0 + db1 + (d – 1) b2 + … + bd = O(bd)پيچيدگی حافظه؟؟ O(bd)بهينه ؟؟ بله، (اگر هزينه گام = يک)می تواند برای کاوش درخت جستجوی هزينه يکسان اصلاح شود.

اسلاید 71: 71تعداد گره های گسترش يافته در BFS:1 + b + b2 + … + bd-1 + bdاگر b = 10 و d = 5 :1 + 10 + 100 + 1, 000 + 10,000 + 100, 000 = 111,111 در IDS:6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456محاسبه ميزان سربار:((123456 – 111111)/111111)* 100 = 11% با افزايش فاکتور انشعاب b ميزان سربار کاهش می يابد. در بدترين حالت b = 2، سربار 100% است و اين جستجو دو برابر زمان می برد. برای d های بزرگ: NIDS / NBFS = b / (b – 1)مقايسه کارآيي IDS و BFS

اسلاید 72: 72استدلال جلورو در مقابل عقبرو هدف روال جستجو، کشف يک مسير از ميان فضای حالت مسأله از يک حالت اوليه به يک حالت هدف می باشد. چنين جستجويی به دو روش ممکن است:(1) رو به جلو، از حالت اوليه به سمت حالت هدف(2) رو به عقب، از حالت هدف به سمت حالت اوليهفاکتورهای موثر در انتخاب جهت جستجو1- تعداد حالت های اوليه و حالت های هدف ( کمتر به بيشتر)مثال: رانندگی از يک محل ناآشنا به سمت منزل( عقبرو)2- فاکتور انشعاب در دو جهت ( کمتر)مثال: اثبات تئوری ( از يک اصل می توان تعداد زيادی تئوری نتيجه گرفت)( عقبرو)3- طبيعی بودن جهت جستجومثال: سيستم خبره تشخيص بيماری MYCIN ( جلورو)

اسلاید 73: 73جستجوی دو طرفه (Bidirectional Search) ايده، جستجوی همزمان: ( به شرطی که ميسر باشد) از حالت اوليه به سمت حالت هدف (forward) ، و از حالت هدف به سمت حالت اوليه .(Backward) اگر عمليات قابل وارونه کردن باشند( مانند معمای هشت)، می توان از جستجوی دو طرفه استفاده نمود، اما مثلا در مسأله تنگ آب تمام عمليات قابل وارونه سازی نمی باشند.مثال: b = 10 و d = 6 حستجوی سطحی: 1,111,111 گره را بررسی می کند جستجوی دو طرفه تنها 1,111 + 1,111 = 2,222 را بررسی می کند.

اسلاید 74: 74جستجوی دو طرفه (Bidirectional Search) در مسايلی که دارای حالات اوليه و هدف متعددی باشند، ممکن است با شکست روبرو شود.بايد يک راه موثر برای کنترل هر گره جديد وجود داشته باشدتا متوجه شويم که آيا اين گره قبلا در درخت جستجوی طرف ديگر ظاهر شده است يا خير ( اغلب با جدول پراکندگی)بايد تصميم بگيريم که در هر جهت از کدام روش جستجو استفاده کنيم. بايد گره های حداقل يکی از جستجوها در حافظه ذخيره شوند( جستجوی سطحی)، بنابراين پيچيدگی حافظه و زمان O(bd/2) است.

اسلاید 75: 75مقايسه استراتژيهای جستجو

اسلاید 76: 76حالات تکراری شکست در تشخيص حالت های تکرای می تواند يک مسأله خطی را به يک مسأله نمايي تبديل کند!

اسلاید 77: 77جستجوی گرافfunction GRAPH-SEARCH( problem, fringe) returns a solution or failureclosed  an empty setfringe  INSERT( MAKE-NODE(INITIAL-STATE[ problem]), fringe)loop doif fringe is empty then return failurenode  REMOVE-FRONT( fringe)if GOAL-TEST[ problem]( STATE[ node]) then return nodeif STATE[ node] is not in closed then add STATE[ node] to closed fringe  INSERTALL( EXPAND( node, problem), fringe)end

اسلاید 78: 78خلاصه فرموله سازی مسأله اغلب نياز به انتزاع جزييات مسأله دارد، تا بتوان فضای حالتی بدست آوردکه به صورت مقرون به صرفه ای قابل کاوش کرد ن و جستجو باشد.انواع استراتژی های ناآگاهانه وجود دارد. مصرف حافظه جستجوی عميق کننده تکراری دارای مرتبه خطی می باشد و زمان خيلی بيشتری نسبت به ساير روشهای ناآگاهانه مصرف نمی کند.