موضوع مقاله: اکتشاف قابل قبول | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # اکتشاف قابل قبول | مقدمه: در علوم رایانه، به‌ طور خاص در الگوریتم‌های مربوط به مسیریابی، زمانی به تابع هیوریستیک یک تابع قابل قبول گفته می‌ شود که هزینه دست‌ یابی به هدف را بیش از مقدار واقعی تخمین نزند، یعنی هزینه‌ ای که از گره فعلی برای رسیدن به گره هدف تخمین می‌ زند از کمترین هزینه ممکن بیشتر نباشد. | ## بخش 1: اکتشاف قابل قبول | همه اکتشاف‌های سازگار قابل قبول هستند، در حالی که همه اکتشافی های قابل قبول، سازگار نیستند. الگوریتم های جستجو الگوریتم‌های جستجو می‌توانند آگاهانه و نا آگاهانه باشند در الگوریتم جستجوی آگاهانه از هیوریستیک قابل قبول برای تخمین هزینه‌ رسیدن به گره هدف استفاده می‌ شود . این الگوریتم‌ از این مفهوم برای یافتن یک مسیر بهینه تخمینی از گره فعلی به گره هدف استفاده می کند. مثلا در الگوریتم جستجوی A* که مبنای آن بر اجتناب از گسترش مسیر‌هایی است که هم‌ اکنون گران هستند، تابع ارزیابی (از گره‌ n ام تا گره هدف) برابر است: به‌طوری که: = تابع ارزیابی = هزینه‌ ای که تاکنون برای رسیدن به n صرف شده = هزینه تخمینی از گره فعلی تا هدف با استفاده از تابع هیوریستیک محاسبه می شود. همین‌ طور با یک هیوریستیک غیر قابل قبول، الگوریتم A* می‌ تواند راه حل بهینه برای یک مسئله جستجو را به دلیل برآورد بیش از حد در ، با چالش روبرو کند. فرموله کردن را یک گره در نظر می‌ گیریم یک هیوریستیک (اکتشاف) است هزینه تخمینی برای رسیدن به هدف از هزینه بهینه برای رسیدن به هدف است قابل قبول است اگر یافتن مسأله هیوریستیک یک مسئله هیوریستیک قابل قبول می تواند از یک نسخه ساده از مسئله، یا با توجه به اطلاعاتی از پایگاه داده‌ الگو که راه حل‌ های دقیق برای مسائل فرعی را ذخیره می‌ کنند، یا با استفاده از روش های یادگیری استقرایی به دست آید. | ## بخش 2: اکتشاف قابل قبول | می‌ خواهیم یک هیوریستیک قابل قبول برای این مسئله پیدا کنیم فاصله هامینگ فاصله منهتن فاصله هامینگ تعداد کل کاشی هایی است که در جای خود قرار ندارند. از آنجا که هر کاشی نابجا در جای خود حداقل یکبار جابجا می شود بنابراین تعداد کل حرکات برای رسیدن به کاشی‌ های مرتب شده، به تعداد حداقل کاشی‌ های نابجا فعلی است. واضح است که این یک هیوریستیک قابل قبول است یعنی می‌ توان تابع هزینه (تعداد حرکت) را برای رسیدن به هدف (یک پازل مرتب شده)، مینیمم فاصله هامینگ پازل دانست. فاصله منهتن یک پازل نیز مجموع فاصله کاشی با موقعیت صحیح آن است و به صورت زیر تعریف می شود: پازل زیر را در نظر بگیرید که در آن بازیکن می خواهد هر کاشی را طوری جابجا کند که اعداد به ترتیب شمارش عناصر ستونی مرتب شوند. فاصله منهتن در این مسئله یک هیوریستیک قابل قبول است زیرا هر کاشی می‌ بایست حداقل به تعداد نقاط بین خود و موقعیت صحیح خود جابجا شود. 436130817212393144153132145424101111 در جدول فوق زیرنویس‌ ها، فاصله منهتن را برای هر کاشی نشان می دهند. | ## بخش 3: اکتشاف قابل قبول | مجموع مسافت منهتن برای پازل را می‌ توان به صورت زیر نوشت: مثال‌ اثبات بهینگی هر گاه برای رسیدن به گره هدف از اکتشاف قابل قبول استفاده شود، چون در هر تکرار، فقط مسیر کمترین تخمین (هزینه تا گره فعلی + هزینه اکتشاف تا گره هدف) از میان چندین مسیر نامزد را پی می‌ گیرد، در واقع وقتی کاوش به هدف می‌ رسد، ارزیابی مسیر‌ها نیز پایان می‌یابد و مهم‌تر اینکه، هرگز تمام مسیرهای بهینه را قبل از آن مرحله نمی‌ بندد (این چیزی است که با الگوریتم جستجوی A* امکان پذیر است اگر دقت خاصی صورت نگیرد )، پس این الگوریتم فقط می تواند در یک مسیر بهینه خاتمه یابد. این به این معناست که قبل از خاتمه، هزینه ارزیابی شده T کمتر (یا برابر) با هزینه ارزیابی شده S بوده است (در غیر این صورت می‌ بایست S انتخاب می‌شد). از آنجایی که T_eval و T_true نمی توانند با هم مساوی و هم نابرابر باشند، فرض ما باید نادرست بوده باشد و بنابراین پایان یافتن الگوریتم در مسیری پرهزینه تر از بهینه باید غیر ممکن باشد. به عنوان مثال فرضی تصور کنید هزینه‌ های زیر را داریم: (هزینه بالا/زیر گره، اکتشافی است، هزینه در لبه هزینه واقعی است) 0 10 0 100 0 START O GOAL | | 0| |100 | | O O O 100 1 100 1 100 ابتدا شروع به بازدید از گره میانی بالا می‌کنیم، هزینه کل مورد انتظار، یعنی f(n) برابر ۱۰ است. و هدف تنها یک کاندید است، با f(n) برابر با 110 سپس گره‌های دیگر را نیز بررسی می‌کنیم و به دنبال آن هدف‌های بروز شده را نیز در نظر می‌گیریم و f(n) همه آنها کمتر از f(n) هدف فعلی است ، یعنی f(n) آنها 100, 101, 102, 102 است. بنابراین اگرچه هدف در مرحله اول یک کاندید بود، اما نتوانستیم آن را انتخاب کنیم زیرا با بررسی دیگر مسیر‌ها فهمیدیم هنوز مسیرهای بهتری وجود دارد. | ## جمع‌بندی | با این حال، باید توجه داشت که هرچند یک اکتشاف قابل قبول می تواند بهینگی نهایی را تضمین کند، اما لزوما نمی‌ تواند کارآمد باشد.