Нарекох този метод "индуктивен метод" в моята книга Introduction to Algorithms: A Creative Approach (Addison-Wesley, 1989), защото използва същият принцип като математическата индукция. След това установих, че индукцията обърква много хора при използването й в този контекст, затова тук се нарича "натрупващметод" , което е по-ясно и описателно име.
Проблемът за максималния правоъгълник , описан превъзходно от David Vandevoorde е идеален пример за илюстриране на натрупващия метод. Натрупващият метод не е перфектен и не винаги е най-добрият, но е приложим в много случаи и определено е техника, която трябва да присъства в арсенала на всеки дизайнер на алгоритми.
Проблемът за максималния правоъгълник
Проблемът за максималния правоъгълник може да бъде обобщен като:
Вход: Двоична матрица N×M B.
Изход: правоъгълник в B с максимална площ, обхващащ само единици
Първият проблем при натрупващия метод е определянето на натрупването. При матрици няма голям избор: или ще добавяме нов ред или нова колона (По късно ще виидм, че това не винаги е вярно). Нека добавим нов ред. Предполагаме, че сме намерили най-големият правоъгълник в първоначалната матрица и сега имаме един допълнителен ред. Трябва да определим дали има въобще по-голям правоъгълник с новия ред. Това ограничава търсенето. Трябва да се имат предвид само правоъгълници, завършващи на последния ред. По тази логика изключваме всички нули в последния ред. Това означава, че може да разделим проблема на няколко подпроблеми чрез разглеждане само на интервалите в последния ред, коит осъдържат само единици
Подпроблемите са независими един от друг, така че трябва да разгледаме само един от тях . Същото решение ще се приложи и за останалите.
Гледайки всеки подпроблем, сега търсим най-големият правоъгълник, който завършва на последния ред, за който знаем че има само единици. За целта трябва да знаем за всяка колона i дължината на долния блок от единици, да го наречем Ci. Тази информация лесно се намира при добавянето на ред- за всяка колона или увеличаваме дължината на блока ( ако последния ред съдържа 1) или се прави 0 (ако съдържа 0). Разделянето на подпроблеми е използвано смао за простота- лесно може да се смята целият ред(с нулите) за един проблем. След тази информация проблемът може да се определи като едноразмерен:
Вход: поредица от цели числа, C1, C2, ..., Ck.
Изход: интервалът [i,j] , в който е максимално произведението на дължината на интервалът (j-i) и минималното число в него.
(Лицето на правоъгълника от единици отговаря на това произведение : ширината на правоъгълника отговаря на дължината на интервала,а височината му на най-малкото число в него).
Натрупващият метод ни позлволи да намалим двуизмерният проблем в едноизмерен. Ако искаме да намерим оптимално репение O(MN) за първоначалния проблем трябва да решим този едноизмерен проблем за линейно време O(k). Използвайки натрупващият метод отново, предполагаме че знаем как да решим проблема при k числа и трябва да изследваме k+1 число, да го наречем Ck+1. Ако е успешно това ще намали проблема още един път и ще ни позволи да се концентрираме върху само едно число.
Трябва да се концентрираме само върху интервали, които завършват в Ck и проверяваме как ги променя Ck+1 . Ако Ck+1>=Ck най-донрият интервал който завършва в Ck може да бъде удължен и да завършва в Ck+1 без промяна на неговото минимално число, така че той е най-добрият възможен интервал. Но ако Ck+1<Ck неможе лесно да се определи най-добрият интервал.
Без Ck+1=3 най-добрият интервал (2a) се състои от последните две числа имащи произведение min{6,5}×2=10. Увеличаването на този интервал с числото 3 (2b) дава min{6,5,3}×3=9, което не е най-доброто. Но тъй като най-малкото число сега е 3 може да използваме по-голям интервал (2c), имащ произведение min{3,6,5,3}×4=12. Ако увеличим на цял ред (2d) ще получим произведение min{4,2,3,6,5,3}×6=12. Няма лесен начин за определяне само от гледане на Ck+1 и най-добрият интервал до Ck. Това изглежда като провал за натрупващия метод, защото само концентрирането върху Ck+1 не изглежда достатъчно.
Но натрупващият метод може да бъде приложен по много начини и затова е толкова мощен. Натрупването на по едно число в края на поредицата е естествен, но не единстен начин за натрупване. Може би вместо при натрупване да гледаме последното число Ck+1 трябва да гледаме първото число C1? В този случай първото число има съвсем същият ефект както последното, така че това няма да помогне. Но защо да не използваме най-малкото число в интервала или най-голямото? Получава се ,че използването на най-малкото или най-голямото число води до два различни оптимални алгоритъма.
Да започнем с най-малкото число, да го наречем m. За простота ще използвам m за стойността и за променливата. Как може m да влияе на решението ? Ако най-добрият интервал съдържа m, то този интервал съдържа всичкo. С други думи ако m е в най-добрия интервал, то тогава този интервал е цялата поредица. Запомняме това и проверяваме алтернативите. Ако m не се съдържа в най-добрия интервал, тогава този интервал е отстрани на m или отляво или отдясно. Сега разделяме проблема на два независими подпроблема, всеки от който може да се реши рекурсивно, така че проблема е решен. Например в
се виждат последователно избраните интервали отгоре надолу 2, 3, 4, 5 и 6. Получаването на реализация на линейно време на това решение не е очевидно, но има надежда , тъй като обработката на m е за константно време.
Да започнем натрупващият метод при отчитане на максималното число, да го наречем M. Това се явява малко по-хитро, но води до по-лесен за реализация алгоритъм. Отново - как M може да влияе н арешението? Ако M е част от интервалът има две възможности. Интервалът се състои само от M ,което дава лице M×1 = M или интервалът включва и някой от съседните на M числа. Във втория случай M няма да допринася повече отколкото неговият съсед. Така ако можем да открием подходящият съсед на М , можем да му дадем приноса на М, като определим, че съседът му има двоен принос и не гледаме повече М. Ако може да правим това безпроблемно имаме натрупващо решение, защото може да обработваме по едно максимално число .
Може да направим брояч за всяко число, който да показва колко от неговите съседни трябва да се смятат, когато това число се използва за най-добрия интервал. След това премахваме М и увеличаваме броячът за някой от съседните му (тайната кое съседно число да изберем ще бъде разкрита след малко). Всъщност какво ще стане когато се гледа най-малкото число в интервал - всички негови по-големи съседи са били рагледани преди това и имат собствени броячи. Така най-малкото число ще знае колко е голям интервалът му.
Да предположим, че числата са са в намляващ ред започвайки от ляво. Алгоритъмът ще вземе C1 като първи правоъгълник , след това броячът на C2 се увеличава на 2. На втората стъпка се брои два пъти C2 (защото неговият брояч е 2) и неговият правоъгълник е 2×C2. Проверяваме дали това е повече ор предишния най-добър правоъгълник (C1) и вземаме по-големият от тях. След това задаваме брояч на C3 , който става 3 и има лице 3×C3 и така нататък. Това е най-простият случай и по принцип алгоритъмът работи добре.
Кой съсед да използваме - по-големият или по-малкият? Отговорът е по-големият, защото е по-безпроблемният избор. Всеки интервал, който съдържа някой от съседите на М ще съдържа поне М и по-големият съсед (може да съдържа и двата съседа). Чрез добавянето на приноса на M към по-големия съсед ни дава сигурност, че М се дава принос към всеки интервал, който го съдържа.Пример за подобно смятане е :
Приносът на 6 е 1×6. Второто по големина е 5, чиито брояч сега е 2, така че има принос 2×5. Следващото е 4, което дава своя принос на съседа си 2. Следващото е 3 (Аз избрах дясното 3, но без проблеми може и да е лявото), което има принос 3×3. Когато се разглежда другото 3 броячът е 4, така че лицето става 4×3=12. Последното е 2, чиито брояч става 6 и води до друго най-добро решение 12.
Двата предложени алгоритъма не са пълни. Трябва внимателно да се изберат структури от данни, които извършват ефективно всички операции.Дяволът е в детайлите. Но детайлите са по-лесни след цялостното схващане на алгоритъма, каквото направихме сега. Една от силните страни на натрупващия метод е в лесното намиране на алгоритмична идея.
Алгоритъмът показан по-горе се сътои от цхетири стъпки, които се повтарят за всяко число:
1. Намираме следващото по големина M.
2. Проверяваме текущото лице спрямо предичното най-добро.
3. Увеличаваме броячът на по-големия съсед на M.
4. Изтриваме M.
За да получим списъкът с максиммумите , трябва да сортираме числата. За радост всички числа са от 1 до N (тъй като те са броя на единиците в колона) и можем да ги сортираме за линейно време използвайки прост метод за сортиране. Намирането на съседните числа може да стане чрез използване на двойно свързан списък, който позволява изтриването на число. Всички тези операции могат да се извършат за линейно време. (Алгоритъмът може да се опрости допълнително след забележката, че сортирането не е фатално)
Заключение
Натрупващият метод е полезн начин за откриване на нови алгоритми. Той може да доведе и до нови начини за решение. Но не е магическа пръчка и не може да замени интуицията и опита, само помага те да се развият.
Уди е професор по компютърни науки в Аризонския университет.
Няма коментари:
Публикуване на коментар