Проблем затворења

С Википедије, слободне енциклопедије

У теорији графова и комбинаторној оптимизацији, затворење усмереног графа је скуп чворова без излазних грана. То значи, да граф не може да има гране које полазе из области затворења а завршавају се изван те области. Проблем затворења је поступак проналажења затворења са максималном или минималном тежином чворова у усмереном графу са тежинским чворовима. [1][2] Проблем може бити решен у полиномијалном времену свођењем на решавање проблема максималног протока. Може се користити за моделовање различитих апликативних проблема при бирању оптималног подскупа извршних задатака, уз постојање зависности између парова задатака, као што је на пример поступак вађења руде у руднику са отвореним копом.

Алгоритми[уреди | уреди извор]

Сажимање - кондензација[уреди | уреди извор]

Затворење максималне тежине датог графа G је исто што и комплемент затворење минималне тежине транспонованог графа G, стога су оба проблема еквивалентна по рачунској сложености.

Ако два чвора графа припадају истој чврсто повезаној компоненти, они мора да се понашају исто у односу на сва своја затворења: није могуће да затворење садржи један чвор а други не. Зато се улазни граф за проблем затворења може заменити својим сажетком, у коме је свака чврсто повезана компонента замењена појединачним чвором. Сажетак је увек усмерени ациклички граф.

Свођење на максимални проток[уреди | уреди извор]

Пикар 1976 је показао [2][3] да је затворење са максималном тежином могуће добити из G решавањем проблема максималног протока на графу H конструисаног додавањем на граф G два додатна чвора s и t. За сваки чвор v са позитивном тежином у G, увећани граф H садржи грану од чвора s до v са капацитетом једнаким тежини v, а за сваки чвор v са негативном тежином у G, увећани граф H садржи грану од чвора v до t чији је капацитет негативна тежина од v. Свим гранама у G су дати бесконачни капацитети у H.[1]

Минимални одсечак који одваја s од t на овом графу не може да има гране од G које су директно усмерене дуж одсечка: одсечак са таквом граном би имао бесконачни капацитет и не би био минимум. Зато скуп чворова на истој страни одсечка као s аутоматски формира затворење C. Капацитет одсечка је једнак тежини свих ненегативних чворова умањено за тежину чворова у C, који је минимизован када је тежина у C-у максимална. Са максимални проток - минимални одсечак теоремом, решавањем проблема максималног протока, може да се изведе минимални одсечак и оптимално затворење.[1]

Алтернативни алгоритми[уреди | уреди извор]

Алтернативни алгоритми за проблем максималног затворења који не израчунвају токове су такође проучавани.[4][5][6] Њихово време извршења је слично времену најбржих познатих алгоритама протока.[4]

Примене[уреди | уреди извор]

Рудници са отвореним копом[уреди | уреди извор]

Површински коп рудника може бити моделиран као скуп блокова материјала који се могу уклонити само ако су уклоњени сви блокови директно изнад њих. Блок има укупну вредност, која је једнака вредности минерала који се могу издвојити из њега, умањену за трошкове издвајања минерала и вађења блока; у неким случајевима, блок нема вредност али ипак мора бити уклоњен да би се стигло до следећих блокова, том блоку се додељује негативна вредност.

Може се дефинисати ацикличка мрежа која има чворове који одговарају блоковима материјала, са гранама сваког блока које повезују тај блок са блоковима изнад њега који пре њега морају да се уклоне. Тежина сваког чвора ове мреже одговара укупној вредности блока. Најпрофитабилнији план ископавања је могуће добити проналажењем затворења са максималном тежином, а затим треба формирати тополошки редослед блокова тог затворења.[1][5][7]

Војни системи нишањења[уреди | уреди извор]

У војним операцијама, мете високе вредности као што су командни центри, су често заштићени вишеслојним системима одбране, који могу заузврат бити заштићени другим системима. Да би се погодила мета, сви системи одбране морају прво бити уклоњени, тако да оригинална мета постаје секундарна мета. На сваку мету треба усмерити одређену количину средстава да би напад био успешан. Оптимални скуп циљева за напад, да би се добила највиша вредност поготка, у односу на утрошене ресурсе, може да се моделира као проблем за затворење графа.[1][8]

Планирање мреже за доставу робе[уреди | уреди извор]

Проблем планирања система доставе робе може да се моделира мрежом у којој чворови представљају градове а (неусмерене) гране представљају руте за потенцијалне испоруке терета између два грда. Свака рута може да доноси известан приход, али се може користити само ако су складишта за терет саграђена на оба краја руте, уз одређене трошкове. Проблем дизајнирања мреже која максимизира разлику између профита и трошкова може се решити као проблем затворења, тако што би се свака неусмерена грана поделила на две усмерене гране, обе усмерене изван у односу на тачку поделе. Тежина сваке тачке поделе је позитиван број, тј. профит одговарајуће руте, а тежина оригиналног чвора графа је негативан број, тј. трошкови градње складишта у том одговарајућем граду.[1][9] Заједно са рудницима са отвореним копом, ово је био један од оригиналних мотивационих апликација за проучавање проблема затворења; 1970. је проучаван у два независна објављена рада у истом издању и истом часопису од стране Ј.М.В. Риса и Мишела Белинског.[9][10][11]

