هیوریستیک (اکتشاف) قابل قبول

این مقاله در حال بهبود است لطفا حذف نشود...

در علم کامپیوتر، به‌ طور خاص در الگوریتم‌های مربوط به مسیریابی ، زمانی به تابع هیوریستیک یک تابع قابل قبول گفته می‌شود که هزینه دست‌یابی به هدف را بیش از مقدار واقعی تخمین نزند، یعنی هزینه‌ای که از گره فعلی برای رسیدن به گره هدف تخمین می‌زند از کمترین هزینه ممکن بیشتر نباشد.

این مفهوم مرتبط با اکتشاف سازگار (یکنوا) است. همه اکتشافی های سازگار قابل پذیرش هستند، در حالی که همه اکتشافی های قابل قبول سازگار نیستند.

الگوریتم های جستجو

در الگوریتم جستجوی آگاهانه از هیوریستیک قابل قبول برای تخمین هزینه‌ی رسیدن به گره هدف استفاده می‌شود . این الگوریتم‌ از این مفهوم برای یافتن یک مسیر بهینه تخمینی به گره هدف از گره فعلی استفاده می‌کند. مثلا در الگوریتم جستجوی A* که مبنای آن بر اجتناب از گسترش مسیر‌هایی است که هم‌اکنون گران هستند، تابع ارزیابی (از گره‌ nام تا گره هدف) برابر است:

$f(n)=g(n)+h(n)$

به طوری که:

$f(n)$ = تابع ارزیابی

$g(n)$ = هزینه‌ای که تاکنون برای رسیدن به n صرف شده

$h(n)$ = هزینه تخمینی از گره فعلی تا هدف.

$h(n)$ با استفاده از تابع هیوریستیک محاسبه می شود. با یک تخمین خوب می‌توان به طرز چشمگیری هزینه جستجو را کاهش داد. همین‌طور با یک هیوریستیک غیر قابل قبول، الگوریتم A* می تواند راه حل بهینه برای یک مسأله جستجو را به دلیل برآورد بیش از حد در $f(n)$، با چالش روبرو کند.

فرموله کردن

$n$ را یک گره در نظر می‌گیریم

$h$ یک هیوریستیک (اکتشاف) است

$h(n)$ هزینه تخمینی برای رسیدن به هدف از $n$

$h^{*}(n)$ هزینه بهینه برای رسیدن به هدف است $n$

$h(n)$ قابل قبول است اگر $\forall n$

$h(n)\leq h^{*}(n)$

یافتن مسأله هیوریستیک

یک مسأله هیوریستیک قابل قبول می‌تواند از یک نسخه ساده از مسئله، یا با توجه به اطلاعاتی از پایگاه داده‌ الگو که راه حل‌های دقیق برای مسائل فرعی مسئله را ذخیره می‌کنند، یا با استفاده از روش های یادگیری استقرایی به دست آید.

مثال‌

مسأله پازل پانزده‌تایی را در نظر بیاورید. می‌خواهیم یک هیوریستیک قابل قبول برای این مسأله پیدا کنیم:

• فاصله هامینگ
• فاصله منهتن

فاصله هامینگ تعداد کل کاشی‌هایی است که در جای خود قرار ندارند. از آنجا که هر کاشی نابجا در جای خود حداقل یکبار جابجا می‌شود بنابراین تعداد کل حرکات برای رسیدن به کاشی‌‌های مرتب شده، به تعداد حداقل کاشی‌های نابجا فعلی است. واضح است که این یک هیوریستیک قابل قبول است یعنی می‌ توان تابع هزینه (تعداد حرکت) را برای رسیدن به هدف (یک پازل مرتب شده)، مینیمم فاصله هامینگ پازل دانست.

همچنین فاصله منهتن یک پازل نیز مجموع فاصله کاشی با موقعیت صحیح آن است و به صورت زیر تعریف می شود:

$h(n)=\sum _{\text{all tiles}}{\mathit {distance}}({\text{tile, correct position}})$

پازل زیر را در نظر بگیرید که در آن بازیکن می خواهد هر کاشی را طوری جابجا کند که اعداد به ترتیب شمارش عناصر ستونی مرتب شوند. فاصله منهتن در این مسأله یک هیوریستیک قابل قبول است زیرا هر کاشی می‌بایست حداقل به تعداد نقاط بین خود و موقعیت صحیح خود جابجا شود.

43	61	30	81
72	123	93	144
153	132	14	54
24	101	111

