Задача 2 от брой 11/2004 - ИМЕНА - Анализ

Втората задача от Конкурса е така наречения проблем за най-къс съдържащ низ (shortest superstring). Задачата е NP-трудна, поради което намирането на оптималния отговор за всеки тестов пример би било невъзможно в приемливо време. Ето защо, в условието се изискваше състезателите да намерят колкото се може по-добро решение. Няма да се спираме върху понятията за NP-трудна и NP-пълна задача, а ще препоръчаме на любознателния читател да се обърне към някоя книга разглеждаща сложност на алгоритми или за кратък увод да прочете началото на анализа на задача 4 от Конкурса 2002-03.

Нека с S₁, S₂, …, S_N означим низовете от входния файл. А с overlap(i,j) бележим максималното застъпване на два низа S_i и S_j –  дължината на най-дългия низ, който е едновременно наставка на S_i и представка на S_j. Без ограничение на общността  можем да приемем, че никой от дадените низове не съдържа в друг. Ако такива има, то можем да ги намерим в процеса на изчисление на застъпванията и да ги игнорираме.

Алгоритъм, намиращ оптималното решение на задачата е този пробващ всички възможни нареждания на низовете един след друг и след това застъпва всеки два последователни възможно най-много. Ако едно нареждане на дадените низовете е i₁, i₂, … i_N, то дължината на низа съдържащ дадените при тази наредба ще е |Si₁| + | Si₂| + … + | Si_N| - overlap(i₁, i₂) - overlap(i₂, i₃) - … - overlap(i_N-1, i_N). За съжаление всички възможни нареждания са N!, което е твърде голямо (за информация 100! е число с над 150 цифри). Ето защо, (почти) всички решения на задачата се състоят условно от две части: изчисляване на застъпванията между всички двойки низове и намиране на подходяща наредба на низовете.

За първата част могат да се използват няколко ефективни алгоритми. Участниците, запознати с анализа на задача 1 от миналогодишния Конкурс (2003-04) или съответните алгоритми ще се досетят, че overlap(i,j) може се изчисли чрез алгоритъма Кнут-Морис-Прат или Z-алгоритъма. Понеже ние се интересуваме от всички overlap(i,·), то е по-разумно да се използва обобщената версия на KMP алгоритъма - алгоритъма на Ахо-Корасик (описан в анализа на споменатата задача). Друг подход е да се построи суфиксно дърво или суфиксен масив за дадените низове и да се използват свойствата му за намиране на застъпванията. През изминалите няколко години се появиха и първите линейни алгоритми за построяване на суфиксен масив на даден низ  - характеристика, която имаха суфиксните дървета, но на цената на много повече памет. Един от тях може да бъде намерен на http://www.cs.helsinki.fi/juha.karkkainen/publications/icalp03.pdf .

Втората част на решението под една или друга форма разглежда проблема за възможно най-добро нареждане на низовете, така че сумарното застъпване между всеки два последователни низа, да е колкото се може по-голямо. Един подход е да се построи ориентиран граф и в него да се разглежда задачата за намиране най-къс цикъл, минаващ през всички върхове (задачата за търговския пътник). Върховете на графа са N+1 – по един съответстващ на всеки низ (v_i съответства на S_i)  и един начален v₀ (имащ фиктивна роля). Теглото (дължината) на реброто от v_i до v_j (нека го означим с w(i,j)) отразява с колко удължаваме строения от нас низ, ако в края му досега е S_i и добавим S_j с възможно най-голямо застъпване т.е. w(i,j) = |S_j| - overlap(i,j). Дефинираме w(0,i) = |Si| и w(i,0) = 0 за всяко i > 0, за да съответства най-късия цикъл в граф на най-дългия низ съдържащ всички дадени. За намиране на добро решение на задачата за търговския пътник близко до оптималното (approximation algorithm)  има различни техники, описани в научната литература. Една от тях е да се използва задача за назначенията (виж задача 3 от Конкурса 2002-03), чрез която намираме цикли нямащи общи върхове и обхващащи всички върхове на графа, общата дължина на които е възможно най-малка. След което обединяваме тези цикли в един.

Ако предпочитаме да не разглеждаме задачата като графова една възможна идея е следната: на всяка стъпка избираме двата низа които имат максимален overlap и ги заменяме с най-късия който съдържа само двата; прилагайки това N-1 пъти накрая ще остане един низ, съдържащ всички дадени низове, защото на всяка стъпка броя на низовете намалява с едно. Друг алгоритъм е този на Blum, Jiang, Li, Tromp и Yannakakis в статията им “Linear approximation of shortest superstring”  - виж  http://citeseer.ist.psu.edu/blum91linear.html . А една по-нова статия е тази на Breslauer, Jiang, и Jiang – “Rotations of Periodic Strings and Short Superstrings” - виж http://citeseer.ist.psu.edu/breslauer96rotations.html .

Трима участника успяват да решат дадените тестови примери във времевото ограничение: Ростислав Руменов (Шумен), Радослав Герганов (София) и Илиан Илиев (София), като те заемат първите три места. Победител в този кръг е Ростислав Руменов от Шумен, чието решение се справя най-успешно с всички поставени тестове примери. Анализът на решението му може да намерите тук.

За въпроси можете да ни пишете на адрес: konkurs@musala.com.

Supported by Musala Soft Ltd.

Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.