Анализ на решенията
Категория: Интернет
понеделник, 10 Февруари 2003 0:00ч
Нека S ={1,2,...,|S|}, а на T={1,2,...,|T|}. Нека G(SИT,E) е двуделен граф, т.е. множеството от ребрата му е разбито на две подмножества S и T такива, че за всяко ребро (i,j) от E е в сила i е от S, а j е от T. Подмножеството от ребра M наричаме съчетание, ако всеки връх на графа е край на не повече от едно ребро от M. Едно от възможните решения на задачата за намиране на съчетание с максимален брой ребра в двуделен граф се основава на понятието алтерниращ път. Нека M е произволно съчетание в графа. Върховете, които са краища на ребра от M, наричаме покрити, а тези, които не са краища на ребра от M - свободни. Пътят vi1, vi2,..., vim в двуделен граф наричаме алтерниращ (относно M), ако в него се редуват свободни и покрити върхове. Ако началният и крайният върх на един алтерниращ път са свободни, той се нарича нарастващ. Основната теорема тук гласи, че M е с максимален брой елементи тогава и само тогава, когато не съществува нарастващ алтерниращ път относно M. Действително, ако се изхвърлят от M тези ребра, които участват в нарастващ алтерниращ относно M път, а се добавят тези, които участват в пътя, но не са от M, ще се получи ново съчетание M’, което има едно ребро повече от M. Построяването на нарастващи пътища обикновено се извършва с модификация на обхождане в ширина.
Нека сега за всяко ребро (i, j) е зададена цена cij - реално неотрицателно число. Спокойно можем да считаме, че двуделният граф е пълен, т.е. всеки връх от S е свързан с ребро с всеки връх от T (липсващите ребра можем да добавим, като им дадем цена 0). Сега задачата за съчетение с максимален брой ребра е тривиална. Интересна задача е да се намери съчетание (то непременно ще е с максимален брой елементи), което има максимална цена, т.е. максимална сума от цените на участващите в него ребра. В нашата задача |S|=|T|=n, което не е от съществено значение.
Една възможност за решаване на задачата за съчетание с максимална цена в двуделен граф е с помощта на дискутираната вече техника потоци в мрежи (вж. например решение на зад. 5 от бр. 4 от 2001 г.). Действително: да добавим един връх за източник и да го свържем с върховете от S, както и един връх за цел и да свържем всеки връх от T с него. На всяко от ребрата да поставим капацитет 1. За цени на ребрата, които добавихме, нека поставим числото 0, а на всяко ребро (i, j) на двуделния граф - числото M + 1 - cij, където M е максималната цена на ребро от графа. В получената по този начин мрежа трябва да решим задача за намиране на максимален поток с минимална цена, която, разбира се, е малко по-трудна от задачата, коментирана в цитирания по-горе брой на списанието. Сложността на такъв алгоритъм ще бъде с O(n3).
Задачата за съчетание с максимална цена може да бъде формулирана и като следната задача на линейното програмиране: да се намерят такива стойности на променливите xij, 0ЈxijЈ1, SiОS xij=1, SjОT xij=1, i=1,2,...,n, j=1,2,...,n, че сумата SiОS SjОT cij.xij да е максимална. Не е трудно да се види, че решението на тази задача винаги е целочислено и xij=1 тогава и само тогава, когато реброто (i, j) участва в съчетание с максимална цена.
Споменатият по-горе алгоритъм на Кун, известен още като унгарски алгоритъм, е сложна смес от техниката на алтерниращите пътища и линейното програмиране. Като използва спецификата на конкретната задача, той я решава със сложност O(n3). Традиционно за линейното програмиране е да се обърне дадената задача в така наречената дуална, която в случая е следната: на всеки връх i от S да съпоставим променлива ui, a на всеки връх j от T - променлива vj. Дуалната задача е да се намерят такива стойности на променливите ui и vj, 0Јui,vj и cijЈui+vj за всяко i от S и за всяко j от T така, че Sui+Svj да е минимална. Не е никак лесно да се види връзката между двете задачи, но тя се дава от следните три условия:
а) ако xij=1, то ui+vj= cij;
б) ако ui > 0, то SjОT xij=1;
в) ако vj > 0, то SjОsxij=1.
Идеята на унгарския алгоритъм е да се започне с някакви стойности на променливите ui и vj, за които са изпълнени условията а) и в) и да се поддържат тези условия изпълнени през цялото време на работата, като постепенно се намалява броят на неизпълнените условия б) с използване на техниката на нарастващите алтерниращи пътища. Тъй като в този случай ребрата имат цени, за нарастване на пътищата се използва модификация на алгоритъма на Дейкстра, вместо обхождане в ширина (по начина, който споменахме по-горе, задачата се обръща предварително от задача за максимум в задача за минимум, тъй като ще се използва алгоритъмът на Дейкстра).
Както се очакваше, голям брой участници (17) успяха да решат напълно задачата в поставените рамки. За да се определи победител, се наложи се да използваме като критерий времето за работа върху “най-сложния” тест (номер 9). Програмите на 17-те участника бяха изпълнени многократно с този тест, за да се получи ясна разлика във времената за работа. Най-бързо се оказа решението на Иван Станишев. Близко до времето на победителя са постиженията на Илиян Илиев, Николай Тодоров и Захари Караджов. Още тринадесет участника предложиха добри решения, които при малко по-голямо времево ограничение биха заслужили (почти) пълен брой точки.
Немалко участници се опитаха да решат задачата с “greedy” или “backtracking” алгоритми. За тази стандартна задача това видимо не можеше да доведе до добър резултат.
