Pro ∣R∣=1 tak platí minimum, protože je tam jen start za cenu 0
Pomocí belmana dokážu, že vrchol, který přidávám do R je segmentem nejkratší cesty
Jinými slovy, mám nejkratší cestu (s,v) a přidávám vrchol w, protože má ze všech možných cest z v nejmenší cenu. Proto vzniklá cesta (s,w) je opět nejkratší protože neexistují hrany se zápornou váhou.
Dynamické flow
- Můžeme přidat čas
- Chceme kumulovat tok na nodech (např. ropa v tankerech, parkoviště)
- Lze převést zpět na max flow (zavedením duplicitních nodů v různých časech)
Min-cut
Může existovat více ekvivalentních cutů
Množina vrcholů obsahující s ale nikoliv t
Hrany vedoucí z množiny cutu jsou plně sarurované ( flow = u ) a hrany vedoucí do množiny jsou také plně saturované ( flow = l )
Kapacita cutu = maximální flow
Ford-Fulkerson (Max-Flow)
Obecně řečeno nestačí maximalizovat všechny toky hrany, musíme na to jít chytřeji (nechceme např. maximallizovat hranu vedoucí do s) => proto Ford-Fulkerson
Vytvoření proveditelného toku
Pokud jsou všechny lower boundy nulové, neboli ∀e ∈ E(G); l(e) = 0 můžu jít do kroku 2. s initial flow = 0
Pokud nejsou všechny lower-boundy nulové:
Vytvoříme cirkulaci (vytvoříme hranu z t do s s l=0 a u=∞)
Spočítám balance (pozor, tyto balance jsou odlišné od výše zmíněných!) (l vstupních - l výstupních) a snížím hodnoty l a u o l
Přidám nový s’ od kterého povedeme hrany do vrcholů s balancí > 0 s l = 0 a u = balanci
Přidám nový t’ do kterého povedeme hrany z vrcholů s balancí < 0 s l = 0 a u = -balanci
Zapnu max-flow na novém grafu
Výsledné new-flow zadám do starého grafu jako flow = l + new-flow
Inkrementální zlepšování
Nejdříve najdeme cestu od s do t takovou, že každá hrana v cestě není plně saturovaná (je možná použít zpetné hrany)
Této cestě zvýšíme (snížíme v opačných hranách) tok o maximální možné zlepšení (min z možných zlepšení jednotlivých hran cesty)
Opakuji dokud jsem ještě schopen najít zlepšující cestu z s do t
Time complexity:
Celočíselné flow (znamená celočíselné l a u)
obecně - O(|E|2 * U) kde U je maximum z u
Alternativně použijeme algoritmus Floyd-Warshall
Při vytváření augmentované cesty použijeme algoritmus pro nejkratší cestu - O(|E|2 * |V|)
Celočíslenost Ford-Fulkersona
Když všechny kapacity l a u jsou celá čísla (integery), kapacita augmentované cesty γ při běhu Forda-Fulekrsona je rovněž celé číslo
Protože máme nax-flow konečné hodnoty, existuje konečný počet kroků algoritmu
Rovněž z LP formulace můžeme říci, že celočíselnost vyplývá z úplné unimodularity matice incidence grafu G, což je matice A ve formulaci A - x ≤ b.
Feasible Flow with Balances
Zadáno jako (G, l, u, b):
G - orientovaný graf
l - lower bound hran
u - upper bound hran
b - balance vrcholů (suma všech balancí = 0)
Derivát tokové sítě, ale máme více zdrojů a více cílů
Decision problém - ptáme se, jestli lze dosáhnout toku
Tento problém lze polynomiálně redukovat na problém mac flow
Přidáme nový zdroj s’ a spojíme ho s původními zdroji a nastavíme l=u=b (jinými slovy nastavíme lower bound a upper bound na balanci uzlu)
Přidáme společný spotřebič t’ a spojíme ho s původními spotřebiči a nastavíme l-u-b (jinými slovy nastavíme lower bound a upper bound na balanci uzlu)
Pokusíme se vyřešit max-flow.
Existují-li toky pak lze použít zadané balance a rozhodovací úloha má odpověď ano.
Minimum cost flow
Každá hrana má cenu c
Přenesení jedné jednotky po dané hraně nás stojí právě c
Hledáme maximální tok při minimálním costu
Zadáno jako (G, l, u, c, b):
G - orientovaný graf
l - lower bound hran
u - upper bound hran
c - cost hran
b - balance vrcholů (suma všech balancí = 0)
Max flow můžeme polinomiálně redukovat na minimum cost flow
Přidáme cirkulaci = přidáme hranu z t do s, kde u=∞ a l=0 a c=-1
Cenu všech ostatních hran c nastavíme na 0
Balanci všech vrcholů b nastavíme na 0
Maximalizujeme cenu
Shortest path můžeme polynomiálně redukovat na min cost flow
Použijeme LP formulaci min-cost flow
Nastavíme b(s)=1 a b(t)=-1
Pro všechny ostatní (t.j. mimo zdroj a spotřebič) b(v)=0
l(e)=0 a u(e)=∞ pro všechny hrany e
Získáte (primární) LP formulaci problému nejkratší cesty (viz příklad zcela unimodulární matice A v přednášce o ILP) #Tady nemám sebemenší tušení co tohle znamená, lol
Chinese mailman problem můžeme polynomiálně redukovat na min cost flow (#bylo to v testu, tak se na to nevykašlete 🙃)
Listonoš musí zajít na poštu, vzít dopisy a obejít s nimi všechny ulice města a nakonec se vrátit do výchozího bodu – zpět na poštu. Musí přitom urazit minimální vzdálenost.
V grafu, který reprezentuje město, představují hrany grafu ulice a uzly odpovídají křižovatkám. Hrany jsou ohodnoceny kladnými čísly, které odpovídají délce ulic.
Postup:
Nastavíme b(v)=0 pro všechny vrcholy
Nastavíme l(e)=1 a u(e)=∞ pro všechny hrany
Vyřešíme min flow
Existuje pošťákova cesta, která využívá každou hranu přesně jednou (tj. Eulerian walk) iif pokud má každý vrchol stejný indegree a outdegree (tj. Eulerian digraph).
Dopředné hrany budou mít hodnoty u = u - flow a c = c
Zpětné hrany budou mít hodnoty u = flow - l a c = -c
Vyházím hrany s u = 0
Naleznu záporný cyklus (záproný součet cen)
γ = součet cen * min(u) v cyklu
Upravíme flows v původním grafu o γ aby to dávalo smysl (neporušil jsem kirchofa)
Znovu jdu do bodu 2. dokud existuje negativní cyklus v residuálním grafu
Time complexity - O(∣E∣2∗∣V∣∗C∗U) kde U je maximum z u a C maximum z c
Minimum cost multicommodity flow
Přidává různé typy přenášených informací (které nesmíme pomotat)
Každý vrchol má balance jednotlivých typů
Každý vrchol musí splňovat kirchofův zákon pro jednotlivé komodity
Zadáno jako (G, l, u, c, b1…m):
G - orientovaný graf
l - lower bound hran
u - upper bound hran
c - cost hran
b[1..m] - vektor znázorňující balanci pro jednotlivé komodity (v součtu musí dávat 0 přes celý graf a komodity)
Cíl minimalizovat ∑eϵE(G)∑mϵMfm(e)∗c(e)
Párování
Maximum Cardinality Matching Problem
Párování s největším počtem hran (spojení)
Algo - M-alternig Path
Najdeme náhodné párování
Najdeme alternující cestu (cesta na které se střídá nevybraná hrana s vybranou, začíná a končí nevybranou hranou a koncové vrcholy nepatří žádnému párování)
Prohodíme vybrané a nevybrané hrany v cestě
Opakujeme 2-3 dokud neexistuje alternativní cesta
Maximum Cardinality Matching in Bipartite Graphs
Párování s největším počtem hran (spojení) párující vrcholy ze dvou skupin
Lze řešit pomocí max-flow
Minimum Weight Matching in a weighted graph
Takové párování co nám dá nejmenší součet cen na hranách
Minimum Weight Perfect Matching
Takové párování co nám dá nejmenší součet cen na hranách a všechny vrcholy jsou napárované
Známé jako assignment problem
Lze převést na min cost flow podobně jako bipartitní párování
Knapsack
NP-Hard, ale ne moc (existují kvalitní aproximační algoritmy)
Je zadán jako:
n = počet předmětů
ci = cena předmětu
wi = váha předmětu
W = nosnost batohu (nesmí být překročena)
předmět buď vložíme nebo nevložíme do batohu
Maximalizujeme cenu věcí v batohu
Fractional Knapsack problem
-Stejné jako knapsack, ale předměty nemusíme vkládat celé
Řeší: bin packing, contaner loading, 1-D, 2-D, 3-D cutting problem.
O(nlogn) jen znovu seřadím
Algoritmus:
Pokud ∑i=1nwi<W vložíme vše a máme hotvo
Vyřadíme předměty s wi>W
Přeindexujeme předměty podle wici od největšího po nejmenší
Postupně dáváme předměty do batohu dokud se nám tam další předmět nevejde celý
Tento předmě označíme jako h
Do batohu dáme takovou čás h, která se do něj ještě vejde
R-aproximační algoritmus
Takový algoritmus A, který je definován číslem r∈Q pro problém J
Výsledek algoritmu A je maxilmálně r1 hodnoty optima algoritmu J
Pro maximalizaci JA(I)≥r1∗J∗(I)
Pro minimalizaci r∗J∗(I)≥JA(I)
Frekvence “worst case scenaria” není sledována
Knapsack (0/1 Knapsack)
2-Aproximation algorithm
Alespoň r1 optima (kde r=2)
O(n)
Algoritmus:
Pokud ∑i=1nwi<W vložíme vše a máme hotvo
Vyřadíme předměty s wi>W
Přeindexujeme předměty podle wici od největšího po nejmenší
Postupně dáváme předměty do batohu dokud se nám tam další předmět nevejde celý
Tento předmě označíme jako h
vložíme předměty {1,...,h−1} nebo jen {h} na základě toho, co je výhodnější
Důkaz, že r=2
Můžeme vynechat předměty, jejichž w>W
Když ∑i=1nwi<W, tak máme optimální řešení
Protože ∑i=1hci je horním omezením optimální hodnoty, lepší z dvou možných řešení {∑i=1hci} a h je minimálně polovina optimální hodnoty
Lze zmenšit počet sloupců (zrychlit algo) nalezením dělitele t ve tvaru cjˉ=⌊tcj⌋ (pokud se nejedná o společného dělitele snižujeme přesnost řešení)
Aproximační schéma
r=1+ϵ
Mějme zadaný knapsack a ϵ (o kolik jsme ochotni být vzdáleni od optima v procentech)
O(n2∗ϵ1)
Postup:
Spustíme 2-aproximační algoritmus a řešení označíme jako S1
Spočítáme proměnou t=max{1,nϵ∗c(S1)}
Spočítáme cj′=∣tcj∣forj=1,...,n
Spustíme dynamické programování s pozměněnými cenami s upper boundem C=t2c(S1)
Vrátíme vyšší cenu z S1 a S2
TSP
Cesta v grafu přes všechny vrcholy grafu - Hamiltonovská cesta
Spojení posledního a prvního vrcholu - Hamiltonovská kružnice
Reálné problémy TSP: Capacitated Vehicle routing Problem, Time Windows, Pick-up and Delivery.
EHC - existence hamiltonovské kružnice (circuit)
Existuje kružnice, která prochází všemi vrcholy právě jednou?
Neorintovaný graf (obecný)
Rozhodovací problém - NP-Complete
Podobně existence hamiltonovského cyklu - v orientovaném grafu
TSP - traveling salesman problem
Naleznout hamiltonovskou kružnici s minimální váhou
Symetrické TSP - v neorientovaném grafu
Asymetrické TSP - v orientovaném grafu
Optimalizační problém - NP-Hard
Počet hamiltonovských kružnic = 2(n−1)!
Ale nevíme proč je to tak těžký (jakože to neví ani Hanzálek), MSTs je ještě víc
Složitost se pronásobuje konstantou, která souvisí s nějakým parametrem grafu (e.g. součet vah objektů u Knapsacku)
Silně NP-Hard problémy
Neumíme na ně najít pseudopolynomiální algoritmy (e.g. dynamické programování)
Nepomůže nám omezit parametry vstupu polynomem - stále zůstává NP-Hard
Důkaz, že TSP je silně NP-Hard
Mějme:
L=TSP
Lp=TSPsresktricıˊc(e)∈1,2 (t.j. omezení na váhy hran 1 a 2)
Dokazujeme, že i když takto omezíme váhy hran, problém je stále NP hard a proto je silně NP-Hard
Použijeme polynomiální redukci z existence hamiltonovské kružnice
Postup:
Vezmeme neoritovaný graf G s n vrcholy
V tom najdeme libovolnou hamiltonovskou kružnici G′
V grafu G ohodnotíme každou hranu z G′ váhou 1 a ostatní hrany váhou 2
G má hamiltonovskou kružnici iif optimální TSP řešení je rovno n
Obecný r-aproximační algoritmus
Neexistuje n-aproximační algoritmus pro obecné TSP
Důkaz sporem
Uvažujme, že existuje r-aproximační algoritmus A s r≥1
Ukážeme, že s tímto A jsme schopni řešit existenci hamiltonovské kružnice
To by znamenalo, že P=NP
Postup:
Mějme neorientovaný graf G, ve kterém chceme najít hamiltonovskou kružnici
Vytvoříme TSP instanci Kn takovou, že vrcholy jsou totožné a hrany ohodnotíme:
1 pro hrany ∈G
2+(r−1)∗n pro hrany ∈G
Vyřešíme pomocí A
Pokud je optimum v intervalu <n,r∗n>, pak Hamiltonovská kružnice existuje
Pokud je větší, G nemá hamiltonovský cyklus
To by znamenalo, že jsme schopni řešit EHC v polynomiálním čase algortimem A
Metric TSP
Má vlastnost, že platí trojůhelníková nerovnost c(∣AB∣)≤c(∣AC∣)+c(∣CB∣)
Nadále silně NP-hard
Existují aproximační algoritmy
Nemetrickou instanci můžeme pevést na metrickou přičtením největší váhy hrany ke všem hranám
To neporošuje přechozí důkaz, protože nalezené optimum pro transformovaný graf neodpovídá přesně původnímu grafu, protože je k němu přičteno “velké číslo” zatažené transformací
Nearest Neighbor
O(n2)
Heuristika, nikoli aproximační algoritmus
Postup:
Vybereme první vrchol a přeindexujeme na v[1]
Vybereme nejlacinější hranu, která z nás vychází a nejde do vrcholů, ve kterých jsme už byli
Opakujeme bod 2 dokud nemáme všechny vrcholy
Spojíme poslední vrchol s v[1]
Double-tree (metric TSP)
2-aproximační alog
O(n2)
Algoritmus:
Najdeme MST T
Všchny hrany v T zvojíme
V T nalezneme Eulerovský tah L
Z Eulerovského tahu L odebereme vrcholy co jsme už navštívili, ale ponecháme poslední a tím vytvoříme Hamilnovskou kružnici H
∀j∈{i+1,..,4m}:Tj=(ai,0,∞),i=j−m; každý tento task Tj odpovídá elementu I3P
Nejmenší doba čekání
1∣∣∑Cj - easy (seřazené dle pj - SPT shortest processing time first)
1∣∣∑wjCj - easy (seřazené dle wjpj)
1∣rj∣∑Cj - NP-hard
1∣pmtn,rj∣∑Cj - easy (upravené seřazení dle pj)
1∣pmtn,rj∣∑wjCj - NP-hard
1∣dj~∣∑Cj - easy (upravené seřazení dle pj)
1∣dj~∣∑wjCj - NP-hard
1∣prec∣∑Cj - NP-hard
Nejmenší lateness (v β je dj, Lmax může být záporný)
1∣∣Lmax - easy (nejdřívšjší dj první = EDD - earliest due date first)
1∣rj∣Lmax - NP-hard
1∣rj,pj=1∣Lmax - easy (EDD)
1∣pmtn,rj∣Lmax - easy (EDD Horn)
1∣pmtn,rj,dj=dj~∣Lmax - easy (EDD/EDF Horn)
1∣pmtn,prec,rj,dj=dj~∣Lmax - easy (převod na prec a pak EDD/EDF)
Bratley’s Algorithm
1∣rj,dj~∣Cmax
O(n!)
Algoritmus:
Začnu stromovou strukturu s n levely (n=počtu tasků)
Root na levelu 0 je před vložením prvního tasku
Na level 1 zadávám první tasky, na levelu 2 zadávám druhé tásky ze zbytku, atd.
Pravidla pro ukončení větve:
Pokud mezi childy nodu, existuje child, který nedodrží deadline tasku → do nodu se nazanořuji
Jestliže jsem našel node, který dokončil všechny využité tasky před ri všech zbylích tasků, jsem v optimální větvi → stačí projít pouze childy tohoto nodu
Jestliže jsem našel řešení a test optimality říká true → skončím
Pokud moje rozpracované řešení má horší hodnotu než již nalezené řešení → nezanořuji se dál
BRTP
Podmínky:
První úloha v rozvrhu musí začínat na svém release timu
Všechny úlohy běží bez “idlu”
r1≤ri∀i=2...k
Jestliže platí, pak je rozvrh optimální
BRTP není nezbytnou podmínkou optimality!! (tzn. rovrh může být optimální, ačkoli BRTP neplatí)
nejdříve beru tasky T′, ze kterých v precedentím grafu už nic nevychází
taskům T′ nastavím level = pi
vyberu předcházející tásky tásků z T′ a vytvořím nové T′ s těmito tasky
levely tasků T′ nastavím jako level = pi+max(levelsi) kde levelsi jsou levely následovníků
dokud nejsou olevelovány všechny tasky → vracím se do bodu 3
schduling:
do množiny Z vložím tasky, které nemají nedokončené předchůdce (jsou available)
z množiny Z vyberu tasky s max(leveli) do množiny S
všechny tasky z S rozložíme rovnoměrně na zdroje (jeden task nesmí běžet na 2 zdrojích zároveň, ale více úloh se může o čas na zdroji podělit)
pokud mi zbyli zdroje a tásky v Z→ vracím se do bodu 2
spustíme zdroje
zdroje přerušíme jakmile nějaký task na zdroji dožene level jiného tasku nebo se task dopočítá → všechny tásky vyndáme ze zdrojů a vracíme se do bodu 1
Arc consistency - při vztahu z domény xi do xj existuje ke každé možné doménové hodnotě ai∈xi existuje alespoň jedna aj∈xj, které splňuje všechny constraints
CSP je arc consistent pokud všchny hrany jsou arc consistent
algo:
do seznamu S vložíme postupně všechny arcs propojení proměnných dle constraints
ze seznamu S vyjmeme první dvojici proměnných (xi,xj)