هرقدر تابع هیوریستیک h تخمین بهتروقابل قبول تری بزنه ، هزینه رسیدن به جواب کمتره . و تخمین بهتر و دقیق تر هم تخمینی است که به هزینه واقعی مسیر نزدیک تر باشه .مفهوم قابل قبول بودن (admisible) همینه
درواقع بهترین تخمین همون هزینه واقعی مسیر هست ولی در بعضی مسائل ممکنه ما از قبل نسبت به هزینه واقعی اطلاعی نداشته باشیم. درنتیجه مجبوریم تخمین بزنیم

---

اضافه میکنم که هرچقدر تخمین به هزینه مسیر نزدیک تر باشه و قابل قبول تر باشه گرههای کمتری بسط داده میشن و جلوی بسط گرههای غیر ضروری گرفته میشه

مزسی از پاسختون .
توی پوران قابل قبول بودن h رو شرط لازم برای بهینگی جواب در جستجو A* گفته و چون اثباتش رو ارائه داده قابل فهم . همینطور در بحث کارایی چند تابع قابل قبول گفته اگر h2 بزرگتر از h1 باشد و هر دو قابل قبول باشند h2 تعداد نود کمتری گسترش می دهد . و این مورد رو هم براش دلیل اورده. پس دقیقا حرف شما رو برای مواردی که مقایسه بین ۲ تابع قابل قبول هست رو می فهمم ، اما من جایی دلیل برای اینکه اگر h قابل قبول باشد نسبت به وقتی که قابل قبول نباشه تعداد نود کمتری رو گسترش می ده ندیدم برا همین نمی فهممم چرا گزینه ۲ درست . می دونید توی تست کلا گفته اگر h قابل قبول باشد نسبت به وقتی که نباشد تعداد نود کمتری را برای پیدا کردن جواب بررسی می کنه. حالا دلیل این برای چی ؟ نمی دونم منظورم رو رسوندم ؟ یعنی من می فهمم که
"هرچقدر تخمین به هزینه مسیر نزدیک تر باشه و قابل قبول تر باشه گرههای کمتری بسط داده میشن و جلوی بسط گرههای غیر ضروری گرفته میشه "
اما نمی فهمم چرا بین یک قابل قبول و یک غیر قابل قبول بازم قابل قبول کمتر گسترش می ده ؟
من این تست رو که دیدم چون فقط دیده بودم قابل قبول بودن شرطی برای بهینگی جواب هست حواب ۳ رو زدم .

خب خودتون الان همین مطلب رو اشاره کردید : "جلوی بسط گرههای غیر ضروری گرفته میشه "

(۱۱ آذر ۱۳۹۱ ۰۵:۲۹ ب.ظ)ana_12345 نوشته شده توسط:  "هرچقدر تخمین به هزینه مسیر نزدیک تر باشه و قابل قبول تر باشه گرههای کمتری بسط داده میشن و جلوی بسط گرههای غیر ضروری گرفته میشه "

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

من گفتم برای مقایسه ۲ تابع قابل قبول من این مورد رو می فهمم وقبول دارم که هر چه قابل قبول به تخمین واقعی نردیک تر باشه تعدادد نود کمتری رو حستحو می کنه اما مسئله اینجا که تست داره غیر قابل قبول رو با قابل قبول مقایسه می کنه . الان توی راسل ، برای جستجو اول بهترین هم نگاه کردم تازه گیج تر شدم ، یه مثال بخارست هستا اونجا تازه تابع قابل قبول باعث گسترش نودهای اضافه می شه . اخرسرم گفته با انتخاب هیوریستسک مناسب، می توان پیجیدگی زمانی رو کم کرد اما نگفته با انتخاب هیوریستیک قابل قبول می توان تعداد پیچیدگی زمانی رو کم کرد. شما این که هیوریستیک قابل قبول منجر به کاهش پیچیدگی زمانی می شه رو تو کتاب یا مرجعی دیدن ؟ اقا شرمنده ها ولی خوب چی کار کنم فکرم به جایی نمی رسه .(((

بچه ها چرا توی *A وقتی h=*h میشه پیچیدگی زمانی میشه حاصل ضرب عمق جواب در تعداد متوسط شاخه ها؟ این توی کتاب گفته شده؟(کنکور ۸۹ IT )من فکر می کردم پیچیدگیش نمایی هستش..ممنون میشم توضیح بدین