Задача 5 от брой 2/2005 - МРЕЖА - Анализ

Дадената задача в този кръг може да се разгледа като обобщение на задача 5 от 2001-02 година и задача 4 от 2003-04 година, които се свеждаха до намиране на максимален поток в граф. Предлагаме на тези, които не са запознати с този проблем, да прочетат първо анализите на горните две задачи на сайта на конкурса.

Крайния ориентиран граф (без примки) G(V,E), по чиито ребрата са дефинирани функции cap и cost с положителни реални стойности, ще наричаме мрежа ако във V съществува точно един връх s, от който само излизат ребра и точно един връх t, в който само влизат ребра. Стойността cap(i,j) се нарича капацитет на реброто (i,j) (т.е. максималната стойност на потока, който може да “тече” по реброто (i,j)), cost(i,j) се нарича цена на реброто (i,j) (т.е. колко струва преминаване на единица поток през реброто), върхът s – източник, а върхът t – цел на мрежата.

Поток с цена в мрежата наричаме функция f с реални стойности, дефинирани върху ребрата на мрежата, за която са в сила:

·          f(i,j) ≤ cap(i,j) и f(i,j) = -f(j,i) за всяка двойка върхове i и j.

·          за всеки връх i, различен от s и t, сумата от f(i,j) за всяко j от V е равна на 0.

·          cost(i,j)= -cost(j,i), за всяка двойка върхове i и j

Стойността на потока наричаме числото |f| = å_jÎV f(s,j) = å_iÎV f(i,t), а цена на потока – cost(f ) = å_f(v,w)>0 cost(v,w) f(v,w) = å_i,jÎV cost(v,w) f(v,w) / 2. Поток има минимална цена, ако не съществува поток g, за който |g|=|f| и cost(g) < cost(f).

В нашата задача е известен потокът, който се търси, но това не пречи задачата да се разглежда като задача за максимален поток. Добавянето на супер-източник и ребро от него към източника със стойност зададения поток свежда задачата до намиране на максимален поток с минимална цена. За да е изпълнено условието cost(i,j)= -cost(j,i), то може да удвоим върховете в графа. Всеки връх v се замества с два върха v’ и v’’, свързани с ребро . Всички ребра влизащи във v сега влизат във v’, а всички излизащи от v – излизат от v’’. Капацитетът на новото ребро (v’, v’’) ще е неограничено (т.е. достатъчно голямо число), а цената му 0. Такава конструкция гарантира единствено ребро между всеки два върха на графа след като неориентираните ребра се заменят с две ориентирани (по една във всяка посока). Ребрата чиито край е източника или целта трябва да се ориентират еднопосочно, за да се изпълнени условията за графа.

Остатъчната функция се дефинира като res(i,j) =cap(i,j) - f(i,j), а остатъчната мрежа R е граф с върхове върховете G, същите източник и цел, ребра двойките (i,j), за които res(i,j)>0, с капацитет res(i,j) и същата ценова функция.

Решаването на задачата максимален поток с минимална цена има различни подходи. Ето няколко от тях.

Идеята за намаляване на цените се основава на това, че поток има минимална цена тогава и само тогава, когато остатъчната мрежа няма отрицателни цикли. За да намерим максималния поток с минимална цена можем първо да намерим какъвто и да е максимален поток, а после ще намаляваме цената му „пускайки” колкото се може повече поток по отрицателните цикли. Това се повтаря докато има отрицателни цикли. За капацитети/цени, които са реални числа този алгоритъм може никога да не завърши, но при целочислени рано или късно ще приключи. Времето за изпълнение на този алгоритъм не е полиномиално.

Алгоритъмът на Форд-Фълкерсън за намиране на максимален поток използва нарастващи пътища (път от s до t с ребра с положителен капацитет в остатъчния граф). Така втората идея за намиране на максимален поток с минимална цена използва верността на твърдението, че ако f е поток с минимална цена и p е нарастващ път с минимална цена, то добавянето на p към f дава поток с минимална цена. Сложността на този алгоритъм е O(<брой стъпки> * <сложността за намиране нарастващ път с минимална цена>). Ако се използва търсене в ширина за строенето на нарастващия път, то това е O(N*M*|f^*|), където f^* е максималният поток. Сложността може да бъде подобрена, като се използва трансформация върху цената на ребрата, за да ги направим неотрицателни и да можем да използваме алгоритъма на Дийкстра. Тази трансформация е: cost"(i,j) = cost(i,j) + dist(i) - dist(j), където dist(i) e дължината на най-късия път от s do i. Понеже на всяка стъпка остатъчната мрежа се променя, то трябва да се променят и трансформираните цени. Така сложността може да се сведе до O(N*M+|f^*|*(M+N*logN)).

Използвайки „скалиране” може да се подобри алгоритъмът, когато потокът е много голям. Идея на скалирането при намирането на максимален поток е във всяка стъпка на алгоритъма добавяме поток само по онези ребра в остатъчната мрежа с капацитет ≥ z. Между всеки две стъпки z се намалява наполовина. Тази идея е приложима и при намирането на максимален поток с минимална цена, но чрез някои модификации. Както и по-горе, за по-ефективното реализиране на алгоритъма се изисква трансформация, при която ребрата в остатъчната мрежа не са отрицателни. Така може да се получи алгоритъм със сложност O((N*М+N*logN)*logC), който очевидно зависи от броя върхове, броя ребра и максималния капацитет на всяка ребро, но не и от стойността на потока. За по-задълбочено запознаване с тази и други интересни задачи препоръчваме книгата „Network Flows: Theory, Algorithms, and Applications” на Orlin, Magnanti, Ahuja.

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

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

Supported by Musala Soft Ltd.

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