n فایل که طول فایل iام [tex]l_{i}[/tex] و احتمال دسترسی به ان [tex]p_{i}[/tex] است به ما داده شده است.میخواهیم این فایل را طوری پشت سر هم قرار دهیم که میانگین زمان دسترسی به فایل ها کمینه شود.
به عبارت دیگر میخواهیم فایل ها را به ترتیب ا تا n شماره گذاری کنیم به طوری که [tex]\sum_{i=1}^{n}(_p_{i\sum_{j=1}^{i}_l{j}})[/tex]
کمینه شود.کدامیک از راه حل های زیر بهترین ترتیب برای این کار است
۱/مرتب سازی بر اساس [tex]\frac{l_{i}}{p{i}}[/tex] به صورت صعودی
۲/مرتب سازی بر اساس [tex]\frac{p_{i}}{l{i}}[/tex] به صورت صعودی
۳/مرتب سازی بر اساس [tex]l_{i}[/tex] ودر صورت تساوی بر اساس [tex]_p{i}[/tex]
۴/ساخت درخت هافمن بر اساس [tex]\frac{l_{i}}{p_{i}}[/tex] و پیمایش اول عمق آن
جواب: گزینه ۱
من خودم اینجوری تحلیل کردم که باید اون فایل هایی که طولشون بشتره و احتمالشون کمتره اول پیمایش بشن اونها که طول فایلشون کمتر و احتماشون بیشتر دیرتر پیمایش بشن اینجوری گزینه ۱ درست میشه و میشه درخت هافمن هم باشه این همون تخلیل درخت هافمن مگه نیست؟؟؟
شبیه کد هافمن هست ولی خود کد هافمن نیست چون الان ما طول رشته ها و مقدار احتمال انها روا داریم و فقط می خواهیم انها را طوری مرتب کنیم که در جستجوی خطی کمترین زمان صرف شود ولی در کد هافمن ما رشته ها را بر اساس احتمال ممکن تعیین می کردیم
جواب بدیهی هست هر رشته ی که احتمال بالاتری داشته باشد باید در دسترس باشد پس باید نزدیکتر ذخیره شود برای اینکه رشته های بزرگ در ابتدا تاخیر ما را زیاد نکند باید طول رشته ها هم در نظر گرفته شود و هر رشته ای که طول کمتری دارد اولویت بیشتری دارد پس L کوچکتر زودتر و P بزرگتر زودتر که حاصل ان کسر گزینه ی یک میشه