Stängningsproblem
I grafteori och kombinatorisk optimering är en stängning av en riktad graf en uppsättning av hörn C , så att inga kanter lämnar C. Stängningsproblemet är uppgiften att hitta maxvikts- eller minimumviktsförslutningen i en vertexvägd riktad graf . Det kan lösas i polynomtid med en reduktion till maximalt flödesproblem . Den kan användas för att modellera olika applikationsproblem för att välja en optimal delmängd av uppgifter att utföra, med beroenden mellan par av uppgifter, ett exempel är i dagbrottsbrytning .
Algoritmer
Kondensation
Maximalviktsstängningen för en given graf G är densamma som komplementet till minimiviktsslutningen på transponeringsgrafen för G , så de två problemen är ekvivalenta i beräkningskomplexitet. Om två hörn av grafen tillhör samma starkt sammankopplade komponent måste de bete sig likadant som varandra med avseende på alla stängningar: det är inte möjligt för en stängning att innehålla en vertex utan att innehålla den andra. Av denna anledning kan ingångsgrafen till ett stängningsproblem ersättas av dess kondensation , där varje starkt ansluten komponent ersätts av en enda vertex. Kondensationen är alltid en riktad acyklisk graf .
Reduktion till maximalt flöde
Som Picard (1976) visade kan en stängning med maximal vikt erhållas från G genom att lösa ett maximalt flödesproblem på en graf H konstruerad från G genom att lägga till två ytterligare hörn s och t . För varje vertex v med positiv vikt i G innehåller den förstärkta grafen H en kant från s till v med kapacitet lika med vikten av v , och för varje vertex v med negativ vikt i G innehåller den utökade grafen H en kant från v till t vars kapacitet är negationen av vikten av v . Alla kanter i G ges oändlig kapacitet i H .
Ett minimalt snitt som skiljer s från t i denna graf kan inte ha några kanter av G som passerar i riktning framåt över snittet: ett snitt med en sådan kant skulle ha oändlig kapacitet och skulle inte vara minimum. Därför bildar uppsättningen av hörn på samma sida av snittet som s automatiskt en förslutning C . Kapaciteten hos snittet är lika med vikten av alla toppvikt med positiv vikt minus vikten av hörnen i C , vilket minimeras när vikten av C är maximerad. Genom max-flöde min-cut-satsen kan ett minimum cut, och den optimala förslutningen härledd från det, hittas genom att lösa ett maximalt flödesproblem.
Alternativa algoritmer
Alternativa algoritmer för maximal stängningsproblem som inte beräknar flöden har också studerats. Deras körtid liknar den för de snabbaste kända flödesalgoritmerna.
Ansökningar
Dagbrottsbrytning
En dagbrottsgruva kan modelleras som en uppsättning materialblock som kan tas bort genom att bryta den när alla block direkt ovanför den har tagits bort. Ett block har ett totalt värde som är lika med värdet av de mineraler som kan utvinnas från det minus kostnaden för avlägsnande och utvinning; i vissa fall har ett block inget extraktionsvärde men måste ändå tas bort för att nå andra block, vilket ger det ett negativt värde. Man kan definiera ett acykliskt nätverk som har blocken i en gruva som hörn, med en kant från varje block till blocken ovanför det som måste tas bort tidigare än det. Vikten av varje vertex i detta nätverk är det totala värdet av dess block, och den mest lönsamma planen för gruvdrift kan bestämmas genom att hitta en maximal viktförslutning och sedan bilda en topologisk ordning av blocken i denna förslutning.
Militär inriktning
I militära operationer skyddas högvärdiga mål som ledningscentraler ofta av lager av försvarssystem, som i sin tur kan skyddas av andra system. För att nå ett mål måste alla dess försvar tas ner, vilket gör det till ett sekundärt mål. Varje mål behöver en viss mängd resurser för att tilldelas det för att kunna utföra en framgångsrik attack. Den optimala uppsättningen av mål att attackera, för att få ut det mesta värdet för de resurser som förbrukas, kan modelleras som ett stängningsproblem.
Design av transportnätverk
Problemet med att planera ett fraktleveranssystem kan modelleras av ett nätverk där hörnen representerar städer och de (oriktade) kanterna representerar potentiella fraktleveransrutter mellan par av städer. Varje rutt kan uppnå en viss vinst, men kan endast användas om godsdepåer byggs i båda dess ändar, med en viss kostnad. Problemet med att utforma ett nätverk som maximerar skillnaden mellan vinsten och kostnaderna kan lösas som ett stängningsproblem, genom att dela upp varje oriktad kant i två riktade kanter, båda riktade utåt från indelningspunkten. Vikten av varje indelningspunkt är ett positivt tal, vinsten för motsvarande rutt, och vikten av varje original grafvertex är ett negativt tal, kostnaden för att bygga en depå i den staden. Tillsammans med dagbrottsbrytning var detta en av de ursprungliga motiverande ansökningarna för att studera förslutningsproblemet; den studerades ursprungligen 1970, i två oberoende tidningar publicerade i samma nummer av samma tidskrift av JMW Rhys och Michel Balinski .
Jobbschemaläggning
Sidney (1975) och Lawler (1978) beskriver en tillämpning av stängningsproblemet på en version av schemaläggning av jobb där man får en samling uppgifter som ska schemaläggas att utföras, en i taget. Varje uppgift har två siffror kopplade till sig: en vikt eller prioritet och en bearbetningstid, den tid det tar att utföra den uppgiften. Dessutom har uppgifterna prioritetsbegränsningar: vissa uppgifter måste utföras före andra. Dessa prioritetsbegränsningar kan beskrivas av en riktad acyklisk graf G där en kant från en uppgift till en annan indikerar att den första uppgiften måste utföras tidigare än den andra. Målet är att välja en ordning som överensstämmer med dessa begränsningar (en topologisk ordning av G ) som minimerar den totala viktade slutförandetiden för uppgifterna.
Även om (som Lawler visar) detta schemaläggningsproblem är NP-komplett i allmänhet, beskriver Sidney en nedbrytningsmetod som kan hjälpa till att lösa problemet genom att reducera det till flera mindre problem av samma typ. I synnerhet, om S är en delmängd av uppgifterna som (bland alla delmängder) har det största möjliga förhållandet mellan sin totala vikt och sin totala bearbetningstid, och dessutom S är minimal bland alla uppsättningar med samma kvot, så finns det en optimalt schema där alla uppgifter i S utförs före alla andra uppgifter. Så länge S inte är hela uppsättningen av uppgifter, delar denna uppdelning av uppgifterna upp schemaläggningsproblemet i två mindre problem, ett med schemaläggning av S och ett med schemaläggning av de återstående uppgifterna. Även om S är en stängning (för en graf med omvända kanter från G ) är problemet med att hitta S inte exakt ett problem med maximal viktförslutning, eftersom värdet på S är ett förhållande snarare än en summa av vikter. Icke desto mindre visar Lawler att S kan hittas i polynomtid av en binär sökalgoritm där varje steg i sökningen använder en instans av stängningsproblemet som en subrutin.