سلام
من تونستم این الگوریتم رو با الگوریتم کوله پشتی معادل کنم.
ببین فرض میکنیم شما یک شاخه مثلا به طول 16 متر داری و سه تا قطعه به طولهای 9 و 4 و 6. بهترین برش برای این قطعه برش میله های 6 و 9 که کمترین هدر رفتگی رو به ما میده.
فرض کن L طول شاخه ، L1 و L2 و L3 و ... هم طولهای قطعه ها باشند. یعنی در این مثال :
L = 16
L1 = 9 , L2 = 4 , L3 = 6
یک تابع بازگشتی تعریف میکنیم که هدفش مینیمم کردن مقدار پرتی میباشه که الهام گرفته از برنامه سازی پویا و خصوصا مساله کوله پشتی 0 و 1 :
F(n,L) = min {F(n-1,L) , F(n-1 ,L-Ln)}
و نقاط مرزیه:
F(0,K) = K
F(0,-K) = infinite
یعنی هنگامی که میخوایم میله n ام رو تست کنیم دو حالت داریم. یا میله n ام رو انتخاب نمیکنیم و ادامه مساله رو با (F(n-1,L حل میکنیم یا اینکه میله n ام رو انتخاب میکنیم و ادامه مساله رو با (F(n-1,L-Ln حل میکنیم و در آخر بین این دو تا کوچیکتر رو انتخاب میکنیم.
حالا مثالمون رو با این فرمول به صورت بازگشتی حل میکنیم
F(3,16) = min {F(2,16) , F(2,10) [L3]}
F(2,16) = min {F(1,16) , F(1,12) [L2]}
F(2,10) = min {F(1,10) , F(1,6) [L2]}
F(1,16) = min {F(0,16) , F(0,7) [L1]}
F(1,12) = min {F(0,12) , F(0,3) [L1]}
F(1,10) = min {F(0,10) , F(0,1) [L1]}
F(1,6) = min {F(0,6) , F(0,-3) [L1]}
F(0,16) = 16
F(0,7) = 7
F(0,12) = 12
F(0,3) = 3
F(0,10) = 10
F(0,1) = 1
F(0, 6) = 6
F(0,-3) = infinite // hamoon binahayate khodemoon ya masalan 1000
حالا که به نقاط پایانی رسیدیم یعنی دیگه قطعه ای برای تست نبود او نا تو فرمولامون جایگذاری میکنیم
توجه کن که اون توابعی که عدد کوچیکه سمت راسته میلش هم انتخاب میشه که جلوی // نوشتم
F(1,16) = min {F(0,16) , F(0,7) [L1]} = min {16 , 7} = 7 // L1
F(1,12) = min {F(0,12) , F(0,3) [L1]} = min {12 , 3} = 3 // L1
F(1,10) = min {F(0,10) , F(0,1) [L1]} = min {10 , 1} = 1 // L1
F(1,6) = min {F(0,6) , F(0,-3) [L1]} = min { 6 , 1000} = 6 // nothing
حالا مرحله بعد
F(2,16) = min {F(1,16) , F(1,12) [L2]} = min {7 , 3} = 3 // L1 + L2
F(2,10) = min {F(1,10) , F(1,6) [L2]} = min {1 , 6} = 1 // L1 + nothing
و در آخر جواب مساله بدست میاد:
F(3,16) = min {F(2,16) , F(2,10) [L3]} = min {3 , 1} = 1 // L1 + nothing + L3
یعنی با هدر رفتگی 1 و انتخاب میله های 1 و 3
این فقط برای یک شاخه بود. همونطور که قبلا گفتم زمان این مساله نمایی که در اینجا داریم (O(2^n یعنی برای 1 شاخه و سه تا قطعه 1+3^2 یعنی 16 بار تابع رو فراخوانی کردیم. حالا اگه بخوایم چند تا شاخه رو حساب کنیم دو راه به ذهن من رسید
راه اصلی استفاده از حالت چند بعدیه مثلا اگه سه تا شاخه داشته باشیم به طولهای L و K و M و n تا قطعه فرمولی به شکل (F(n,L,K,M رو باید حل کنیم که زمان باز کشتی اون (O(8^n رو داره که سر به فضا میزنه. البته 100% جواب درست رو میده.
راه دوم اینه که با همون فرمول اولی (یک بعدی) حل کنیم و بعد از تموم شدن اولین شاخه همون کار رو با یه شاخه دیگه و قطعه های باقیمونده انجام بدیم که من تست کردم جواب بهینه رو داد. یعنی نتونستم مثال نقضی ارائه کنم که با این روش دوم جواب بهینه نده.
اما اگه بتونی یه کم بیخیال پرتی و این جور حرفها بشی زمان اجرات سریعتر میشه. یعنی سعی کنی برای هر شاخه تعداد قطعه های کمتری رو تست کنی تا سریعتر حل بشه
تا اینجای کار شما برای انتخاب اولین شاخه باید تعداد اجرای تابع معادل 39^2 رو متحمل بشی (میتونی بزنی ماشین حساب ببینی چقدر میشه(حدود 550 میلیارد))
تازه این برای اولیشه. برای بقیش هم باید همین حدود (البته هر مرحله کمتر میشه) رو متحمل بشی.
امیدوارم فکر نکنی این راه با تست کردن یکیه. چون تست کردن زمان فاکتوریلی میخواد. یعنی برای اولین میله !39 حالت برای تست داری که یه رقم مافوق فضایی میشه (من نتونستم عددش رو بخونم (یه 2 با 46 تا صفر جلوش) اونم فقط برای اولین میله)
امیدوارم بتونی تو پروژه ات ازش استفاده کنی!!!
البته این چیزی بود که به ذهن من رسید. اگه بتونی یه روش حریصانه یا شبه حریصانه واسه این مساله پیدا کنند اونوقت با 39 بار اجرا حل میشه!!!(بعید میدونم)