Алчен алгоритъм за "Раница"
Алчен алгоритъм за проблема с раницата с гарантирана точност 2 .
Както вече отбелязахме, алчните евристики са най-простите и популярни методи за решаване на различни изчислително трудни проблеми. Нека да видим какво може да направи тази евристика за проблема с раницата.
Разгледайте следния проблем.
Задача 13. Раница (раница) "
c1; : : : ; c n , c j 2 N - "разходи" на позиции;
a 1; : : : ; a n , a j 2 N - "размери" или "тегла";
B 2 N - "размер на раницата".
Намерете максималната стойност f на целевата функция
с ограничение на размера на "раницата":
a i x i B; x i 2 f 0; 1g:
2.1. АЛГОРИТМИ С ОЦЕНКИ НА ТОЧНОСТ
По същество задачата означава да изберете артикули с най-висока обща цена, които се побират в раница с даден размер. Този проблем често възниква при избора на оптимален контрол в различни области (разпределение на бюджета на отдела за проекти и др.).
Нека разгледаме какъв резултат може да се постигне, като се използва, както в раздел 2.1.1, "алчният подход". Първата идея, която обикновено възниква, когато се запознаете с този проблем, е да изберете обекти според
намаляване на относителната им цена, поставяне на всичко, което се побира в раницата (вижте алгоритъм 18). За съжаление нищо добро не може да се каже за качеството на евристиката на Алгоритъм 18.
Упражнение 2.1.10. Докажете, че за всяко число k е възможно да се представи входен набор от данни, за който Алгоритъм 18 ще избере набор от данни, който е k пъти по-лош от оптималния.
Ясно е, че проблемът е, че след като е "поласкан" от първия малък, но "сравнително скъп" артикул, алгоритъмът рискува да пропусне голям и ценен артикул от оптималния набор.
Оказва се, че качеството на работа е гарантираноТази евристика може да бъде подобрена, ако след приключване на нейната работа цената на полученото осъществимо решение се сравнява с максималния коефициент c max и в съответствие с максимума се избира или „алчно решение“, или един артикул с максимална цена (предполагаме, че размерите на всички артикули не надвишават размера на раница - в противен случай те могат просто да бъдат изключени от разглеждане).
Получава се така нареченият модифициран алчен алгоритъм (виж Алгоритъм 19), за който вече може да се гарантира качеството на намереното решение.
Теорема 4. За стойността на решението f G , получено чрез модифициран алчен алгоритъм 19 “Ryuk- и оптималната стойност на f за задача 13 “Раница”,