La oss se på skattekistene våre igjen. Hvis A sin nøkkel er i B kan vi redusere “åpne A” til “åpne B”
Kompletthet: Universalnøkkel! $X \leqslant C$ for alle $X$
At sertifikatet for ja-svar kan verifiseres i polynomisk tid
som mapper instaner av $L´$ til instanser av $L$
Dette er altså reduksjonen fra $L´$ til $L$, som viser $L´\leqslant_p L$
for alle $x \in \{0,1\}^{⋆}$
Vi må sørge for at vi får samme svar for $f(x)$
![prosess][../prosess]
Hva slags objekt er en instans? En mengde? En sekvens? En graf? Består den av flere deler, som for eksempel en graf og en vektfunksjon? Stilles det spesielle krav for at en instans skal være gyldig?
Hva slags objekt er resultatet? Har vi et søkeproblem, beslutningsproblem eller optimeringsproblem? Dersom vi har et søkeproblem: Hva er søkerommet?
For søkeproblemer: Hvilke krav stilles det til objektene vi leter etter? For optimering: Hva er løsningsrommet og mulighetsområdet, og hva er målfunksjonen? For beslutningsproblemer: Hva er spørsmålet?
Må den ha en bestemt verste, gjennomsnittlig eller amortisert kjøretid? Kan den kun bruke bestemte operasjoner? Er minnet begrenset? Kan den være randomisert?
Skal det være en øvre eller nedre grense for kjøretid? Eller, vise at et problem er NP-komplett?
Kan du redusere til et eksiterende problem som har de egenskapene du trenger, f.eks. som kan løses like effektivt? Husk å bevare nødvendig egenskaper i reduksjonen.
Plassér probleminstansen i en familie med flere instanser som beskrives av et sett med parametre eller egenskaper, som for eskempel størrelse. Om mulig, del problemet opp mer.
Kanskje det passer i et rammeverk for algoritme design?
Kan du redusere fra et eksisterende problem som er f.eks. like vanskelig å løse effektivt?
Du kan la løsningen for et delproblem være avhengig av at andre delproblemer er løst allerede, men du kan ikke ha uendelige avhengighetskjeder! Alle andre relasjoner fungerer.
Hvis du skal løse et problem i polynomisk tid, sørg for at reduksjonen har polynomisk tid!
Du vil dekke ferievakter ved en klinikk, og må ha minst én lege på vakt hver dag. Du vet hvem som kan når, men hver lege skal maks stille 1 dag per ferieperiode og maks $c$ dager totalt
Ønsker å ha minst én lege $(d)$ på vakt hver feriedag $(f)$ Kan gjøres omtrent som matching (hvem er tilgjengelig når?) …men hver lege kan jobbe et visst antall $(c)$ feriedager Hva om man maksimalt skal jobbe (f.eks.) én dag per ferie? Vi kan innføre én node per lege/ferie-kombinasjon Disse nodene “distribuerer” antall dager en lege kan jobbe Hver slik grupperings-node har en inn-kant med kap. (f.eks.) 1
Da har vi løst problemet! (Vi ser at i dette eksempelet så finnes det ingen løsning! 😛)
Etter et bankran kan politiet sette opp et gitt antall veisperringer og vil stanse forbryterne om mulig. Du har kart over veinettet og får oppgitt makshastigheten til forbryterne, hvor og når forbrytelsen skjedde og når veisperringene kan være på plass. Hvor bør de settes opp?
Vi sikter mot minimalt snitt, der kantene har kapasitet 1 Vi slår sammen mangedoble kanter og legger sammen kapasiteter Koble ytterste noder til $t$, og vi har løst problemet!
Simsallabim!
En handelsreisende skal besøke et sett med byer. Hver by skal besøkes nøyaktig én gang, og handelsreisen skal være så kort som mulig
Dette er TCP problemet
TSP
I TDT4125 Algoritmekonstruksjon lærer du mer avanserte designmetoder, som bl.a. går ut over det å finne eksakte løsninger i polynomisk tid. Vi jobber med NP-harde problemer, onlineproblemer approksimasjonsalgoritmer, parametriserte algoritmer, og mye mer!
Det finnes programvare som løser lineære optimeringsproblemer, helt generelt! Om vi krever heltallsløsninger er det NP- hardt, men de fungerer overraskende bra i praksis likevel.
using JuMP, Cbc
using JuMP: dot
function knapsack(n, w, v, W)
m = model(solver=CbcSolver())
@variable m x[1:n] Bin
@objective m Max dot(x, v)
@constraint m W >= dot(x, W)
solve(m)
getvalue(x)
end
x er spesielle JuMP -variable; getvalue(x) gir oss vanlige verdier