سلام
من داشتم این سوالات رو میزدم که یهو به این تست بر خوردمو با اطمینان زدم بعد دیدم که آقای یوسفی نظرش با من متفاوته.
سوال پیوسته.
من نظرم روی گزینه ۴ بود به این دلیل که ما باید هر چه زودتر این تیر رو به تیکه های کوچیک تقسیم کنیم که هزینه کم بشه.
خوب من فکر کردم اگه بیام و هر بار I وسط رو در هر تیکه انتخاب کنیم هزینه به شکل زیر میشه:
اولین بار اگر فاصله ها مرتب نباشند با هزینه n میانه اونارو پیدا میکنیم (اگه مرتب هم باشند که بهتر)
بعد با تابع پارتیشن این فاصله ها رو مرتب میکنیم و بعد تیر رو دو نصف میکنم!!! این مرحله هم مرتبه اش n فرض میشه.
حالا واسه هر دو نصف همین کار رو میکنیم که مرتبه نهایی به صورت زیر در میاد که مرتبه چند جمله ایه:
[tex]n n 2(\frac{n}{2}) 4(\frac{n}{4}) ...[/tex]
که تعداد این n هاlgn +2 هست پس در کل میشه nlgn که چند جمله ای حساب میشه!
من نمیدونم مشکلم چیه ؟!
آخه آقای یوسفی گفتند که این مسئله تداعی کننده درخت دودویی بهینه است و با الگوریتم پویا از مرتبه [tex]n^3[/tex] میشه.
چرا شما همش نصف می کنید؟ در حالی که باید به اندازه های r1,r2,...rn برش بزنید.
من به راه حل حریصانه فکر کردم...
نه گفته که هزینه برش برابر طول تیر چوبی هست پس ما در هر مرحله باید طول تیر رو حداقل کنیم تا هزینه حداقل بشه!
اینطور نیست؟
اما یه جورایی هم درسته چون از راه حریصانه هم میشه حلش کرد.
نمی دونم ... کسی نظری نداره ؟؟
گویا کسی دوست نداره به من کمک کنه
نه دوست من شما همه رو به شک انداختید
شما استدلالتون رو بفرمایید من این تاپیک رو واسه همین درست کردم که هر کس استدلال خودش رو مطرح کنه. من نظرم اون بوده شما شاید نظرتون متفاوت باشه و البته درست تر از من!!
سلام .
اولا بهتون تبریک میگم چون تست ها رو با استدلال میزنید این خیلی نکته ی مثبتی است .
دوما جوابی که شما دادید در این مورد اشتباه است و هزینه بهینه رو نداره .
البته فک کنم یه مقدار صورت تست رو اشتباه درک کردید شما دارید فقط رو هزینه ی زمانی مسئله مانور میدید در حالی که اصل صورت تست رو فراموش کردید .
***ابتدا باید دنبال راه حل بهینه کمترین هزینه برش چوب ها باشیم بعد دنبال الگوریتمی با کمترین هزینه زمانی باشیم
با یه مثال پیش میریم .
فرض کنید تیر چوبی زیر رو با طول L=10 داریم که حاوی سه نقطه {x1,x2,x3} می باشد
[attachment=8778]
اگر با روش یافتن میانه و سپس پارتیشن این میانه جلو بریم (البته فک کنم پارتیشن هم نمیخوایم چون خود نقاط به ترتیب فاصله از سر چوب قرار دارن که مرتب هستن) هزینه برش به صورت زیر میباشد :
به ترتیب اول نقطه ی x2 بعد نقاط x1,x3 برش میخورن که با توجه به تیکه تیکه شدن هر قسمت در هر مرحله هزینه به صورت زیر میباشد
[tex]X2 = 10[/tex]
[tex]X1 = 3[/tex]
[tex]X3 = 7[/tex]
[tex]10 7 3 = 20[/tex]
[tex]X1 = 3[/tex]
[tex]X3 = 7[/tex]
[tex]10 7 3 = 20[/tex]
می بینیم که هزینه برش این تیر با روش یافتن میانه برابر ۲۰ شد .
حالا در ادامه به ترتیب زیر نقاط رو برش میزنیم
[tex]X3= 10[/tex]
[tex]X1= 5[/tex]
[tex]X2= 3[/tex]
[tex]10 5 3 =18[/tex]
[tex]X1= 5[/tex]
[tex]X2= 3[/tex]
[tex]10 5 3 =18[/tex]
میبینیم که این ترتیب برش زدن هزینه بهینه ۱۸ رو به دست آورد که اثبات رد روش شما است .
حالا باید ببینیم تفاوت چیست ؟ در واقع شما احتمال انتخاب یه نقطه رو با استفاده از یک درخت دودویی تقریبا متوازن انجام میدید ، به این ترتیب که میانه در ریشه درخت قرار میگیره و بقیه نقاط در دو طرف که هزینه رسیدن به این نقطه (ریشه) نسبت بقیه نقطه ها بیشتر است و یعنی شما شانسی به بقیه نقاط برای انتخاب در مرحله اول نمیدهید .
حال اگر از تابع احتمالی استفاده کنیم که مثلا برای این مثالی که زدیم شانس رو به نقطه x3 بدهد که در ریشه درخت قرار بگیرد اونوقت به هزینه بهینه میرسیم .
می بینیم روش حل این تست دقیقا تداعی کننده روش درخت جستجوی بهینه است (یافتن احتمال مناسب برای قرار دادن بهترین نقطه در ریشه)
حالا به هزینه روش درخت حستجوی بهینه دقت میکنیم که از مرتبه [tex]\Theta (n^{3})[/tex] است و چند جمله ای
اول از این تشکر کنم که شما بعد از ۲ هفته بلاخره اولین کسی هستید که جواب سوالم رو میدید(البته دوستانی بودن که بام همدردی کردند ولی جواب سوالم رو ندادند) .
و بعد هم از تعریفتون بیشتر تشکر میکنم.بله من چون حافظه ی ضعیفی دارم تا مسئله کاملا درک نشه تو ذهنم نمیمونه و باید حتما تجزیه تحلیل کنم.
خوب بریم سراغ جوابی که دادید :
بله استدالتون کاملا صحیح هست.و کاملا هم مشخص !
نه من دنبال مرتبه زمانی نبودم ، فقط دنبال جواب بهینه بودم و انقدر راه حلم بدیهی بود که تو نوشتنش عجله کردم و به اشتباه میانه رو وسط کشیدم(همون لحظه تایپ راه حل رو نوشتم) ، در صورتی که خیلی ساده تر میشه از طریق بازگشتی حلش کرد که بهینه هم باشه!
شما از این نکته به اشتباه افتادید که من گفتم میانه ها و بر اساس اونهم حساب کردم . اما منظورم کلا وسط بود.
خوب حالا راه حل بازگشتی که بر اساس وسط تیر چوبی کار کنه :
میشه جای میانه اینطور فرض کرد که در هر بار نزدیکترین نقطه به وسط تیر چوبی، برش داده میشه به این صورت که ابتدا طول تیر چوبی رو نصف میکنیم و اسمشو m میذاریم و از طریق جستجوی دودویی دنبال نزدیکترین نقطه برش به m میگردیم که با lg n قابل انجامه خوب حالا چوب رو نصف میکنیم و هر نصف رو به صورت بازگشتی دوباره به همین حالت تقسیم میکنیم. حالا مسئله با زمان تقریبا nlg n که بازم چند جمله ایه.
من مشکلم با اثبات روش پویا نبود بلکه من مشکلم با اینه که چرا توی گزینه ها گفته که با بقیه روشهای برنامه نویسی نمیشه پیاده سازیش کرد که شما اگه بخواید من با همه روشها واستون حل میکنم. من میخوام این ثابت بشه ، چرا فقط روش پویا ؟؟؟
(۱۷ دى ۱۳۹۱ ۰۱:۴۹ ب.ظ)mp1368 نوشته شده توسط: با یه مثال پیش میریم .
فرض کنید تیر چوبی زیر رو با طول L=10 داریم که حاوی سه نقطه {x1,x2,x3} می باشد
اگر با روش یافتن میانه و سپس پارتیشن این میانه جلو بریم (البته فک کنم پارتیشن هم نمیخوایم چون خود نقاط به ترتیب فاصله از سر چوب قرار دارن که مرتب هستن) هزینه برش به صورت زیر میباشد :
به ترتیب اول نقطه ی x2 بعد نقاط x1,x3 برش میخورن که با توجه به تیکه تیکه شدن هر قسمت در هر مرحله هزینه به صورت زیر میباشد
[tex]X2 = 10[/tex]
[tex]X1 = 3[/tex]
[tex]X3 = 7[/tex]
[tex]10 7 3 = 20[/tex]
می بینیم که هزینه برش این تیر با روش یافتن میانه برابر ۲۰ شد .
حالا در ادامه به ترتیب زیر نقاط رو برش میزنیم
[tex]X3= 10[/tex]
[tex]X1= 5[/tex]
[tex]X2= 3[/tex]
[tex]10 5 3 =18[/tex]
میبینیم که این ترتیب برش زدن هزینه بهینه ۱۸ رو به دست آورد که اثبات رد روش شما است .
سلام
میبخشید اگه سوالم واضحه از نظر شما ،ولی من متوجه نمیشم شما تو شکلی که کشیدین x2=3 هست پس چرا تو ۲ تا مثال x2=10 گذاشتین؟
همینطور بقیه ی xها
؟
ممنون
(۱۹ دى ۱۳۹۱ ۱۱:۲۱ ب.ظ)jafarir نوشته شده توسط:(17 دى ۱۳۹۱ ۰۱:۴۹ ب.ظ)mp1368 نوشته شده توسط: با یه مثال پیش میریم .
فرض کنید تیر چوبی زیر رو با طول L=10 داریم که حاوی سه نقطه {x1,x2,x3} می باشد
اگر با روش یافتن میانه و سپس پارتیشن این میانه جلو بریم (البته فک کنم پارتیشن هم نمیخوایم چون خود نقاط به ترتیب فاصله از سر چوب قرار دارن که مرتب هستن) هزینه برش به صورت زیر میباشد :
به ترتیب اول نقطه ی x2 بعد نقاط x1,x3 برش میخورن که با توجه به تیکه تیکه شدن هر قسمت در هر مرحله هزینه به صورت زیر میباشد
[tex]X2 = 10[/tex]
[tex]X1 = 3[/tex]
[tex]X3 = 7[/tex]
[tex]10 7 3 = 20[/tex]
می بینیم که هزینه برش این تیر با روش یافتن میانه برابر ۲۰ شد .
حالا در ادامه به ترتیب زیر نقاط رو برش میزنیم
[tex]X3= 10[/tex]
[tex]X1= 5[/tex]
[tex]X2= 3[/tex]
[tex]10 5 3 =18[/tex]
میبینیم که این ترتیب برش زدن هزینه بهینه ۱۸ رو به دست آورد که اثبات رد روش شما است .
سلام
میبخشید اگه سوالم واضحه از نظر شما ،ولی من متوجه نمیشم شما تو شکلی که کشیدین x2=3 هست پس چرا تو ۲ تا مثال x2=10 گذاشتین؟
همینطور بقیه ی xها
؟
ممنون
منظورشون هزینه برش از نقطه مثلا x2 است که میشه به اندازه طول تیر چوبی!
چون در مرحله اول طول تیر ۱۰ هست از هر نقطه ای که برش بخوره هزینه ۱۰ داره ، پس اولین برش هزینه ۱۰ داره و برش های بعدی هر یک به اندازه طول تیر خودشون.
موفق باشید
من سپاس رو زدم برای دوستمون.
اما خودم یه جا دیگه ثابت کردم میشه O)N
---
لطفا بفرمایید آیا نمونه ی این سوال توی کتابی حل شده است یا خیر؟