Распоређивање послова[уреди | уреди извор]

Сидни 1975 и Лавлер 1978 описују примену проблема затворења на примеру распореда послова у продавници где је дат скуп задатака које треба распоредити за извршење, на начин један по један. Сваком задатку придружена су два броја: тежина или приоритет, и време обраде односно време потребно за извршење задатка. Поред тога, задаци имају ограничења првенства: одређени задаци се морају извршити пре других. Ова ограничења приоритета могу се описати помоћу усмереног ацикличног графа G у коме гране између два задатка указују да први задатак мора бити извршен пре другог задатка. Циљ је да се изабере редослед који је у складу са ограничењима (тополошки редослед од G) који минимизира укупно тежинско време извршења задатка.[12][13]

Иако је Лавлер показао да је проблем заказивања послова НПНП-комплетан у целини, Сидни је описао метод разчлањивања (декомпозиције) који помаже у решавању проблема сводећи га на неколико мањих проблема истог типа. Конкретно, ако је S подскуп од задатака који (међу свим подскуповима) има највећу могућу размеру између укупне тежине и укупног времена обраде, и поред тога S је минималан у односу на све скупове са истом размером, па онда постоји оптимални распоред у којем се сви задаци у S обављају пре свих других задатака. Докле год S није комплетан скуп задатака, ова подела задатака дели проблем распоређивања послова у два мања проблема, један распоређује S а други распоређује преостале задатке.[12] Иако је S затворење (за граф са обрнутим гранама од G) проблем проналажења S није баш прави проблем затворења са максималном тежином јер је вредност S размера а не сума тежина. Ипак, Лавлер је показао да се S може наћи у полиномијалном времену помоћу алгоритма за бинарно претраживање у коме сваки степен претраживања користи случај проблема затворења као подпрограм.[13]

Референце[уреди | уреди извор]

  1. ^ а б в г д ђ Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), „19.2 Maximum weight closure of a graph”, Network flows, Englewood Cliffs, NJ: Prentice Hall Inc., стр. 719—724, ISBN 978-0-13-617549-0, MR 1205775 
  2. ^ а б Cook, William J.; Cunningham, William H.; Pulleyblank, William R.; Schrijver, Alexander (2011), „Optimal closure in a digraph”, Combinatorial Optimization, Wiley Series in Discrete Mathematics and Optimization, 33, John Wiley & Sons, стр. 49—50, ISBN 9781118031391 
  3. ^ Picard, Jean-Claude (1976), „Maximal closure of a graph and applications to combinatorial problems”, Management Science, 22 (11): 1268—1272, MR 0403596, doi:10.1287/mnsc.22.11.1268 
  4. ^ а б Hochbaum, Dorit S. (2001), „A new-old algorithm for minimum-cut and maximum-flow in closure graphs”, Networks, 37 (4): 171—193, MR 1837196, doi:10.1002/net.1012 
  5. ^ а б Lerchs, H.; Grossmann, I. F. (1965), „Optimum design of open-pit mines”, Transactions of the Canadian Institute of Mining and Metallurgy, 68: 17—24 . As cited by Hochbaum 2001
  6. ^ Faaland, Bruce; Kim, Kiseog; Schmitt, Tom (1990), „A new algorithm for computing the maximal closure of a graph”, Management Science, 36 (3): 315—331, doi:10.1287/mnsc.36.3.315 
  7. ^ Johnson, T. B. (1968), Optimum pit mine production scheduling, Technical Report, University of California, Berkeley, CA . As cited by Ahuja, Magnanti & Orlin 1993
  8. ^ Orlin, D. (1987), „Optimal weapons allocation against layered defenses”, Naval Research Logistics Quarterly, 34: 605—617, doi:10.1002/1520-6750(198710)34:5<605::aid-nav3220340502>3.0.co;2-l . As cited by Ahuja, Magnanti & Orlin 1993
  9. ^ а б Hochbaum, Dorit (2004), „50th Anniversary Article: Selection, Provisioning, Shared Fixed Costs, Maximum Closure, and Implications on Algorithmic Methods Today”, Management Science, 50 (6): 709—723, doi:10.1287/mnsc.1040.0242 
  10. ^ Rhys, J. M. W. (1970), „A selection problem of shared fixed costs and network flows”, Management Science, 17 (3): 200—207, doi:10.1287/mnsc.17.3.200 
  11. ^ Balinski, M. L. (1970), „On a selection problem”, Management Science, 17 (3): 230—231, doi:10.1287/mnsc.17.3.230 
  12. ^ а б Sidney, Jeffrey B. (1975), „Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs”, Operations Research, 23 (2): 283—298, doi:10.1287/opre.23.2.283 
  13. ^ а б Lawler, E. L. (1978), „Sequencing jobs to minimize total weighted completion time subject to precedence constraints”, Ann. Discrete Math., 2: 75—90, MR 0495156, doi:10.1016/S0167-5060(08)70323-6 
Преузето из „https://sr.wikipedia.org/w/index.php?title=Проблем_затворења&oldid=26983079”