(۱۳ آبان ۱۳۹۲ ۰۹:۲۱ ب.ظ)zimenswall نوشته شده توسط:  سلام
یه تستی بود که دو تا کتاب دو تا جواب مختلف ازش دیدم که یکی گفته بود قابل قبوله و یکی گفته بود قابل قبول نیست

حالا واقعا کدومشونه؟

اینو میدونم که اگر هزینه مراحل یکسان باشه اول عمق تکراری بهینه است ، حالا منظورش از قابل قبول همون بهینه است یا نه؟

طبق فیلم آموزشی آقای رامین رهنمون :
قابل قبول یا admissible: بهینه و کامل بودن الگوریتم، الگوریتم اول عمق تکراری هم بهینه هست و هم کامل پس قابل قبول است.

(۱۳ آبان ۱۳۹۲ ۱۱:۳۹ ب.ظ)sepid نوشته شده توسط:  

(13 آبان ۱۳۹۲ ۰۹:۲۱ ب.ظ)zimenswall نوشته شده توسط:  سلام
یه تستی بود که دو تا کتاب دو تا جواب مختلف ازش دیدم که یکی گفته بود قابل قبوله و یکی گفته بود قابل قبول نیست

حالا واقعا کدومشونه؟

اینو میدونم که اگر هزینه مراحل یکسان باشه اول عمق تکراری بهینه است ، حالا منظورش از قابل قبول همون بهینه است یا نه؟

طبق فیلم آموزشی آقای رامین رهنمون :
قابل قبول یا admissible: بهینه و کامل بودن الگوریتم، الگوریتم اول عمق تکراری هم بهینه هست و هم کامل پس قابل قبول است.

پس یعنی الگوریتمی که هم کامل باشه و هم بهینه پس قابل قبوله. یعنی هر دو شرط را باهم دارا باشد

(۱۳ آبان ۱۳۹۲ ۰۹:۲۱ ب.ظ)zimenswall نوشته شده توسط:  سلام
یه تستی بود که دو تا کتاب دو تا جواب مختلف ازش دیدم که یکی گفته بود قابل قبوله و یکی گفته بود قابل قبول نیست

حالا واقعا کدومشونه؟

اینو میدونم که اگر هزینه مراحل یکسان باشه اول عمق تکراری بهینه است ، حالا منظورش از قابل قبول همون بهینه است یا نه؟

الگوریتم های جست و جو را میتوان به دو صورت Tree Search و یا Graph search پیاده سازی کرد که طبق اسلایدای راسل داریم:
جستجوی مدل گراف یه مجموعه میگیره که اونایی که ملاقات کرده رو دوباره نبینه، ولی درخت اینو نداره و ممکنه توی لوپ بیفته.

DFS:
نسخه graph توی گراف هایی که بینهایت حالت دارن کامل نیست ولی توی گراف های finite کامل هست.
نسخه درخت هم کامل نیست توی هیچ مدل! چون ممکنه توی لوپ بیافته.

واسه زمان:
[tex]O(b^m)[/tex]
m عمق عمیق ترین گره(ممکنه بینهایت باشه) و اگه m خیلی از d (عمق ، کم عمق ترین گره) بیشتر باشه، افتضاح هست.
واسه فضا:
[tex]O(bm)[/tex]

بهنیه؟
نه

(۱۳ آبان ۱۳۹۲ ۱۱:۵۴ ب.ظ)SnowBlind نوشته شده توسط:  

(13 آبان ۱۳۹۲ ۰۹:۲۱ ب.ظ)zimenswall نوشته شده توسط:  سلام
یه تستی بود که دو تا کتاب دو تا جواب مختلف ازش دیدم که یکی گفته بود قابل قبوله و یکی گفته بود قابل قبول نیست

حالا واقعا کدومشونه؟

اینو میدونم که اگر هزینه مراحل یکسان باشه اول عمق تکراری بهینه است ، حالا منظورش از قابل قبول همون بهینه است یا نه؟

الگوریتم های جست و جو را میتوان به دو صورت Tree Search و یا Graph search پیاده سازی کرد که طبق اسلایدای راسل داریم:
جستجوی مدل گراف یه مجموعه میگیره که اونایی که ملاقات کرده رو دوباره نبینه، ولی درخت اینو نداره و ممکنه توی لوپ بیفته.

DFS:
نسخه graph توی گراف هایی که بینهایت حالت دارن کامل نیست ولی توی گراف های finite کامل هست.
نسخه درخت هم کامل نیست توی هیچ مدل! چون ممکنه توی لوپ بیافته.

واسه زمان:
[tex]O(b^m)[/tex]
m عمق عمیق ترین گره(ممکنه بینهایت باشه) و اگه m خیلی از d (عمق ، کم عمق ترین گره) بیشتر باشه، افتضاح هست.
واسه فضا:
[tex]O(bm)[/tex]

بهنیه؟
نه

دوست گرامی
در این سوال گفته شده عمقی تکراری. عمقی تکراری میتونه بهینه باشه به همون شرطی که گفتم