سلام دوستان قبلا کسی در مانشت گرافی گذاشتن و فردی حلش کرده
میخاستم بپرسم چرا در محاسبه ی هزینه هر گره ،گره قبلیشم با هزینه یال و خود گره جمع زده؟
[
attachment=21124]
[
attachment=21125]
سلام
خوب عددی که رویه یال نوشته هزینه هر یال هست یا به نوعی هزینه از گره شروع تا اون گره هست و معروفه به g
و عددی که تویه دایره هر گره نوشته شده هزینه احتمالی از اون گره تا گره هدف هست که معروفه به h
و برای اینکه تصمیم بگیریم کدوم گره رو انتخاب کنیم در هر مرحله g+h میشه برای هر گره و کمترین رو انتخاب میکنیم و بسط میدیم!
اگه توجه کنید تویه عکس دوم قسمت 1 کنار A با خودکار نوشته 5 که همون 3+2 هست و کنار B نوشته 4 که همون 2+2 هست و چون 4 کوچیکتر بوده اونو انتخاب کرده و بسط داده و ...
منظورتون همی بود!؟
سلام خیلی ممنمنوم از پاسختون اره منظورم همینه اما تو عکس شماره یک را حل کنار A,B,D جوری حساب کرده که هم هزینه گره قبلی و هم عدد روی یال و هم خود همون گره ها که گفتم با هم جمع شدن. اخه همه جا فقط هزینه روی یال با گره ای که میخایم بهش بریم جمع میشه اینجا گرهپمبدا هم جمع شده
ببخشید از گره B به A.D.F
[
attachment=21126]
(17 دى 1395 12:43 ق.ظ)Never.forget نوشته شده توسط: [ -> ]سلام خیلی ممنمنوم از پاسختون اره منظورم همینه اما تو عکس شماره یک را حل کنار A,B,D جوری حساب کرده که هم هزینه گره قبلی و هم عدد روی یال و هم خود همون گره ها که گفتم با هم جمع شدن. اخه همه جا فقط هزینه روی یال با گره ای که میخایم بهش بریم جمع میشه اینجا گرهپمبدا هم جمع شده
ببخشید از گره B به A.D.F
سلام
اگه منظورت اون عدد 6 هست که قرمز نوشته شده کنار B اون مقدار مسیر نیست که جمع شده باشه ( اون مقدار 6، مقدار بهترین فرزند B هست که جایگزین مقدار B شده ) و به این دلیل هست چون مقدار گره A=5 هست و از همه فرزندان گره B مقدارش کمتره پس الگوریتم تصمیم میگیره بجای فرزندای B، گره A رو انتخاب کنه و چون داره تغیر مسیر میده میاد مقدار کمترین فرزند B رو جایگزین مقدار B میکنه تا اگه بعدا مقدار فرزندای A هم خوب نبود یادش بمونه که بهترین فرزند B چقده مقدارش و بتونه سریع برگرده
اوکی شد؟