Задача 4 от брой 01/2004 - ЕКСПЕРИМЕНТИ - Анализ

Четвъртата задача от тазгодишния Конкурс е от вид, който не е непознат за нашите реoдовни участници. Тя е подобна на задачата от петия кръг на Конкурса от 2000-2001г. Общото между тези две задачи е, че те могат да бъдат атакувани с една и съща, много мощна алгоритмична техника – потоци в мрежи. Кратко въведение в терминологията на задачата за намиране на максимален поток в мрежа може да се намери на страницата на Конкурса, в коментара към посочената по-горе задача. Също там може да намерите и описание на един от основните алгоритми за намиране на максимален поток в мрежа – алгоритъма на Ford-Fulkerson. Затова няма да повтаряме тук тези уводни бележки. Препоръчваме на читателите, за които такъв кратък увод в тематиката не е достатъчен, да се обърнат към някой от основните текстове по Теория на алгоритмите (например към често споменаваната в нашите коментари книга Introduction to Algorithms на T. Cormen, Ch. Leiserson и R. Rivest).

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

За решаването на настоящата задача построяваме мрежа по следния начин. Първо построяваме крайния ориентиран граф на мрежата. Избираме по един връх a₁,a₂,…,a_M за всеки от уредите или приспособленията, необходими за извършването на експериментите и по един връх b₁,b₂,…,b_N за всеки експеримент. Добавяме отделно двата специални върха s и t – източник и цел на мрежата, съответно (вж. Фиг. 1). Свързваме източника s с всеки един от върховете  a_I, I=1,2,…M  с ориентирано ребро (s,a_I) и за капацитет c(s,a_I) на всяко такова ребро определяме цената на съответния уред или приспособление. Свързваме всеки един от върховете  b_J, J=1,2,…N  с целта t посредством ориентирано ребро (b_J,t) и за капацитет c(b_J,t) на всяко такова ребро определяме стойността на съответния експеримент. Свързваме посредством ориентирано ребро (a_I,b_J) върха a_I, I=1,2,…M с върха  b_J, J=1,2,…N  тогава и само тогава когато за провеждането на експеримента  b_J е необходим уредът a_I и за капацитета c(a_I,b_J) на всяко такова ребро ще считаме че е безкрайно голям.

Да допуснем, че сме решили задачата за намиране на максимален поток в така получената мрежа и нека F e стойността на намерения максимален поток.  Очевидно F не може да надхвърля сумата S от цените на всичките уреди и приспособления. Стойността на F можем да интерпретираме като максималната част от цената на всички уреди, която би се изплатила от проведени експерименти. При това ще се окаже, че за някои уреди  F(s,a_I)=c(s,a_I), т.е. стойността на съответния уред би се изплатила напълно и значи си струва да се опитаме да закупим този уред. Ако пък  F(s,a_I)<c(s,a_I), тогава стойността на съответния уред не може да  се изплати напълно и значи закупуването на този уред ще намали печалбата. Затова да разгледаме множеството А от тези уреди, за който F(s,a_I)=c(s,a_I). Да образуваме множеството B от всички експерименти, за които необходимите уреди са в множеството A. Оптимално решение на задачата ще бъде подмножеството А’, състоящо се от  всички уреди от А, които са необходими за поне един експеримент от B.  Ако искаме да намерим и печалбата, трябва от  сумата на стойностите на експериментите в B да извадим сумата от цените на закупените уреди от А’. За примера от фиг. 1 стойностите на максималния поток са показани по ребрата на мрежата. (Първата стойност в надписа на всяко ребро е неговия капацитет, а втората стойност е стойността на намерения поток за това ребро.) От нея се вижда, че максимална печалба ще бъде реализирана ако се закупят уредите с номера 1, 2 и 4. При това положение експериментите които могат да се осъществят са 1 и 3 и значи печалбата ще бъде 15.        

В коментара на пета задача от 2000-2001г. се  спряхме на класическия алгоритъм на Ford-Fulkerson. Този алгоритъм в общия случай не е достатъчно бърз. Затова тук ще се спрем на един друг алгоритъм, който се счита за един от най-бързите алгоритми за намиране на максимален поток – preflow-push алгоритъма. За разлика от Ford-Fulkerson, който има “глобален” характер,  preflow-push алгоритъма работи по-скоро локално. За разлика от алгоритъма на Ford-Fulkerson той поддържа характеристика f:VxV->R, наречена preflow, откъдето идва и името му. Тази характеристика се подчинява на симетричното свойство и удовлетворява изискването да не надхвърля капацитета. Да означим с e(u) сумата на потока влизащ във върха u и да наречем тази сума остатъчен поток (забележете, че заради симетричността на f излизащите от u ребра “отнемат” поток от u).

Ще изложим накратко интуитивната идея на preflow-push алгоритъма. Нека си мислим че всеки връх v на мрежата може да се поставят на платформа с височина h(v) (h= 1, 2, ..., 2|V|), като h(s)=|V|, а h(t)=0. Да си мислим също, че всеки връх v на мрежата разполага с резервоар с неограничен обем, които може да поеме целият остатъчен поток e(v), достигнал до този връх. Основни за алгоритъма са следните две операции:

-          push(u,v), където h(u)= h(v)+1. Изпраща поток от u към v с обем равен на min{e(u),c(u,v)};

-          lift(u), като e(u)>0 и за всеки връх v до който би могъл да бъде изпратен поток от u е изпълнено h(u)≤h(v). В резултат височината на u става равна на min{h(v)| за всяко v до който би могъл да бъде изпратен поток от u}+1.

С помощта на така описаните операции могат да се реализират различни стратегии за търсене на максимален поток. Общата идея е да се прилага push докато може, след което да се направи lift и отново да се опитва push. Когато нито една от операциите не е приложима, тогава намереният до момента поток е максимален.  Известни стратегии са lift-to-front и push-relabel. Първата е описана в споменатата вече книга на T. Cormen, Ch. Leiserson и R. Rivest.

В условието на задачата не се изискваше намирането на оптимум, (макар че, както се вижда от коментара по-горе, постигането му не е много трудно). Това даваше възможност на участниците да използват и други алгоритми и идеи. Въпреки това, няма получено решение, което да има стопроцентов резултат. Едната от причините е, че решенията на участниците, които са имплементирали алгоритъм за намиране на максимален поток, са бавни на най-големия тест. Това е често срещано явление, когато се използват готови стандартни библиотеки. Заради тяхната универсалност, те не винаги са най-ефективни. И това го подчертаваме не за първи път. Участниците, пък, които са реализирали своя по-бърза идея, не винаги достигат до най-добрия възможен резултат. Такъв е случаят с победителя в този кръг – Стефан Стефанов от Варна.

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

Supported by Musala Soft Ltd.

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