در جدول فوق زیرنویس‌ها، فاصله منهتن را برای هر کاشی نشان می دهند. مجموع مسافت منهتن برای پازل را می‌توان به صورت زیر نوشت:

$h(n)=3+1+0+1+2+3+3+4+3+2+4+4+4+1+1=36$

هر گاه برای رسیدن به گره هدف از اکتشاف قابل قبول استفاده شود، چون در هر تکرار، فقط مسیر کمترین تخمین (هزینه تا گره فعلی + هزینه اکتشاف تا گره هدف) از میان چندین مسیر نامزد را پی می‌گیرد، در واقع وقتی کاوش به هدف می‌رسد، ارزیابی مسیر‌ها نیز پایان می‌یابد و مهم‌تر اینکه، هرگز تمام مسیرهای بهینه را قبل از آن مرحله نمی‌بندد (این چیزی است که با الگوریتم جستجوی A* امکان‌پذیر است اگر دقت خاصی صورت نگیرد  )، پس این الگوریتم فقط می‌تواند در یک مسیر بهینه خاتمه یابد. برای اینکه بفهمید چرا؟ برهان خلف زیر را در نظر بگیرید:

فرض کنید چنین الگوریتمی در مسیر T با هزینه واقعی T_true بیشتر از مسیر بهینه S با هزینه واقعی S_true خاتمه یافته است. این به این معناست که قبل از خاتمه، هزینه ارزیابی شده T کمتر (یا برابر) با هزینه ارزیابی شده S بوده است (در غیر این صورت می‌ بایست S انتخاب می‌شد). این هزینه‌‌های ارزیابی شده را به ترتیب T_eval و S_eval نشان می‌ دهیم. موارد فوق را می‌توان به صورت زیر خلاصه کرد.

S _true < T _true

T _eval ≤ S _eval

اکتشاف قابل قبول، بدین معناست که در مرحله ما قبل آخر   T_eval = T_true درست باشد زیرا هر گونه افزایش هزینه واقعی توسط اکتشاف در T غیر قابل قبول است و اکتشاف نمی‌تواند منفی باشد. از سوی دیگر، یک اکتشاف قابل قبول مستلزم آن است که S_eval  ≤  S_true باشد که ترکیب با نابرابری های فوق به ما T_eval < T_true و به طور خاص‌تر  T_eval ≠ T_true می‌‌دهد. از آنجایی که T_eval و T_true نمی‌توانند با هم مساوی و هم نابرابر باشند، فرض ما باید نادرست بوده باشد و بنابراین پایان یافتن الگوریتم در مسیری پرهزینه تر از بهینه باید غیر ممکن باشد.

به عنوان مثال، تصور کنید هزینه‌‌های زیر را داریم: (هزینه بالا/زیر گره، اکتشافی است، هزینه در لبه هزینه واقعی است.

0    10   0    100     0
شروع ---- O ----- هدف
 |                  |
0|                  | 100
 |                  | 
 O ------- O ------ O
100   1  100   1      100

ما شروع به بازدید از گره میانی بالا می‌کنیم، هزینه کل مورد انتظار، یعنی f(n) برابر ۱۰ است. و هدف تنها یک کاندید است، با f(n) برابر با 10+100+0=110

سپس گره‌های دیگر را نیز بررسی می‌کنیم و به دنبال آن هدف‌های بروز شده را نیز در نظر می‌گیریم و f(n) همه آنها کمتر از f(n) هدف فعلی است ، یعنی f(n) آنها

100,101,102,102 است. بنابراین اگرچه هدف در مرحله اول یک کاندید بود، اما نتوانستیم آن را انتخاب کنیم زیرا با بررسی دیگر مسیر‌ها فهمیدیم هنوز مسیرهای بهتری وجود دارد. به این ترتیب، یک اکتشاف قابل قبول می‌تواند بهینه بودن مسیر را نیز تضمین کند.

با این حال، توجه داشته باشید که اگرچه یک اکتشافی قابل قبول می تواند بهینگی نهایی را تضمین کند، لزوما کارآمد نیست.

همچنین ببینید

• اکتشاف سازگار
• تابع اکتشاف
• الگوریتم جستجو

This article "هیوریستیک (اکتشاف) قابل قبول" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:هیوریستیک (اکتشاف) قابل قبول. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---

 Facebook Page

 Follow us on Twitter !

Read or create/edit this page in another language

• هیوریستیک (اکتشاف) قابل قبول in English