Влияние върху производителността
Изтегляне 1.47 Mb.
|
Свързани:
saap conspect
- Навигация на страницата:
- Best Fit
First FitПредишният алгор. създава нова торба не винаги когато това е нужно, защото разглежда само последната. Напр. за схемата горе, ел. 0.3 може да се постави в В1 или В2 а не в нова. First Fit стратегията сканира торбите подред за да установи дали може да постави новия ел. Тъй като се сканират предходните торби, О(N ). Може да се сведе до O(N log N) – ако сканираме както при бинар. търсене. Видно е че във всеки момент най-много 1 торба може да е запълнена ½, тъй като ако са 2, то могат да се поставят в 1. Значи най-много 2М спрямо оптимумът от М торби. проверяваме дали следващата в поредицата може да се постави в торбата, която съдържа последния ел. ако не – нова торба.Работи с линейно време. Ето резултат над предходната поредица: Т2 Нека М е оптималния брой торби за пакетиране на I ел. Next fit никога не използва повече от 2М торби. Док. Разглеждаме съседните B j и B j+1. Сумата от обемите в тях е >1, иначе в 1 торба. Aко направим тези разсъждение за всички съседни, виждаме че най-много ½ пространство е похабено. Използвани са най-много двукратен брой торби. Ето най-лоша последователност на входа:нечетни si имат размер 0.5, четни – размер 2/N. Нека N се дели на 4. Оптимално пакетиране е от N/4 +1. Реалното в този алгоритъм заема N/2. T.e почти двойно: Best FitВместо да поставяме нов елемент в първа възможна торба, го поставяме там където е възможно, но и има най-малко свободно място.Елемент с тегло 0.3 е поставен в В3, а не в В2. Има подобрение, но не и за лошите поредици. Off-Line алгоритми. Помощни теореми и оценки на подхода Off-line алгоритмиСега можем да аналзираме цялата поредица, преди да подреждаме. Големият проблем на on-line алгоритмите е че не пакетират добре големи ел. когато те идват към края. Добре би било големите да ги сортираме отпред. Това е алгоритъмът first fit decreasing: В случая това е и оптимал.решение. Не винаги е така. Значи считаме, всички ел. са вече подредени намаляващо.Ще док, че ако оптимал.пакетиране изисква М торби, сега са нужни не-повече от (4М + 1)/3 Изтегляне 1.47 Mb. Сподели с приятели:
|