Алгоритъм на решението на задача 2




ИмеАлгоритъм на решението на задача 2
Дата на преобразуване22.10.2012
Размер35.35 Kb.
ТипРешение
източникhttp://konkurs.musala.com/content/c01/p2/solution_boyan_angelov.rtf
Алгоритъм на решението на задача 2


Предложената задача съществено се отличава от задача 1 по сложност. Докато в предишната задача алгоритъма не беше особено сложен и решаващ за скоростта на изпълнение ( решаващи бяха структурите от данни и файловия вход/изход ), в настоящата задача нещата са точно обратните.


Тук имаме един проблем, който може да се причисли към семейството на “knapsack” проблемите. Интересната модификация тук е че размера на необходимата ограда се променя взависимост от това кое дърво е отсечено. “Knapsack” проблемите имат множество приложения в практиката и са изследвани обстойно през последните десетилетия. Има предложени множество алгоритми за намиране на оптимални или близки до оптималните решения, като по-известните са динамичното програмиране, “branch and bound” алгоритми и т.н. “knapsack” проблемите имат сложност NP и алгоритмите за решение имат полиномиална сложност.


При зададените условия на задачата алгоритъма с пълно изчерпване на комбинациите веднага отпада, тъй като К <= 50 ( намиране на решението при К = 50 би отнело години ). Така че е необходимо да се използва някой от оптимизираните алгоритми. Аз съм се спрял на решение използващо динамичното програмиране, тъй като дава един от най-добрите резултати.


Динамичното програмиране се състои в разбиване на проблема на по-малки проблеми, чието решение се намира по-бързо. Това е техника, която намира успешно приложение в решаването на много проблеми от реалния свят. За целта се използва следната рекурентна зависимост:


Означаваме с p = D( i, w( i ) ) решението на задача с i-дървета и w( i ) метра необходима ограда за да се оградят. “p” e цената на отрязаните дървета. Тогава имаме следната рекурентна зависимост за оптималното решение:


min( price( K ), D( K-1, w( K ) ) ), ако length( K ) >= w( K )

p = D( К, w( К ) ) =

min( D( K-1, w( K )), D( K-1, w( K - 1 ) – length( K )) + price( K )),

ако length( K ) < w( K )


като price(K) е цената на К-тото дърво, length(K) е метрите ограда, които могат да се построят ако се отсече К-тото дърво, а w( K – 1 ) e оградата необходима за да се оградят дърветата като се отреже К-тото дърво. Идеята е да се провери на всяка стъпка колко ще е цената ако се отсече i-тото дърво и колко ще е ако не се отсече и да се вземе минимума. За да не се превърне алгоритъма в алгоритъм на пълното изчерпване се спира ако при отсичането на i-тото дърво оградата е достатъчна, за да се заградят останалите дървета. Също така в конкретната имплементация на алгоритъма са спира ако цената е по-висока от намерена вече временна оптимална цена.


Описаният алгоритъм се представя доста добре в повечето от случаите. Сложността му е

О( К * W ), където W e началната необходима ограда. Естествено, в някои случаи би могъл и да представи доста зле ( О( 2 на степен К ) ), но това са случаите в които всеки алгоритъм би се затруднил ( ако видя реализиран алгоритъм, който се представя добре в някои подбрани от мен случаи ще сваля шапка на автора ).


Естествено биха могли да се направят някои оптимизации. Например в моята имплементация аз първо сортирам дърветата в нарастващ ред по отношението цена/метри и намирам начално оптимално решение като отсичам първите j дървета така че оградата да е достатъчна за останалите. В някои случаи това дори е оптималното решение, но не винаги. Но при така зададени входни данни алгоритъма работи средно 10 пъти по-бързо, отколкото ако дърветата се дадат разбъркани и началната оптимална цена е равна на безкрайност.


Има възможности и за още оптимизации използвайки стохастични модели, но това вече излиза извън пределите на задача от конкурс за програмиране ( в интерес на истината аз съм имплементирал една малка такава оптимизация, която се състои в задължително отрязване на част от дърветата преди пускане на алгоритъма, но при определени условия за размера на необходимата ограда и броя на дърветата ).


Няма да описвам структурите от данни, които съм използвал, тъй като не са нищо особенно. Само ще спомена че гората се пази в двумерен масив, като в 0 – вия ред и стълб се пази броя на дърветата в съответния ред и стълб за да се намира по-бързо размера на оградата, необходима за заграждане на останалите дървета. Това си е разход на памет, но пък улеснява нещата.


Ами, това е

Свързани:

Алгоритъм на решението на задача 2 iconЗадача 4 Описание на решението и реализирания алгоритъм
Първото решение, което може да хрумне на човек, е да напише бектрекинг, реализиращ пълно изчерпване на всички възможни оцветявания....
Алгоритъм на решението на задача 2 iconАлгоритми. Определение, свойства, видове
Един от най-важните етапи при решение на задача е съставянето на нейният алгоритъм
Алгоритъм на решението на задача 2 iconЗадача №1 Задача №2 Задача №3 Задача №4 Задача №5 Апелляция Кочегаров Сергей Сергеевич моу «Гимназия»
Члены жюри: Волокитина Т. И., Виниченко В. Д., Сурков С. В., Белова Н. Н., Воронова Н. И., Черняева И. В
Алгоритъм на решението на задача 2 iconТест Информатика 2012 Отворете празен файл в Ексел. Направете 5 различни страници и ги наименувайте Задача 1, Задача 2, Задача 3, Задача 4, Задача 5 Първа задача
На първата страница – направете таблица със следните редове и колони. В тази таблица ще сложите автоматична информация от другите...
Алгоритъм на решението на задача 2 iconЗадача А. Решението и ще доведе до задача Б
Загадката на Сфинкса е една от най-старите и най-известните. Отговорът е „човекът,” който пълзи на 4 „крака” сутрин (когато е бебе),...
Алгоритъм на решението на задача 2 iconАлгоритъм на Loop
Този subdivision алгоритъм е създаден през 1987 година от Charles Loop. Работи само с мрежи от триъгълници. На всяка стъпка от алгоритъма...
Алгоритъм на решението на задача 2 iconЗащита от хакери, Ларс Кландер Глава 5
Както и при нормалния цифров подпис, сертификатът се базира на алгоритъм с публичен ключ – криптиращ алгоритъм, използващ два ключа...
Алгоритъм на решението на задача 2 iconАлгоритъм на Doo-Sabin
Алгоритъмът на Doo-Sabin е алгоритъм за subdivision на 3D повърхнини. Началната мрежа
Алгоритъм на решението на задача 2 iconГониометричен алгоритъм за изчисляване на скоростта на ракета
Резюме: Предлага се прост алгоритъм за изчисляване на скоростта на ракета от филмов стоп-кадър, където е видим конусът на кóсата...
Алгоритъм на решението на задача 2 iconОлимпиада по програмиране на сащ април 2001
Открийте алгоритъма и го използвайте за да напишете програма, която генерира триъгълници по същия алгоритъм, като входните данни...
Поставете бутон на вашия сайт:
Документация


Базата данни е защитена от авторски права ©bgconv.com 2012
прилага по отношение на администрацията
Документация
Дом