شرط پذیرش بودن یک الگوریتم برای یافتن جواب مسئله کدام است ؟
۱/ [tex]\exists n; h(n)\leqslant h^{*} , g(n)\geqslant g^{*}[/tex]
۲/ [tex]\exists n; h(n)\geqslant h^{*} , g(n)\geqslant g^{*}[/tex]
۳/[tex]\forall n; h(n)\leqslant h^{*} , g(n)\geqslant g^{*}[/tex]
۴/ [tex]\forall n; h(n)\leqslant h^{*} , g(n)\leqslant g^{*}[/tex]
پوران پژوهش گفته گزینه ۴
پارسه گفته گزینه ۳
حالا کدوم درسته؟
البته تا این قسمتشو میدونم که [tex]\forall n; h(n)\leqslant h^{*}[/tex] ولی نمیدونم در مورد g چی میشه ؟
ولی احتمال میدم که g بهینه یا همون [tex]g^{*}[/tex] باید از g و هر مسیر دیگری تا نود n کوچکتر باشه [tex]g(n)\geqslant g^{*}(n)[/tex]
که یعنی گزینه ۳ ولی دلم میخواد اطمینان قلبی به جواب پیدا کنم
(۲۴ شهریور ۱۳۹۲ ۰۸:۲۷ ب.ظ)zimenswall نوشته شده توسط: شرط پذیرش بودن یک الگوریتم برای یافتن جواب مسئله کدام است ؟فکر میکنم گزینه ۴ درست باشه؛
۱/ [tex]\exists n; h(n)\leqslant h^{*} , g(n)\geqslant g^{*}[/tex]
۲/ [tex]\exists n; h(n)\geqslant h^{*} , g(n)\geqslant g^{*}[/tex]
۳/[tex]\forall n; h(n)\leqslant h^{*} , g(n)\geqslant g^{*}[/tex]
۴/ [tex]\forall n; h(n)\leqslant h^{*} , g(n)\leqslant g^{*}[/tex]
پوران پژوهش گفته گزینه ۴
پارسه گفته گزینه ۳
حالا کدوم درسته؟
البته تا این قسمتشو میدونم که [tex]\forall n; h(n)\leqslant h^{*}[/tex] ولی نمیدونم در مورد g چی میشه ؟
ولی احتمال میدم که g بهینه یا همون [tex]g^{*}[/tex] باید از g و هر مسیر دیگری تا نود n کوچکتر باشه [tex]g(n)\geqslant g^{*}(n)[/tex]
که یعنی گزینه ۳ ولی دلم میخواد اطمینان قلبی به جواب پیدا کنم
برداشت من از g* هزینه مسیر جواب بهینه است؛ حالا الگوریتمی که میاد و نودی رو بسط میده که هزینه رسیدن از گره شروع تا اون گره بیشتر از هزینه جواب بهینه است نمیتونه الگوریتم قابل قبولی باشه؛ بعبارت دیگه الگوریتمی قابل قبوله که نودی رو با هزینه مسیر بیشتر از هزینه بهینه بسط نده (این یکی از دلایل بهینه بودن A* هم هست)؛
(مثلا فرض کنید الگوریتمی تا گره x پیش رفته و هزینه رسیدن به x هم باشه ۱۰؛ هزینه مسیر بهینه هم باشه ۱۵؛ حالا اگه در گام بعدی الگوریتم گره y رو بسط بده که هزینه رسیدن به اون بشه ۱۸ یعنی الگوریتم نتونسته گره هدف (با هزینه ۱۵) رو در اون گام پیدا کنه)
(۲۴ شهریور ۱۳۹۲ ۰۹:۱۵ ب.ظ)Ghiasoddin نوشته شده توسط:(24 شهریور ۱۳۹۲ ۰۸:۲۷ ب.ظ)zimenswall نوشته شده توسط: شرط پذیرش بودن یک الگوریتم برای یافتن جواب مسئله کدام است ؟فکر میکنم گزینه ۴ درست باشه؛
۱/ [tex]\exists n; h(n)\leqslant h^{*} , g(n)\geqslant g^{*}[/tex]
۲/ [tex]\exists n; h(n)\geqslant h^{*} , g(n)\geqslant g^{*}[/tex]
۳/[tex]\forall n; h(n)\leqslant h^{*} , g(n)\geqslant g^{*}[/tex]
۴/ [tex]\forall n; h(n)\leqslant h^{*} , g(n)\leqslant g^{*}[/tex]
پوران پژوهش گفته گزینه ۴
پارسه گفته گزینه ۳
حالا کدوم درسته؟
البته تا این قسمتشو میدونم که [tex]\forall n; h(n)\leqslant h^{*}[/tex] ولی نمیدونم در مورد g چی میشه ؟
ولی احتمال میدم که g بهینه یا همون [tex]g^{*}[/tex] باید از g و هر مسیر دیگری تا نود n کوچکتر باشه [tex]g(n)\geqslant g^{*}(n)[/tex]
که یعنی گزینه ۳ ولی دلم میخواد اطمینان قلبی به جواب پیدا کنم
برداشت من از g* هزینه مسیر جواب بهینه است؛ حالا الگوریتمی که میاد و نودی رو بسط میده که هزینه رسیدن از گره شروع تا اون گره بیشتر از هزینه جواب بهینه است نمیتونه الگوریتم قابل قبولی باشه؛ بعبارت دیگه الگوریتمی قابل قبوله که نودی رو با هزینه مسیر بیشتر از هزینه بهینه بسط نده (این یکی از دلایل بهینه بودن A* هم هست)؛
(مثلا فرض کنید الگوریتمی تا گره x پیش رفته و هزینه رسیدن به x هم باشه ۱۰؛ هزینه مسیر بهینه هم باشه ۱۵؛ حالا اگه در گام بعدی الگوریتم گره y رو بسط بده که هزینه رسیدن به اون بشه ۱۸ یعنی الگوریتم نتونسته گره هدف (با هزینه ۱۵) رو در اون گام پیدا کنه)
تشکر
خب این مثالی که شما زدید دلیلی نقضی نبود چون حتما مسیری که *A رفته اشتباه بوده و باید از مسیر دیگه بره.
توی تست ها هم دیدم که از یه مسیری که میریم ممکنه مقدار تابع f+g از هزینه مسیر بهینه بیشتر میشه و *A میاد و از یه مسیر دیگه میره و به جواب میرسه
یعنی مثال شما وقتی درسته که تنها راه رسیدن به y فقط و فقط x باشه.
بازم مشکوکم به این جریان
(۲۴ شهریور ۱۳۹۲ ۰۸:۲۷ ب.ظ)zimenswall نوشته شده توسط: شرط پذیرش بودن یک الگوریتم برای یافتن جواب مسئله کدام است ؟
۱/ [tex]\exists n; h(n)\leqslant h^{*} , g(n)\geqslant g^{*}[/tex]
۲/ [tex]\exists n; h(n)\geqslant h^{*} , g(n)\geqslant g^{*}[/tex]
۳/[tex]\forall n; h(n)\leqslant h^{*} , g(n)\geqslant g^{*}[/tex]
۴/ [tex]\forall n; h(n)\leqslant h^{*} , g(n)\leqslant g^{*}[/tex]
پوران پژوهش گفته گزینه ۴
پارسه گفته گزینه ۳
حالا کدوم درسته؟
البته تا این قسمتشو میدونم که [tex]\forall n; h(n)\leqslant h^{*}[/tex] ولی نمیدونم در مورد g چی میشه ؟
ولی احتمال میدم که g بهینه یا همون [tex]g^{*}[/tex] باید از g و هر مسیر دیگری تا نود n کوچکتر باشه [tex]g(n)\geqslant g^{*}(n)[/tex]
که یعنی گزینه ۳ ولی دلم میخواد اطمینان قلبی به جواب پیدا کنم
خودم هر چی فکر کردم دیدم ظاهرا گزینه ۳ درست باشه
*g یعنی هزینه مسیر بهینه تا نود n. حالا اگه نود n را هدف در نظر بگیریم *g در نود هدف یعنی بهینه ترین مسیر تا اون نود. و هر g دیگری مساوی یا بزرگتر *g میباشد.
توی گراف هایی که توی تست ها هم هست اگر از نود شروع تا نود هدف یا هر نودی، چند مسیر باشه مطمئنا یک مسیر بهینه داریم (*g) و چندتا مسیر غیربهینه که هزینه هاشون بیشتر از *g هست.
(۲۶ شهریور ۱۳۹۲ ۱۰:۳۶ ق.ظ)zimenswall نوشته شده توسط: خودم هر چی فکر کردم دیدم ظاهرا گزینه ۳ درست باشه
*g یعنی هزینه مسیر بهینه تا نود n. حالا اگه نود n را هدف در نظر بگیریم *g در نود هدف یعنی بهینه ترین مسیر تا اون نود. و هر g دیگری مساوی یا بزرگتر *g میباشد.
توی گراف هایی که توی تست ها هم هست اگر از نود شروع تا نود هدف یا هر نودی، چند مسیر باشه مطمئنا یک مسیر بهینه داریم (*g) و چندتا مسیر غیربهینه که هزینه هاشون بیشتر از *g هست.
هزینه مسیر بهینه تا نود n میشه [tex]g^{*}(n)[/tex]؛ بنظرم منظور از g* باید هزینه مسیر بهینه باشه تا گره هدف (که در واقع با h* یکی هست)؛
همین نکته ای که در خط آخر نوشتید جواب سوالتون رو میده؛ اگه الگوریتمی یک یا چندتا از اون مسیرهای غیر بهینه رو قبل از گره هدف انتخاب کنه (یعنی به ازای بعضی از n ها هزینه g(n) از g* بیشتر بشه) معنیش اینه که تضمینی برای بهینه یا کارامدبودن اون الگوریتم نیست؛
(جهت یادآوری: A* هیچ گره ای رو با هزینه ای بیشتر از هزینه گره هدف بسط نمیده؛ یعنی در اون مثال قبلی امکان نداره A* به اشتباه گره y رو قبل از گره هدف بسط بده)
برای رد درستی مورد سه، میتونید گره n رو بگیرید گره شروع؛ واضحه که g به ازای این گره برابر صفره که رابطه
[tex]\forall n :g(n)\geqslant g^*[/tex] رو برای هر الگوریتمی نقض میکنه؛
(برداشت من اینه که این سوال بر اساس تعریف بهینگی الگوریتم A* طرح شده)
(۲۸ شهریور ۱۳۹۲ ۱۰:۵۶ ب.ظ)Ghiasoddin نوشته شده توسط:(26 شهریور ۱۳۹۲ ۱۰:۳۶ ق.ظ)zimenswall نوشته شده توسط: خودم هر چی فکر کردم دیدم ظاهرا گزینه ۳ درست باشه
*g یعنی هزینه مسیر بهینه تا نود n. حالا اگه نود n را هدف در نظر بگیریم *g در نود هدف یعنی بهینه ترین مسیر تا اون نود. و هر g دیگری مساوی یا بزرگتر *g میباشد.
توی گراف هایی که توی تست ها هم هست اگر از نود شروع تا نود هدف یا هر نودی، چند مسیر باشه مطمئنا یک مسیر بهینه داریم (*g) و چندتا مسیر غیربهینه که هزینه هاشون بیشتر از *g هست.
هزینه مسیر بهینه تا نود n میشه [tex]g^{*}(n)[/tex]؛ بنظرم منظور از g* باید هزینه مسیر بهینه باشه تا گره هدف (که در واقع با h* یکی هست)؛
همین نکته ای که در خط آخر نوشتید جواب سوالتون رو میده؛ اگه الگوریتمی یک یا چندتا از اون مسیرهای غیر بهینه رو قبل از گره هدف انتخاب کنه (یعنی به ازای بعضی از n ها هزینه g(n) از g* بیشتر بشه) معنیش اینه که تضمینی برای بهینه یا کارامدبودن اون الگوریتم نیست؛
(جهت یادآوری: A* هیچ گره ای رو با هزینه ای بیشتر از هزینه گره هدف بسط نمیده؛ یعنی در اون مثال قبلی امکان نداره A* به اشتباه گره y رو قبل از گره هدف بسط بده)
برای رد درستی مورد سه، میتونید گره n رو بگیرید گره شروع؛ واضحه که g به ازای این گره برابر صفره که رابطه
[tex]\forall n :g(n)\geqslant g^*[/tex] رو برای هر الگوریتمی نقض میکنه؛
(برداشت من اینه که این سوال بر اساس تعریف بهینگی الگوریتم A* طرح شده)
ممنون که جواب دادی. درسته. *h و *g یکی هستند و یعنی هزینه واقعی مسیر تا نود هدف. اما
طبق تعاریف
g هزینه مسیر از نود شروع تا نود n
و *g هم به احتمال زیاد میشه هزینه مسیر بهینه از نود شروع تا نود n
شما یه نگاه به این شکل بنداز
![[تصویر: 213702_01.JPG]](https://img.manesht.ir/213702_01.JPG)
اگه شکل را در نظر بگیریم دو تا مسیر برای رسیدن به هدف داریم
یکیش با هزینه۹ و یکی هم با هزینه ۶ . پس *g میشه ۶ ، یعنی بهینه ترین مسیر تا هدف. و تمام مسیرهای دیگه باید از *g بزرگتر باشن وگرنه مسیری که از *g کوچکتر باشه ، اون میشه مسیر بهینه. و باید جایگزین *g بشه.
استدلال من نسبت به این سوال اینجوریه.
(۲۸ شهریور ۱۳۹۲ ۱۱:۴۸ ب.ظ)zimenswall نوشته شده توسط: اگه شکل را در نظر بگیریم دو تا مسیر برای رسیدن به هدف داریم
یکیش با هزینه۹ و یکی هم با هزینه ۶ . پس *g میشه ۶ ، یعنی بهینه ترین مسیر تا هدف. و تمام مسیرهای دیگه باید از *g بزرگتر باشن وگرنه مسیری که از *g کوچکتر باشه ، اون میشه مسیر بهینه. و باید جایگزین *g بشه.
استدلال من نسبت به این سوال اینجوریه.
استدلال شما غلط نیست اما کمکی به حل مسئله نمیکنه (:
در واقع استدلال شما تعریف g* هست؛ شما باید از زاویه الگوریتم نگاه کنید؛ مهم نیست چندتا مسیر با هزینه بیشتر از g* داریم مهم اینه که الگوریتم با این مسیرهای غیر بهینه چه کار میکنه؟ در واقع اون تعریف به ازای هر n، منظور به ازای هر n ای هست که الگوریتم اونو بسط داده (یا ویزیت کرده)
گزینه ۳ میگه هر گره ای که الگوریتم اونو ویزیت میکنه (قبل از رسیدن به هدف) باید هزینه رسیدن تا اون گره از g* بیشتر باشه (فرض کنید الگوریتم A اینطور عمل کنه)؛
گزینه ۴ میگه هر گره ای که الگوریتم اونو ویزیت (قبل از رسیدن به هدف) میکنه باید هزینش کمتر از هزینه مسیر بهینه باشه (فرض کنید الگوریتم B اینطوری باشه)؛
حالا کدوم الگوریتم در رسیدن به هدف کارامدتره و قابل قبول؟ الگوریتم A لازمه همه گره های غیر بهینه (که هزینه ای بیشتر از g* دارن) رو ویزیت کنه تا به هدف برسه، اما الگوریتم B تضمین میکنه که اضافه کاری نکنه و فقط گره هایی رو ویزیت میکنه که در مسیر رسیدن به هدف قرار دارن (و هزینه ای کمتر از g* دارن)
شایدم استدلال من غلطه (:
(۲۹ شهریور ۱۳۹۲ ۰۲:۲۳ ق.ظ)Ghiasoddin نوشته شده توسط:(28 شهریور ۱۳۹۲ ۱۱:۴۸ ب.ظ)zimenswall نوشته شده توسط: اگه شکل را در نظر بگیریم دو تا مسیر برای رسیدن به هدف داریم
یکیش با هزینه۹ و یکی هم با هزینه ۶ . پس *g میشه ۶ ، یعنی بهینه ترین مسیر تا هدف. و تمام مسیرهای دیگه باید از *g بزرگتر باشن وگرنه مسیری که از *g کوچکتر باشه ، اون میشه مسیر بهینه. و باید جایگزین *g بشه.
استدلال من نسبت به این سوال اینجوریه.
استدلال شما غلط نیست اما کمکی به حل مسئله نمیکنه (:
در واقع استدلال شما تعریف g* هست؛ شما باید از زاویه الگوریتم نگاه کنید؛ مهم نیست چندتا مسیر با هزینه بیشتر از g* داریم مهم اینه که الگوریتم با این مسیرهای غیر بهینه چه کار میکنه؟ در واقع اون تعریف به ازای هر n، منظور به ازای هر n ای هست که الگوریتم اونو بسط داده (یا ویزیت کرده)
گزینه ۳ میگه هر گره ای که الگوریتم اونو ویزیت میکنه (قبل از رسیدن به هدف) باید هزینه رسیدن تا اون گره از g* بیشتر باشه (فرض کنید الگوریتم A اینطور عمل کنه)؛
گزینه ۴ میگه هر گره ای که الگوریتم اونو ویزیت (قبل از رسیدن به هدف) میکنه باید هزینش کمتر از هزینه مسیر بهینه باشه (فرض کنید الگوریتم B اینطوری باشه)؛
حالا کدوم الگوریتم در رسیدن به هدف کارامدتره و قابل قبول؟ الگوریتم A لازمه همه گره های غیر بهینه (که هزینه ای بیشتر از g* دارن) رو ویزیت کنه تا به هدف برسه، اما الگوریتم B تضمین میکنه که اضافه کاری نکنه و فقط گره هایی رو ویزیت میکنه که در مسیر رسیدن به هدف قرار دارن (و هزینه ای کمتر از g* دارن)
شایدم استدلال من غلطه (:
احسنت ، دو ریالیم افتاد
پس جواب سوال به این بستگی داره که g هایی که در نظر میگیریم، همون g هایی باشه که *A تولید کرده یا g هایی که در کل مسئله وجود داره.
من استدلالم روی تمام gهای مسئله بود، یعنی حتی اونهایی که الگوریتم ویزیت نمیکنه که با این استدلال گزینه ۳ میشه
ولی استدلال شما روی gهایی بود که الگوریتم اونها را تولید میکنه. پس با استدلال شما گزینه ۴ میشه
و سوال بستگی داره از کدوم دید ببینیم. و به نظرم صحبت شما درست تر باشه. چون اگر طبق تعریف *A که میگه نودهایی با هزینه بیشتر از مسیر بهینه را گسترش نمیده به احتمال قوی میشه گفت گزینه ۴ درسته
ممنون از کمک شما