اکتشاف قابل قبول - ویکی‌پدیا، دانشنامهٔ آزاد

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

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

الگوریتم های جستجو[ویرایش]

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

${\displaystyle f(n)=g(n)+h(n)}$

به طوری که:

${\displaystyle f(n)}$ = تابع ارزیابی

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

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

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

فرموله کردن[ویرایش]

${\displaystyle n}$ را یک گره در نظر می‌ گیریم

${\displaystyle h}$ یک هیوریستیک (اکتشاف) است

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

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

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

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

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

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

مثال‌[ویرایش]

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

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

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

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

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

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

${\displaystyle h(n)=3+1+0+1+2+3+3+4+3+2+4+4+4+1+1=36}$

مثال‌

اثبات بهینگی[ویرایش]

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

فرض کنید چنین الگوریتمی در مسیر T با هزینه واقعی Ttrue بیشتر از مسیر بهینه S با هزینه واقعی Strue خاتمه یافته است. این به این معناست که قبل از خاتمه، هزینه ارزیابی شده T کمتر (یا برابر) با هزینه ارزیابی شده S بوده است (در غیر این صورت می‌ بایست S انتخاب می‌شد). این هزینه‌ های ارزیابی شده را به ترتیب Teval و Seval نشان می‌ دهیم. موارد فوق را می توان به صورت زیر خلاصه کرد.

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 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 است. بنابراین اگرچه هدف در مرحله اول یک کاندید بود، اما نتوانستیم آن را انتخاب کنیم زیرا با بررسی دیگر مسیر‌ها فهمیدیم هنوز مسیرهای بهتری وجود دارد. به این ترتیب، یک اکتشاف قابل قبول می‌تواند بهینه بودن مسیر را نیز تضمین کند.

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

منابع[ویرایش]

همچنین ببینید[ویرایش]

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