Power Point

Report
‫الگوريتم هاي جستجوي آگاهانه‬
‫تهيه کننده‪ :‬عبدالرضا ميرزايي‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫سرفصل مطالب‬
‫جستجوي اول‪-‬بهترين‬
‫جستجوي حريصانه‬
‫جستجوي *‪A‬‬
‫جستجوي *‪ A‬حافظه محدود‬
‫جستجوي عميق كننده تكراري*‪A‬‬
‫جستجوي اول بهترين بازگشتي )*‪(RBFA‬‬
‫*‪SMA‬‬
‫هيوريستيك ها‬
‫الگوريتم هاي جستجوي محلي‬
‫جستجوي ‪simulated annealing‬‬
‫الگوريتم هاي ژنتيك‬
‫جستجوي ‪online‬‬
‫‪2‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مرور‪ :‬جستجوي درخت‬
‫• استراتژي توسط ترتيب گسترش يافتن گره ها تعريف مي‬
‫شود‪.‬‬
‫‪3‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫جستجوي اول ‪ -‬بهترين‬
‫• نمونه اي از الگوريتم عمومي ‪ tree-search‬يا ‪ graph-search‬است‬
‫که در ان يک گره بر اساس يک تابع ارزيابي )‪ f(n‬براي گسترش‬
‫انتخاب مي شود‪.‬‬
‫• تابع ارزيابي ‪ evaluation function‬تخمين ”ميزان مطلوب بودن“ گره‬
‫• هربار مطلوب ترين گره گسترش نيافته را بسط مي دهد‪.‬‬
‫• پياده سازي‪:‬‬
‫• گره ها در ‪ fringe‬به ترتيب نزولي ميزان مطلوبيت مرتب مي شوند‪.‬‬
‫• يك صف اولويت‬
‫• حالت هاي خاص‬
‫• جستجوي حريصانه ‪Greedy search‬‬
‫‪4‬‬
‫• جستجوي *‪A‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫جستجوي اول ‪-‬بهترين حريصانه‬
‫• تابع هيوريستيك )‪h(n‬‬
‫• هزينة تخميني مسير از گره ‪ n‬تا نزديکترين گره هدف‬
‫• براي مثال‪ ،‬در نقشه روماني مي توان هزينة مسير از هر شهري‬
‫به بخارست را از طريق مسافت يك خط مستقيم از آن شهر به‬
‫بخارست تخمين زد‪.‬‬
‫)‪ hSLD(n‬فاصله مستقيم از ‪ n‬تا بخارست‬
‫جستجوي اول ‪-‬بهترين حريصانه‬
‫‪5‬‬
‫• جستجوي حريصانه گره اي را گسترش مي دهد كه به نظر مي‬
‫رسد نزديكترين گره به هدف ( بخارست) باشد‪.‬‬
‫• تابع ارزيابي )‪f(n)= h(n‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫نقشه روماني به همراه هزينه مراحل برحسب‬
‫‪6‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫‪km‬‬
‫جستجوي اول ‪-‬بهترين حريصانه‬
‫جستجوي اول ‪-‬بهترين حريصانه‬
‫جستجوي اول ‪-‬بهترين حريصانه‬
‫جستجوي اول ‪-‬بهترين حريصانه‬
‫خواص جستجوي اول ‪-‬بهترين حريصانه‬
‫•‬
‫•‬
‫•‬
‫•‬
‫كامل؟‬
‫–خير (ممکن است در حلقه بينهايت گير کند)‬
‫پيچيدگي زماني؟‬
‫– )‪ O(bm‬اما با يک هيوريستيک خوب مي تواند به شدت بهبود‬
‫يابد‬
‫پيچيدگي حافظه؟‬
‫– )‪ O(bm‬تمام گره ها را در حافظه نگه مي دارد‪.‬‬
‫بهينه؟‬
‫– خير (مثال در مثال قبل مسير بهينه اي وجود دارد که از ديد‬
‫جستجوي حريصانه مخفي مي ماند)‪.‬‬
‫‪11‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫حلقه بينهايت در جستجوي حريصانه‬
‫شروع‬
‫پايان‬
‫‪Iasi  Neamt  Iasi  Neamt ‬‬
‫‪12‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫جستجوي *‪A‬‬
‫• ايده‪ :‬از گسترش مسيرهايي كه تاكنون مشخص شده پرهزينه‬
‫مي باشند‪ ،‬اجتناب كن‪.‬‬
‫• تابع ارزيابي‬
‫)‪f(n) = g(n) + h(n‬‬
‫هزينة رسيدن به گره‬
‫‪n‬‬
‫هزينة تخميني‬
‫ارزانترين مسير از‬
‫گره ‪ n‬به هدف‬
‫‪13‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫هزينة ارزانترين‬
‫مسير گذرنده از گره‬
‫‪ n‬به هدف‬
‫مثال جستجوي *‪A‬‬
‫مثال جستجوي *‪A‬‬
‫مثال جستجوي *‪A‬‬
‫مثال جستجوي *‪A‬‬
‫مثال جستجوي *‪A‬‬
‫مثال جستجوي *‪A‬‬
‫هيوريستيك قابل قبول‬
‫• يك هيوريستيك )‪ h(n‬قابل قبول است اگر براي هر گره ‪n‬داشته‬
‫باشيم ‪:‬‬
‫• )‪h(n) ≤ h*(n‬‬
‫• که )‪ h*(n‬هزينه واقعي براي رسيدن به هدف از گره ‪ n‬مي باشد‪.‬‬
‫• يك هيوريستيك قابل قبول هرگز هزينه رسيدن به هدف را بيش از‬
‫حد تخمين نمي زند‪ ،‬يعني خوش بينانه است‪.‬‬
‫• مثال‪ :‬هيوريستيك )‪ hSLD(n‬هيچگاه فاصله را بيش از حد واقعي‬
‫تخمين نمي زند‪.‬‬
‫• قضيه‪ :‬اگر )‪ h(n‬قابل قبول باشد‪ A* ،‬با استفاده از ‪TREE-SEARCH‬‬
‫بهينه است‬
‫‪20‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫اثبات بهينگي *‪A‬‬
‫• فرض كنيد يك جواب زير بهينه مانند ‪ G2‬ايجاد شده و در ‪fringe‬‬
‫قرار دارد‪ .‬همچنين فرض کنيد ‪ n‬يك گره گسترش نيافته روي‬
‫كوتاهترين مسير به هدف بهينه ‪ G‬باشد‪.‬‬
‫‪since h(G2) = 0‬‬
‫‪since G2 is suboptimal‬‬
‫‪since h(G) = 0‬‬
‫‪from above‬‬
‫‪21‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫)‪= g(G2‬‬
‫)‪> g(G‬‬
‫)‪= g(G‬‬
‫)‪> f(G‬‬
‫)‪f(G2‬‬
‫)‪g(G2‬‬
‫)‪f(G‬‬
‫)‪f(G2‬‬
‫اثبات بهينگي *‪A‬‬
‫• فرض كنيد يك جواب زير بهينه مانند ‪ G2‬ايجاد شده و در ‪fringe‬‬
‫قرار دارد‪ .‬همچنين فرض کنيد ‪ n‬يك گره گسترش نيافته روي‬
‫كوتاهترين مسير به هدف بهينه ‪ G‬باشد‪.‬‬
‫‪from above‬‬
‫‪since h is admissible‬‬
‫)‪f(G‬‬
‫)‪h*(n‬‬
‫)‪g(n) + h*(n‬‬
‫)‪f(G‬‬
‫>‬
‫≤‬
‫≤‬
‫≤‬
‫)‪f(G2‬‬
‫)‪h(n‬‬
‫)‪g(n) + h(n‬‬
‫)‪f(n‬‬
‫چون )‪ f(G2) > f(n‬است *‪ A‬هيچگاه ‪ G2‬را براي گسترش انتخاب نمي کند‬
‫‪22‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫بهينگي *‪A‬‬
‫• اگر به جاي‪ TREE–SEARCH‬از‬
‫قضيه قبل ديگر صدق نمي كند‪.‬‬
‫• ممكن است راه حلهاي نيمه بهينه برگردانده شوند‪ ،‬زيرا –‪GRAPH‬‬
‫‪ SEARCH‬مي تواند ميسر بهينه به يك حالت تكراري را كنار بگذارد‪،‬‬
‫اگر اولين گره توليدي نباشد‪.‬‬
‫• دو راهکار براي حل اين مشكل‪:‬‬
‫‪GRAPH–SEARCH‬‬
‫استفاده كنيم‪ ،‬آنگاه‬
‫• اولين راه حل‪ ،‬اين است كه ‪ GRAPH–SEARCH‬را به نحوي توسعه بدهيم كه‬
‫از بين مسيري كه به يك گره مي رسد آن مسيري كه پرهزينه تر است را‬
‫كنار بگذارد‪ .‬اين روش فضاي زيادي اشغال مي كند‪ ،‬اما بهينگي را تضمين‬
‫مي كند‪.‬‬
‫• راه حل دوم‪ ،‬اطمينان از اين موضوع است كه مسير بهينه به هر حالت‬
‫کامپيوتر شود‪ .‬شرط سازگاري (يا‬
‫دنبال مي‬
‫است كه‬
‫‪ 23‬تكراري‪ ،‬هميشه اولين‬
‫دانشکده برق و‬
‫مسيرياصفهان‬
‫دانشگاه صنعتي‬
‫هيوريستيک هاي سازگار‬
‫• يك هيوريستيك سازگار‬
‫‪consistent‬‬
‫است اگر‬
‫)'‪h(n) ≤ c(n,a,n') + h(n‬‬
‫• شكلي از قانون كلي نامساوي مثلث است كه تصريح مي كند هيچ‬
‫ضلعي از يك مثلث نمي تواند بلندتر از مجموع دو ضلع ديگر باشد‪.‬‬
‫• هر هيوريستيك سازگار‪ ،‬قابل قبول نيز هست‪.‬‬
‫• قضيه‪ :‬اگر )‪ h(n‬سازگار باشد‪ A* ،‬با استفاده از –‪GRAPH‬‬
‫‪ SEARCH24‬بهينه است‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫هيوريستيک هاي سازگار‬
‫• اگر )‪ h(n‬سازگار باشد آنگاه )‪ f(n‬در طول هر مسيري‪ ،‬غيرنزولي‬
‫است‪.‬‬
‫)'‪= g(n') + h(n‬‬
‫)'‪= g(n) + c(n,a,n') + h(n‬‬
‫)‪≥ g(n) + h(n‬‬
‫)‪= f(n‬‬
‫)'‪f(n‬‬
‫• مي توان نتيجه گرفت كه رشته اي از گره ها كه توسط*‪ A‬با استفاده‬
‫از ‪ GRAPH–SEARCH‬گسترش يافته اند به ترتيب غيرنزولي )‪f(n‬‬
‫مي باشد‪.‬‬
‫• در نتيجه‪ ،‬اولين گره هدفي كه براي گسترش انتخاب مي شود بايد يك‬
‫بعدي حداقل به همان اندازه‬
‫اصفهانگره‬
‫تمامي‬
‫‪25‬راه حل بهينه باشد‪ ،‬زيرا‬
‫هايو کامپيوتر‬
‫دانشکده برق‬
‫دانشگاه صنعتي‬
‫بهينگي *‪A‬‬
‫• *‪ A‬به تدريج ‪ f-contour‬ها را اضافه مي کند‪.‬‬
‫‪26‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫خواص جستجوي *‪A‬‬
‫• اولين راه حل پيداشده‪ ،‬بايد يك راه حل بهينه باشد‬
‫• زيرا گره هاي هدف در تمامي ‪contour‬هاي بعدي داراي هزينه‬
‫‪ f‬بيشتري خواهند بود و در نتيجه هزينة ‪ G‬باالتري نيز دارند‬
‫(زيرا تمامي گره هاي هدف داراي ‪ h(n)=0‬هستند)‪.‬‬
‫• جستجوي *‪ A‬كامل است‪.‬‬
‫• همان طور كه نوارهاي با ‪ f‬در حال افزايش را اضافه مي كنيم‪،‬‬
‫بايد باالخره به نواري برسيم كه در آنجا ‪ f‬مساوي هزينة مسير تا‬
‫يك حالت هدف است‪.‬‬
‫‪27‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫خواص جستجوي *‪A‬‬
‫•‬
‫•‬
‫•‬
‫•‬
‫كامل؟‬
‫–بله‪ ،‬مگر اينكه تعدادي نامحدود گره با )‪ f ≤ f(G‬وجود داشته‬
‫باشد‪.‬‬
‫– *‪ A‬در گراف هاي متناهي محلي ( با فاكتور انشعاب محدود)‬
‫كامل مي باشد‬
‫پيچيدگي زماني؟‬
‫– نمايي‬
‫پيچيدگي حافظه؟‬
‫– نمايي تمام گره ها را در حافظه نگه مي دارد‪.‬‬
‫بهينه؟‬
‫‪28‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫خواص جستجوي *‪A‬‬
‫• بهينه؟‬
‫– بله نمي تواند ‪ fi+1‬را گسترش دهد مگر آنکه ‪ fi‬تمام شده باشد‪.‬‬
‫– *‪ A‬تمام گره ها با *‪ f(n) <f‬را گسترش مي دهد‪.‬‬
‫– *‪ A‬برخي گره ها با *‪ f(n) =f‬را گسترش مي دهد‪.‬‬
‫– *‪ A‬هرگز گره اي با *‪ f(n) >f‬را گسترش نمي دهد‪.‬‬
‫• *‪ A‬داراي كارآيي بهينه ‪ optimally efficient‬مي باشد‬
‫• يعني هيچ الگوريتم بهينة ديگري تضمين نمي كند كه تعداد گره هايي‬
‫كه گسترش مي دهد از *‪ A‬كمتر باشد‪.‬‬
‫• علت اين امر آن است كه هر الگوريتمي كه تمامي گره ها را با )‪f(n‬‬
‫*‪ <f‬را گسترش ندهد خطر از دست دادن راه حل بهينه را دارد‪.‬‬
‫‪29‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫جستجوي *‪ A‬با حافظه محدود‬
‫•‬
‫•‬
‫•‬
‫•‬
‫زمان محاسبه‪ ،‬نقطه ضعف اصلي*‪ A‬نيست‪.‬‬
‫از آنجا كه اين الگوريتم‪ ،‬تمامي گره هاي توليد شده را در‬
‫حافظه نگهداري مي كند معموالً بسيار بيشتر از آنكه وقت‬
‫كم بياورد‪ ،‬حافظه كم مي آورد‪.‬‬
‫در مورد بسياري از مسائل بزرگ‪ ،‬عملي نيست‪.‬‬
‫چند راه حل براي مسأله حافظه در *‪A‬‬
‫• جستجوي عميق كننده تكراري *‪(IDA*) A‬‬
‫• جستجوي اول‪-‬بهترين بازگشتي )‪(RBFS‬‬
‫• جستجوي (ساده شده) *‪ A‬با حافظه محدود )*‪((S)MBA‬‬
‫‪30‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫*‪IDA‬‬
‫• ايدة استفاده از راهکار عميق کننده تكراري در زمينة‬
‫جستجوي آگاهانه‬
‫• تفاوت اصلي بين ‪ IDS‬و *‪IDA‬‬
‫• در*‪ IDA‬به جاي محدوده عمقي از محدوده ‪( f‬يعني ‪)g+h‬‬
‫استفاده مي شود‪.‬‬
‫• در هر تكرار‪ ،‬مقدار برش‪ ،‬كوچكترين هزينة ‪ f‬ميان تمام‬
‫گره هايي است که از برش تكرار قبلي بيشتر باشند‪.‬‬
‫‪31‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫جستجوي اول ‪-‬بهترين بازگشتي (‪)RBFS‬‬
‫• يك الگوريتم بازگشتي با فضاي خطي كه سعي مي كند از جستجوي‬
‫اول‪ -‬بهترين استاندارد تقليد كند‪.‬‬
‫• ساختار‪ RBFS‬مشابه جستجوي اول عمق بازگشتي است‪ ،‬اما به جاي‬
‫ادامه دادن مسير فعلي به طور نامشخص‪ ،‬خود را از مقدار بهترين‬
‫‪f‬مسير جايگزين قابل دسترس از تمام اجداد گره فعلي مطلع نگه‬
‫مي دارد‪.‬‬
‫• اگر گره فعلي از اين محدوده فراتر رود‪ ،‬تابع بازگشتي آن را به‬
‫عقب برمي گرداند تا روي يك مسير جايگزين ديگر قرار گيرد‪.‬‬
‫• در بازگشت به عقب مقدار ‪ f‬مربوط به هر گره موجود در مسير را‬
‫با بهترين مقدار ‪ f‬فرزندانش جايگزين مي کند‪.‬‬
‫ممكن مي باشد‪.‬‬
‫هنوز‬
‫•‪32‬بنابراين گسترش مجدددانشگاهنتيجه‬
‫برق و کامپيوتر‬
‫فعليدانشکده‬
‫صنعتي اصفهان‬
‫جستجوي اول ‪-‬بهترين بازگشتي (‪)RBFS‬‬
‫‪33‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫جستجوي اول ‪-‬بهترين بازگشتي (‪)RBFS‬‬
‫‪34‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫جستجوي اول ‪-‬بهترين بازگشتي (‪)RBFS‬‬
‫‪35‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫جستجوي اول ‪-‬بهترين بازگشتي (‪)RBFS‬‬
‫‪36‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫خواص جستجوي ‪RBFS‬‬
‫• ‪RBFS‬كمي كارآتر از *‪ IDA‬مي باشد‬
‫– هنوز گسترش اضافي گره ها وجود دارد( تغيير عقيده)‬
‫• پيچيدگي زماني؟‬
‫– بيان پيچيدگي زماني آن نسبتا ً مشكل است‪ :‬هم به دقت تابع هيوريستيك‬
‫بستگي دارد و هم به اين كه در حين گسترش گره ها‪ ،‬بهترين مسير هر چند‬
‫وقت يكبار تغيير مي كند‪.‬‬
‫– مانند *‪ IDA‬در معرض افزايش نمايي پيچيدگي زماني قرار دارد‬
‫• پيچيدگي حافظه؟‬
‫– )‪O(bd‬‬
‫• بهينه؟‬
‫– همانند *‪ ، A‬الگوريتم ‪ RBFS‬نيز يك الگوريتم بهينه است اگر تابع‬
‫هيوريستيك ‪ h‬قابل قبول باشد‪.‬‬
‫‪37‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫خواص جستجوي ‪RBFS‬‬
‫•‬
‫•‬
‫•‬
‫•‬
‫‪ RBFS‬و *‪ IDA‬هر دو‬
‫ممكن است در معرض افزايش نمايي بالقوه در پيچيدگي همراه با‬
‫جستجو در گرافها قرار بگيرند‪.‬‬
‫آنها نمي توانند حالتهاي تكراري‪ ،‬به جز آنهايي را كه بر روي مسير‬
‫فعلي قرار دارند بررسي كنند‪ .‬در نتيجه‪ ،‬ممكن است يك حالت را‬
‫چندين بار اكتشاف كنند‪.‬‬
‫از ميزان بسيار كم حافظه رنج مي برند‪.‬‬
‫• *‪ IDA‬فقط يك عدد را نگهداري مي كند (محدوديت مقدار فعلي ‪)f‬‬
‫• ‪ RBFS‬اطالعات بيشتري را در حافظه نگهداري مي كند‪ ،‬ولي فقط از‬
‫)‪ O(bd‬حافظه استفاده مي کند‪.‬‬
‫‪ • 38‬حتي اگر حافظه بيشتري در دسترس باشد نمي توانند از آن استفاده كنند‪.‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫*‪(Simplified) Memory Bounded A‬‬
‫ايده‪ :‬استفاده از تمامي حافظه موجود‬
‫– يعني‪ ،‬گسترش بهترين گره هاي برگي تا زماني كه حافظه‬
‫موجود پر شود‪.‬‬
‫• *‪ SMA‬دقيقا مثل *‪ A‬عمل مي كند‪ ،‬يعني تا زماني كه‬
‫حافظه پر شود‪ ،‬بهترين گره را گسترش مي دهد‪.‬‬
‫• در صورت پر شدن حافظه هميشه بدترين گره برگي‬
‫(گرهي با بيشترين مقدار ‪ )f‬را از حافظه حذف مي كند‬
‫• اطالعات گره هاي فراموش شده را در پدرشان ذخيره مي‬
‫كند‬
‫‪39‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫*‪(Simplified) Memory Bounded A‬‬
‫• *‪SMA‬‬
‫• كامل است‪ ،‬اگر راه حل دست يافتني وجود داشته باشد (يعني‬
‫اگر عمق كم عمقترين گره هدف كمتر از اندازة حافظه باشد)‪.‬‬
‫• اين الگوريتم بهينه است در صورتي كه راه حل بهينة دست‬
‫يافتني وجود داشته باشد‪ .‬در غير اين صورت بهترين راه حل‬
‫دستيافتني را برمي گرداند‪.‬‬
‫‪40‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫هيوريستيك هاي قابل قبول‬
‫• مثال براي پازل ‪ 8‬تايي‪:‬‬
‫‪ h1‬تعداد كاشيهايي كه در جاي خود قرار نگرفته اند‪.‬‬
‫‪ h2‬مجموع فواصل افقي و عمودي كاشيها از موقعيتهاي هدفشان‬
‫(فاصله ‪ city block‬يا ‪Manhattan‬‬
‫هر دو قابل قبول‬
‫‪h1(S) = 8‬‬
‫‪h2(S) = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18‬‬
‫‪41‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫• اگر بازاء هر ‪ n‬داشته باشيم )‪(h2(n) ≥ h1(n‬و هر دو‬
‫هيوريستيك قابل قبول باشند) آنگاه ‪ h2‬بر ‪ h1‬تسلط دارد و‬
‫براي جستجو بهتر مي باشد‪.‬‬
‫• مثال هزينه جستجو‪ :‬تعداد گره هاي توليد شده در عمق هاي مختلف‪:‬‬
‫‪• d=12‬‬
‫‪IDS = 3,644,035 nodes‬‬
‫‪A*(h1) = 227 nodes‬‬
‫‪A*(h2) = 73 nodes‬‬
‫‪• d=24‬‬
‫‪IDS = too many nodes‬‬
‫‪A*(h1) = 39,135 nodes‬‬
‫‪A*(h2) = 1,641 nodes‬‬
‫‪42‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫ضريب انشعاب موثر *‪b‬‬
‫ضريب انشعاب موثر )‪:(EBF‬‬
‫اگر تعداد گره هاي گسترش يافته توسط روال جستجو ‪ N‬و عمق راه حل ‪d‬‬
‫باشد *‪ b‬به صورت زير محاسبه مي شود‪:‬‬
‫‪N+1 = 1+b* + (b*)2+ … + (b*)d‬‬
‫مثال‪ :‬اگر *‪ A‬راه حلي را در عمق ‪ 5‬با استفاده از ‪ 52‬گره پيدا كند‪،‬‬
‫ضريب انشعاب موثر؟‬
‫‪53 = 1 + b* + (b*)2 +…(b*)5‬‬
‫‪b* = 1.92‬‬
‫• در يك هيوريستيك هر چه فاكتور انشعاب به يك نزديكتر باشد‪ ،‬بهتر‬
‫است و آن هيوريستيك كيفيت كشف كنندگي بيشتري دارد‪.‬‬
‫‪43‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫رابطه بين هزينه جستجو و ضريب انشعاب موثر‬
‫‪44‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫ابداع توابع هيوريستيك‬
‫•‬
‫•‬
‫•‬
‫•‬
‫مسأله اي كه تعداد كمتري محدوديت براي اقدامات دارد‪ ،‬يك‬
‫مسألةتعديل شده ‪ relaxed‬ناميده مي شود‪.‬‬
‫هزينة يك راه حل بهينه براي يك مسألة تعديل شده‪ ،‬يك هيوريستيک‬
‫قابل قبول براي مسألة اصلي است‪.‬‬
‫هزينه راه حل بهينه يك مسأله تعديل شده‪ ،‬بيشتر از هزينه راه حل‬
‫بهينه در مسأله واقعي نيست‪.‬‬
‫مثال‪ :‬پازل ‪ 8‬تايي‪ .‬يك كاشي مي تواند از خانه ‪ A‬به خانه ‪ B‬برود‬
‫اگر ‪ A‬مجاور ‪ B‬باشد و ‪ B‬خالي باشد‪.‬‬
‫‪45‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫ابداع توابع هيوريستيك‬
‫• مثال‪ :‬پازل ‪ 8‬تايي‪ .‬يك كاشي مي تواند از خانه ‪ A‬به خانه ‪ B‬برود‬
‫اگر ‪ A‬مجاور ‪ B‬باشد و ‪ B‬خالي باشد‪ .‬ميتوانيم با حذف يك يا هر دو‬
‫شرط‪ ،‬سه مسألة تعديل شده توليد كنيم‪:‬‬
‫• يك كاشي مي تواند از خانه ‪ A‬به خانه ‪ B‬برود اگر ‪ A‬مجاور ‪ B‬باشد‪)h2( .‬‬
‫• يك كاشي مي تواند از خانه ‪ A‬به خانه ‪ B‬برود اگر ‪ B‬خالي باشد‪.‬‬
‫• يك كاشي مي تواند از خانه ‪ A‬به خانه ‪ B‬برود‪)h1( .‬‬
‫‪46‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫الگوريتم هاي جستجوي محلي و مسائل بهينه سازي‬
‫• در بسياري از مسائل بهينه سازي‪ ،‬مسير راه حل اهميت‬
‫ندارد؛ خود حالت هدف پاسخ مسأله مي باشد‪.‬‬
‫• فضاي حالت = مجموعه پيكره بندي هاي كامل‬
‫• هدف = يافتن يك پيكره بندي كه محدوديت هاي مسأله را ارضاء‬
‫كند‪ ،‬مانند مساله ‪ -n‬وزير‬
‫• در چنين مواردي مي توان از الگوريتم هاي جستجوي‬
‫محلي بهره گرفت‪.‬‬
‫• يك حالت ”فعلي“ را به تنهايي در نظر بگير؛ سعي كن آن را‬
‫بهبود ببخشي‪.‬‬
‫‪47‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫الگوريتم هاي جستجوي محلي و مسائل بهينه سازي‬
‫• جستجوي محلي = استفاده از يك حالت فعلي و حركت به‬
‫حالت هاي همسايه‬
‫• مزايا‪:‬‬
‫– استفاده از حافظه بسيار كم‬
‫– يافتن راه حل هاي معقول در اغلب موارد در فضاهاي حالت‬
‫بزرگ و يا نامحدود‬
‫• مفيد براي مسائل بهينه سازي محض‬
‫– يافتن بهترين حالت بر طبق تابع هدف (‪)objective function‬‬
‫‪48‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫‪State space landscape‬‬
‫• يك ‪ landscape‬هم شامل "محل" (كه توسط حالت تعريف مي شود)‬
‫و هم شامل "ارتفاع" (كه توسط مقدار تابع هيوريستيک هزينه يا تابع‬
‫هدف تعريف مي شود) مي باشد‪.‬‬
‫• اگر ارتفاع متناظر هزينه باشد‪ ،‬آنگاه هدف يافتن عميقترين دره (يك‬
‫كمينة سراسري) است و اگر ارتفاع متناظر با تابع هدف باشد‪ ،‬آنگاه‬
‫هدف يافتن بلندترين قله (يك بيشينة سراسري) است‪.‬‬
‫• يك الگوريتم جستجوي محلي كامل‪ ،‬هدف را (در صورت وجود) پيدا‬
‫مي كند و يك الگوريتم بهينه يك كمينه يا بيشينة سراسري را پيدا مي‬
‫كند‪.‬‬
‫‪49‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫‪State space landscape‬‬
‫‪50‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫تپه نوردي( يا گراديان صعودي‪/‬نزولي)‬
‫• الگوريتم جستجوي تپه نوردي فقط از يك حلقه تشكيل مي شود كه‬
‫مدام در جهت افزايش مقدار حركت مي كند (يعني به سمت باالي‬
‫تپه)‪.‬‬
‫• الگوريتم هنگامي خاتمه پيدا مي كند كه به قلّه اي برسد كه در آنجا‬
‫هيچ همسايه اي مقدار بيشتري نداشته باشد‪.‬‬
‫• اين الگوريتم‪ ،‬درخت جستجو را نگهداري نمي كند‪ .‬بنابراين‪،‬‬
‫ساختمان دادة گره فعلي تنها نياز به ثبت حالت و مقدار تابع هدفش‬
‫را دارد‪.‬‬
‫• تپه نوردي‪ ،‬فراتر از همسايه هاي مجاور حالت فعلي را نگاه نمي‬
‫كند‪.‬‬
‫‪51‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫تپه نوردي( يا گراديان صعودي‪/‬نزولي)‬
‫‪52‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مثال‪-n :‬وزير‬
‫• ‪ n‬وزير را در يك صفحه شطرنج ‪ n * n‬به گونه اي قرار بده كه‬
‫هيچ دو وزيري در يك سطر‪ ،‬ستون و يا قطر قرار نگيرند‪.‬‬
‫• ‪ -8‬وزير‪:‬‬
‫• فرمول بندي حالت كامل‪ :‬هر حالت شامل ‪ 8‬وزير يعني يکي در هر ستون‬
‫• تابع پسين همه حالتهاي ممکني که با جابجايي يک وزير به مربع ديگري‬
‫در همان ستون توليد مي شود را برمي گرداند‪ .‬هر حالت ‪ 7*8‬پسين دارد‪.‬‬
‫• تابع هيوريستيك ‪ h‬تعداد جفتهايي از وزيرهاست كه چه به صورت مستقيم‬
‫و چه غير مستقيم در حال حمله به يكديگر هستند‪.‬‬
‫• كمينة سراسري اين تابع صفر است كه فقط در راه حل كامل اتفاق مي افتد‪.‬‬
‫‪53‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مثال‪-n :‬وزير‬
‫‪ 5‬حرکت‬
‫‪h=1‬‬
‫بهترين پسين داراي ‪ h=12‬است‬
‫‪54‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫‪h=17‬‬
‫تپه نوردي‬
‫• تپه نوردي اغلب به داليل زير گير مي كند‪:‬‬
‫• بيشينه هاي محلي‪ :‬الگوريتمهاي تپه نوردي كه به همسايگي يك‬
‫بيشينة محلي مي رسند‪ ،‬رو به باال به سمت قلّه كشيده مي شوند‪،‬‬
‫ولي پس از آن گير مي كنند و جاي ديگري نمي روند‪.‬‬
‫• ‪ :Ridge‬داراي يك رشته بيشينة محلي هستند كه گذشتن از آنها‬
‫براي الگوريتمهاي حريص بسيار مشكل است‪.‬‬
‫• فالتها‪ :‬فالت ناحيه اي از دورنماي فضاي حالت است كه در آن‬
‫تابع ارزياب‪ ،‬ثابت است‪ .‬فالت مي تواند يك بيشينة محلي مسطح‬
‫باشد كه از آن هيچ مسير رو به بااليي وجود ندارد يا يك شانه‬
‫باشد كه از آن بتوان به باالتر هم رفت‪.‬‬
‫‪55‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫انواع ديگر تپه نوردي‬
‫• تپه نوردي اتفاقي‬
‫‪stochastic hill climbing‬‬
‫• به صورت تصادفي از ميان حركتهاي رو به باال يكي را انتخاب‬
‫مي كند‪.‬‬
‫• احتمال اين انتخاب مي تواند براساس شيب حركتهاي رو به باال‬
‫تغيير كند‪.‬‬
‫• اين روش معموالً كندتر از تيزترين شيب به نتيجه مي رسد‪ ،‬اما‬
‫در بعضي از ‪ landscape‬هاي حالت‪ ،‬بهترين راه حل را پيدا مي‬
‫كند‪.‬‬
‫‪57‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫انواع ديگر تپه نوردي‬
‫• تپه نوردي اولين گزينه‪،‬‬
‫‪first choice hill climbing‬‬
‫• تپه نوردي اتفاقي را به كار مي گيرد به اين صورت كه به‬
‫صورت تصادفي پسين توليد مي كند تا زماني كه پسيني توليد شود‬
‫كه از حالت فعلي بهتر باشد‪ .‬اين راهبرد هنگامي مناسب است كه‬
‫يك حالت داراي تعداد زيادي (مثالً هزار) پسين باشد‪.‬‬
‫• تپه نوردي با شروع مجدد تصادفي‬
‫‪random restart hill climbing‬‬
‫• يك مجموعه جستجوي تپه نوردي را از حالتهاي شروع تصادفي‬
‫اجرا مي كند و هنگامي كه يك هدف پيدا شد متوقف ميشود‪ .‬اين‬
‫روش با احتمال نزديك به يك‪ ،‬كامل مي باشد‪.‬‬
‫‪58‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫سردسازي شبيه سازي شده‬
‫•‬
‫•‬
‫•‬
‫•‬
‫الگوريتم تپه نوردي كه هرگز حركت رو به پايين به سمت حالتهايي‬
‫با مقادير كمتر (يا هزينة باالتر) را انجام نمي دهد‪ ،‬ناكامل بودنش‬
‫قطعي است‪ ،‬زيرا ممكن است در يك بيشينة محلي گير كند‪.‬‬
‫در مقابل‪ ،‬يك راهپيمايي كامالً تصادفي ‪(random walk‬يعني حركت‬
‫به پسيني كه از مجموعة پسينها به طور يكنواخت و كامالً تصادفي‬
‫انتخاب شده است) كامل ولي به شدت ناكارآمد مي باشد‪.‬‬
‫در نتيجه‪ ،‬تالش در جهت تركيب تپه نوردي با يك راهپيمايي‬
‫تصادفي كه هم كارآمد و هم كامل باشد‪ ،‬كار معقولي به نظر مي‬
‫رسد‪.‬‬
‫سردسازي شبيه سازي شده‪ ،‬يك چنين الگوريتمي است‪.‬‬
‫‪59‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫سردسازي شبيه سازي شده‬
‫• ايده‪:‬‬
‫‪Simulated Annealing‬‬
‫• از ماكزيمم هاي محلي با انجام حركت هاي بد فرار كن‪.‬‬
‫• اما به تدريج اندازه و تعداد حركات بد ( به سمت پايين) را كم‬
‫كن‬
‫‪60‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫سردسازي شبيه سازي شده‬
‫•‬
‫•‬
‫•‬
‫•‬
‫پيشروي مانند تپه نوردي مي باشد‪ ،‬اما در هر مرحله حالت‬
‫بعدي به طور تصادفي انتخاب مي شود‪.‬‬
‫اگر حالت بعدي انتخاب شده بهتر باشد‪ ،‬همواره به آن حالت‬
‫بعدي خواهيم رفت‪.‬‬
‫در غير اين صورت‪ ،‬تنها با يك احتمال به آن حالت خواهيم‬
‫رفت و اين احتمال به صورت نمايي كاهش مي يابد‪.‬‬
‫تابع احتمال‪:‬‬
‫• دما ‪T:‬‬
‫• ميزان كاهش در هر مرحله ‪ΔE:‬‬
‫‪61‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫خواص جستجوي ‪SA‬‬
‫• در مقادير باالتر‪ T‬احتمال انجام حركات بد (رفتن به سمت‬
‫پايين) بيشتر است (مانند جستجوي تصادفي رفتار مي كند)‪.‬‬
‫• با كاهش ‪ T‬اين احتمال كاهش يافته و در‪ T=0‬اين احتمال به‬
‫صفر مي رسد‪ ( .‬مانند تپه نوردي رفتار مي كند)‬
‫• مي توان ثابت کرد که اگر ‪ T‬به اندازه کافي آرام کاهش يابد‬
‫با احتمال نزديک به يک ‪ SA‬يک پاسخ بهينه را خواهد‬
‫يافت‪.‬‬
‫‪62‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫جستجوي پرتوي محلي‬
‫•‬
‫•‬
‫•‬
‫•‬
‫•‬
‫‪Local Beam Search‬‬
‫شروع با ‪ k‬حالت كه به طور تصادفي ايجاد شده اند‪.‬‬
‫در هر تكرار‪ ،‬تمام فرزندان براي هر ‪ k‬حالت توليد مي شوند‪.‬‬
‫اگر يكي از آنها حالت هدف بود جستجو متوقف مي شود و در‬
‫غير اين صورت از ميان ليست كامل فرزندان ‪ k‬تا از بهترين ها‬
‫انتخاب مي شوند و مرحله باال تكرار مي شود‪.‬‬
‫تفاوت با جستجوي با شروع مجدد تصادفي‬
‫• در يك جستجوي با شروع مجدد تصادفي‪ ،‬هر فرآيند جستجو به طورمستقل‬
‫از بقيه اجرا مي شود‪.‬‬
‫• در يك جستجوي پرتوي محلي‪ ،‬اطالعات سودمند در بين ‪ k‬جستجوي موازي‬
‫رد و بدل مي گردد‪.‬‬
‫‪63‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫جستجوي پرتوي اتفاقي‬
‫‪Stochastic beam search‬‬
‫• مشکل جستجوي پرتوي محلي‬
‫• اين روش ممکن است از نبود تنوع بين ‪ k‬حالت رنج ببرد‪ .‬به سرعت‬
‫تمامي آنها در محدوده کوچکي از فضاي حالت جمع شوند‪.‬‬
‫• جستجوي پرتوي اتفاقي‬
‫• به جاي انتخاب ‪ k‬بهترين از مجموعه پسينهاي منتخب ‪ k‬پسين را به‬
‫صورت تصادفي انتخاب کند‪.‬‬
‫• احتمال انتخاب هر پسين خاص تابعي از برازندگي آن‬
‫• الگوريتم ژنتيک‬
‫• نمونه اي از جستجوي پرتوي اتفاقي که توليد حالتهاي پسين عالوه بر تغيير‬
‫يك حالت‪ ،‬از تركيب دو حالت والد نيز (تركيب جنسي) انجام مي شود‪.‬‬
‫‪64‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫الگوريتم ژنتيک‬
‫‪65‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مثال الگوريتم ژنتيک‪ – n :‬وزير‬
‫• تابع برازندگي ‪ :‬تعداد جفت وزير هايي كه يكديگر را تهديد‬
‫نمي كنند‪( .‬مينيمم‪ :‬صفر‪ ،‬ماكزيمم‪)8*7/2=28 :‬‬
‫‪24/(24+23+20+11) = 31%‬‬
‫‪23/(24+23+20+11) = 29%‬‬
‫…‬
‫‪66‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مثال الگوريتم ژنتيک‪ – n :‬وزير‬
‫عملگر‬
‫‪67‬‬
‫‪Crossover‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫جستجوي ‪online‬‬
‫• تا كنون تمام الگوريتم هاي مطرح شده ‪ offline‬بودند‪.‬‬
‫• ‪ Offline‬راه حل قبل از اجراي آن معين است‬
‫• ‪ Online‬محاسبه و عمل بصورت يك در ميان‬
‫• جستجوي ‪ online‬براي محيط هاي پويا و نيمه پويا ضروري‬
‫مي باشد‬
‫• در نظر گرفتن تمامي امكان هاي مختلف غير ممكن است‬
‫• استفاده شده در مسائل اكتشافي‬
‫• حالت ها و اعمال ناشناخته‬
‫• مثال‪ :‬يك روبات در يك محيط جديد‪ ،‬يك نوزاد و ‪...‬‬
‫‪68‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مسائل جستجوي ‪online‬‬
‫• دانش عامل‪:‬‬
‫• عمل (ها)‪ :‬ليست اعمال مجاز در حالت ‪s‬‬
‫• تابع هزينه گام ( پس از تعيين ’‪c(s, a, s’) )s‬‬
‫• )‪GOAL-TEST(s‬‬
‫• فرضيات‬
‫• عامل مي تواند حالت قبلي را تشخيص دهد‬
‫• اعمال قطعي هستند‬
‫• دستيابي به هيوريستيك قابل قبول )‪h(s‬‬
‫‪69‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مسائل جستجوي ‪online‬‬
‫• هدف‪ :‬رسيدن به حالت هدف با حداقل هزينه‬
‫• هزينه = كل هزينه مسير پيموده شده‬
‫• نسبت رقابتي = مقايسه هزينه با هزينه مسير راه حل در‬
‫حالتي كه فضاي جستجو شناخته شده باشد‬
‫• مي تواند نا محدود باشد‬
‫• مثال در مواردي كه عامل به طور تصادفي به يك بن بست مي‬
‫رسد‬
‫• فضاي حالت قابل کاوش امن‬
‫• از هر حالت دست يافتني حداقل يک حالت هدف قابل دسترس‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫‪ 70‬باشد‬
‫مسائل جستجوي ‪online‬‬
‫• حالت هاي مالقات شده ‪ A‬و ‪ S‬حالت بعدي؟‬
‫• در يكي از فضاهاي حالت شكست مي خورد‬
‫• هيچ الگوريتمي نمي تواند از بن بست ها در تمامي فضاهاي حالت اجتناب‬
‫كند‬
‫‪71‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫مسائل جستجوي ‪online‬‬
‫• يك محيط ‪ 2‬بعدي را تصور كنيد كه حريف قادر است در حين كاوش‬
‫عامل فضاي حالت را بسازد‬
‫• باعث مي شود يک کارگزار جستجوي برخط يک مسير اجبارا‬
‫ناکارامد را به سمت هدف دنبال کند‪.‬‬
‫‪72‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫کارگزارهاي جستجوي ‪online‬‬
‫• عامل يك نقشه از محيط نگهداري مي كند‬
‫– نقشه بر اساس ورودي ادراكي بهنگام مي شود‬
‫– از اين نقشه براي انتخاب عمل بعدي استفاده مي شود‬
‫• به تفاوت مثال با *‪ A‬دقت كنيد‬
‫• يك نسخه ‪ online‬تنها مي تواند گره اي را گسترش دهد كه به‬
‫طور فيزيكي در آن قرار داشته باشد‪.‬‬
‫• براي اجتناب از جابجايي در عرض درخت بهتر است گره ها‬
‫را به ترتيب محلي گسترش دهيم‪ .‬مثال جستجوي اول عمق‪،‬‬
‫جستجوي محلي و ‪...‬‬
‫‪73‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫کارگزارجستجوي ‪ online‬با کاوش اول عمق‬
‫‪74‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫جستجوي محلي ‪online‬‬
‫• جستجوي تپه نوردي ‪ online‬مي باشد!!!‬
‫• يك حالت ذخيره شده است‬
‫• عملكرد بد به دليل وجود ماكزيمم هاي محلي‬
‫• شروع مجدد تصادفي غير ممكن است‬
‫• راهکار ‪ :1‬گام برداشتن تصادفي ‪random walk‬‬
‫• يکي از اقدامات موجود حالت فعلي را به صورت تصادفي توليد‬
‫ميکند‪.‬‬
‫• مي توان به اقداماتي که تا کنون امتحان نشده اند احتمال باالتري‬
‫داد‪.‬‬
‫‪75‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫جستجوي محلي ‪online‬‬
‫• گام برداشتن تصادفي ‪random walk‬‬
‫• اگر فضا متناهي باشد گام برداشتن تصادفي در نهايت يک هدف‬
‫را پيدا مي کند يا کاوشهايش را کامل مي کند‪.‬‬
‫• اين فرايند ممکن است خيلي کند باشد ( مي تواند حاالت‬
‫بسياري را به صورت نمايي توليد كند)‬
‫‪76‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫جستجوي محلي ‪online‬‬
‫• راهکار ‪ :2‬اضافه نمودن حافظه به تپه نورد‬
‫•‬
‫•‬
‫•‬
‫•‬
‫‪77‬‬
‫ذخيره بهترين تخمين فعلي )‪ H(s‬از هزينه رسيدن به هدف‬
‫)‪ H(s‬در ابتدا تخمين هيوريستيك )‪ h(s‬مي باشد‪.‬‬
‫پس از آن بر اساس تجربه بهنگام مي شود‪.‬‬
‫هزينه تخميني رسيدن به هدف از طريق همسايه اي مانند ’‪،s‬‬
‫هزينه رسيدن به ’‪ s‬به عالوه ي هزينه ي تخميني رسيدن به‬
‫هدف از انجاست يعني )’‪c(s,a,s’)+H(s‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫*‪Learning real-time A‬‬
‫‪78‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫*‪Learning real-time A‬‬
‫‪79‬‬
‫دانشگاه صنعتي اصفهان دانشکده برق و کامپيوتر‬
‫يادگيري در جستجوي ‪online‬‬
‫• نقشه محيط‬
‫• نتيجه هر اقدام در هر حالت‬
‫• در محيطهاي معين تنها يک تجربه براي هر اقدام کافي است‬
‫• براوردهاي دقيق تر از ارزش هر حالت‬
‫• با استفاده از قوانين به روزاوري محلي مشابه *‪LRTA‬‬
‫• به مجرد تعيين دقيق مقادير تپه نوردي محض راهبرد بهينه‬
‫است‪.‬‬
‫• يادگيري مفهوم اعمال‬
‫• اقدام ‪ up‬مختصات ‪ Y‬را افزايش مي دهد مگر اينکه ديواري بر‬
‫‪ 80‬سر راه قرار داشتهدانشگاهباشد‪.‬‬
‫صنعتي اصفهان دانشکده برق و کامپيوتر‬

similar documents