Задача 4 от брой 1/2005 - МЕД - Анализ

Четвърта задача от конкурса по програмиране на PC Magazine Bulgaria и Musala Soft попада в клас задачи, в които се търси решение максимално близо до оптималното или така наречените апроксимационни задачи. Условието може да бъде преформулирано така: Даден е ориентиран, претеглен, цикличен мултиграф. Да се отстранят ребра, така че графът да стане ацикличен и запазените ребра да имат най-голяма тежест. Оптималното решение трудно може да бъде намерено и нашите участници трябваше да търсят различни подходи за решаването на проблема.

На вниманието на нашите читатели ще представим подхода на Ангел Джигаров, чиято грешка в името на входния файл го лиши от победата в кръга.

В решението ще се абстрахираме от графа. С a(i,j) отбелязваме сумата от приоритетите буркан номер i, да бъде изяден преди буркан номер j. Ако не съществуват такива приоритети, то a(i,j) = 0.

Нека допуснем, че в даден момент сме получили пермутация P[1..N] на числата от 1 до N, която представлява реда, по който трябва да бъдат изядени бурканите с мед. Тогава всеки приоритет i->j е изпълнен тогава и само тогава когато позицията на числото i в P е преди позицията на числото j. Следователно можем да сведем задачата до намиране на колкото се може по-добра пермутация P.

Лесно се забелязва, че при генерерирана произволна пермутация в начало, шансът даден приоритет да бъде изпълнен е 50%. Тогава общата сума от спазените приоритети в средния случай ще бъде половината от сумата на всички приоритети, което ни дава минимум 50% от точките.

Оттук нататък пред нас стои въпросът как от дадена пермутация P да намерим пермутация P’, такава че сумата от приоритетите, които са изпълнени в P’ да е по-голяма от тази в P. За тази цел предлагаме три независими една от друга оптимизации.

Първата оптимизация се състои в следното:

За всеки връх i (за i от 1 до N) означаваме с g(i) сумата на a(i,j) – a(j,i), за всяко j от 1 до N. След което сортираме числата от 1 до N спрямо g(i) в низходящ ред и така получаваме нова пермутация.

Втората оптимизация се базира на метода “разделяй и владей”. Нека е дадена функция f(left,right), където 1 ≤ left ≤ right ≤ N, която оптимизира разположението на числата в пермутацията P от позиция left до позиция right.

Очевидно ако left = right, то функцията не трябва да прави нищо. Когато интервалът [left,right] е от два елемента, функицята трябва да провери дали не е по-добре да размени елементите P[left] и P[right].

В случай че функцията f трябва да оптимизира интервал с повече от два елемента, ще означим middle = (left + right) / 2. Изпълняваме функциите f(left,middle) и f(middle+1,right), след което по аналогичен начин на интервал с два елемента проверяваме дали не е по-добре да разменим местата на двете половини а именно интервалът [left;middle] да си смени мястото с [middle+1;right], като наредбата в тях се запази.

Извикване на f(1,N) преставлява втората оптимизация.

Третата оптимизация е подобна на сортировка с метода на вмъкване.

За всяка позиция i от 1 до N, поверяваме дали не съществува позиция j, такава че ако елемента P[i] бъде преместен на позиция j, без да пренареждаме останалите елементи, сумата от спазените приоритети да нарастне.

Сложността на трите оптимизации е съответно O(N.logN), O(N²) и O(N²). Така сложността на цялата програма е О(N²).

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

Победител в кръга стана Ростислав Руменов от Шумен с 98.77 точки.

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

Supported by Musala Soft Ltd.

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