Влияние върху производителността
Изтегляне 1.47 Mb.
|
Свързани:
saap conspect
- Навигация на страницата:
- On-line алгоритми
Постъпателни алгоритми – проблемът „пакетиране” Online & FirstFitТези алгоритми са бързи, но не винаги дават оптимално решение. Имаме N пакета с размери s1….s N (0 <= s i <1). Искаме да ги пакетираме в min брой торби, като всяка торба има обем 1. Ето пример: Съществуват 2 версии на решения:on-line всяка единица се поставя преди следваща (няма връщане назад). Off-line – първо изследваме всички, тогава започваме пакетирване. On-line алгоритмиНе винаги дават оптималното решение. Разглеждаме поредица от I1 ел.от общо М в тегло ½ -б, следвани от останалите с тегло ½+б (б е нещо малко): очевидно, всички могат да се пакетират в М (1 малка + 1 голяма). Нека алгоритъм А прави това пакетиране. Тогава А ще постави малките I1 (половината) ел. всеки в отделен чувал (а не по 2) – общо напр. в М торби. Но как ще знае че следващите са по-големите, а не обратно. Значи А винаги ползва 2М торби вместо М. Тъй като краят (общия брой )е неизвестен , алгоритмите от този вид дават само локална гаранция. Теорема 1 :съществуват вх. поредици, които карат всеки on-line алгоритъм да използва поне 4/3 от оптималния брой торби. Док. Предполагаме обратното и нека М е четно. Алгоритъм А обработва входна поредица I1 от М малки ел., следвани от М големи. Вече сме обработили първите М ел. и сме използвали б торби. (оптималното е б=М/2). Значи (оптимистично )предполагаме че алгоритъмът постига : 2б/М < 4/3 б/М <2/3 Нека всички елементи са обработени. Имаме б торби с първите б ел. (нали алгоритъмът работи оптимално и не може да оставя по 2 големи ел. за 1 торба). Тогава след края първите б торби ще имат по 2 ел. (малък и голям), а следащите - по 1 голям. За 2М ел. ще са нужни 2М – б торби. Оптимумът беще М. Следователно: (2М – б) / М < 4/3 б/М >2/3 Имаме противоречие. Следователно няма on-line алгоритъм, даващ по-добро от 4/3 спрямо оптималното решение. Изтегляне 1.47 Mb. Сподели с приятели:
|