Les 8 - Onoplosbare problemen - over tijdcomplexiteit
Over tijdcomplexiteit
Onoplosbare problemen
Lesduur is: 50 minOnderdelen in deze les
Over tijdcomplexiteit
Onoplosbare problemen
Leerdoel
Aan het eind van deze les kun je uitleggen waarom brute-force bij het rugzakprobleem vastloopt en hoe een benaderingsalgoritme helpt. Ook rangschik je algoritmes op tijdcomplexiteit (Big O) en weet je hoe je $1.000.000 verdient met het P- vs. NP-probleem.
Onoplosbare problemen?
We hebben inmiddels veel algoritmen behandeld, maar niet voor alle problemen is er een perfect algoritme
Hoe zit dat en wat voor problemen zijn dat?
Het rugzakprobleem
Stel...
In je rugzak past maximaal 12 kg.
Je wilt zoveel mogelijk waarde
(in euro’s) meenemen
Welke dozen moet je in je rugzak
stoppen?
1
minute
00
second
Sleep de dozen die samen zoveel mogelijk waarde (in euro's) vormen in de rugzak
1
minute
00
second
Oplossing van het rugzakprobleem
De doos van €12 heeft weliswaar de hoogste waarde, maar als je deze doos kiest, mag er nog maar 1 kilogram in de rugzak. Je kunt dan maximaal €2 aan waarde toevoegen,
voor een totaal van €14.
De combinatie van de lichtere dozen
(€2 + €2 + €3 + €8 = €15) is meer waard.
Wat voor tijdscomplexiteit heeft dit probleem?
Om het rugzakprobleem perfect op te lossen is een brute-force-algoritme nodig.
Voor elk voorwerp heb je exact 2 keuzes:
Een doos wel meenemen (1)
Een doos niet meenemen (0)
Het rugzakprobleem kent dan O(2ⁿ)
Aantal combinaties bij n voorwerpen:
1 voorwerp: 2 mogelijkheden
2 voorwerpen: 2 × 2 = 4 mogelijkheden
3 voorwerpen: 2 × 2 × 2 = 8 mogelijkheden
n voorwerpen: 2 × 2 × ... × 2 = 2ⁿ mogelijkheden
Exponentiële groei: Elk extra voorwerp verdubbelt het werk voor de computer! Bij 30 dozen zijn dat al meer dan 1 miljard (2³⁰) combinaties.
Correctheid of efficiëntie?
Een algoritme maken dat alle mogelijkheden langsgaat:
Heet dus een brute-forcealgoritme
Het levert altijd een correcte oplossing
Maar het is niet efficiënt
Een algoritme maken dat zo dicht mogelijk in de buurt van de oplossing probeert te komen. Zo’n algoritme is wel efficiënt, maar niet (helemaal) correct
Het rugzakprobleem in de praktijk
Het rugzakprobleem komt in de praktijk vaak voor, bijvoorbeeld bij het laden van een vrachtwagen
Of wanneer jij bepaalt waaraan je je zuur verdiende geld uitgeeft
Bij veel voorwerpen bestaat er dus geen snel
algoritme dat dit probleem kan oplossen
Wat is er dan wel mogelijk?
Je kent drie sorteeralgoritmen: bubble sort, merge sort en quicksort. Welke van de drie lijkt erg veel op een bruteforce-algoritme?
Bubble sort
Merge sort
Quicksort
Geen van drieë
Bruteforce sorteeralgoritme
Bubble sort doorloopt steeds de hele lijst en verwisselt eventuele verkeerde combinaties van twee getallen, tot die er niet meer zijn. Dat lijkt erg op het langslopen van alle mogelijkheden, wat een bruteforce-algoritme doet.
Vraag: de beste route
Een vrachtwagen moet spullen bezorgen in Amsterdam, Zwolle en Assen. De vrachtwagen vertrekt vanuit Utrecht en gaat eerst naar Amsterdam. De chauffeur kan voor die rit kiezen uit vier routes. Van Amsterdam naar Zwolle zijn er vijf routes mogelijk. En van Zwolle naar Assen ook vijf routes. Voor de terugreis van Assen naar Utrecht zijn er zes mogelijke routes. Om de beste route te bepalen voor de gehele reis gebruiken we een bruteforce-algoritme.
Hoeveel mogelijke routes moet het algoritme onderzoeken?
30
second
Hoeveel mogelijke routes moet het algoritme onderzoeken om de beste route te vinden?
Antwoord: de beste route
4 * 5 * 5 * 6 = 600 mogelijke routes
Correctheid en efficiëntie
Als het probleem te groot is, werkt bruteforcing niet meer omdat het teveel tijd kost:
Rugzakprobleem met 30 verschillende dozen -> meer dan 2 ^ 30 = 1 miljard mogelijkheden!
Mogelijke benaderingsalgoritmen zijn:
Het probleem vereenvoudigen
Een willekeurige oplossing kiezen, die stapsgewijs verbeteren tot een acceptabele oplossing is gevonden
Een bepaalde tijd allerlei verschillende oplossingen uitrekenen, daarna stoppen en de beste uitkiezen
Benaderingsalgoritme van Dantzig (1957)
Gemaakt door de Amerikaanse wiskundige
George Dantzig (1914 – 2005).
Zijn benaderingsalgoritme voor het rugzakprobleem:
Bereken voor elke doos de waarde per kilogram.
Sorteer de dozen vervolgens op die waarde van
groot naar klein.Vul de rugzak in diezelfde volgorde tot het niet meer past.
Het rugzakprobleem - deel 2
In je rugzak past maximaal 12 kg.
Je wilt zoveel mogelijk waarde
(in euro’s) meenemen
Voer het rugzakalgoritme van Dantzig
uit voor deze rugzak en dozen.
Vindt het algoritme de beste oplossing?
Het rugzakprobleem - deel 2
In je rugzak past maximaal 12 kg.
Je wilt zoveel mogelijk waarde
(in euro’s) meenemen
Bereken voor elke doos de waarde
per kilogram.Sorteer de dozen vervolgens op die waarde
van groot naar klein.Vul de rugzak in diezelfde volgorde tot het
niet meer past.
2
minute
00
second
Vindt het algoritme de beste oplossing?
Ja
Nee
Dat valt niet te bepalen
Het rugzakprobleem - deel 2 - uitwerking
1. Reken waarde per kilogram uit:
2. Sorteer op waarde per kilogram:
Het rugzakprobleem - deel 2 - analyse
Stop je deze lijst op volgorde in de rugtas, dan moet je bij doos 2 stoppen, omdat je dan al 0,5 + 3 + 1 + 2 = 6,5 kg in de rugtas hebt gestopt, en doos 5 van 11 kg past er niet meer bij.
Deze oplossing is hetzelfde als de beste oplossing die je in de vorige paragraaf vond, dus in dit geval heeft het algoritme inderdaad de beste oplossing gevonden. Dit is bij dit algoritme echter niet gegarandeerd.
Het rugzakprobleem - deel 3
Voer het algoritme van Dantzig uit voor deze
dozen. Het maximumgewicht van 12 kg
blijft hetzelfde.
Bekijk nu de volgende dozen:
Doos 1: €15, 9 kg
Doos 2: €8, 6 kg
Doos 3: €9, 6 kg
2
minute
00
second
Vindt het algoritme de beste oplossing?
Ja
Nee
Dat valt niet te bepalen
Het rugzakprobleem - deel 3 - uitwerking
1. Reken waarde per kilogram uit:
2. Sorteer op waarde per kilogram:
Het rugzakprobleem - deel 3 - analyse
Stop je deze lijst op volgorde in de rugtas, dan moet je direct na doos 1 stoppen, omdat er dan al 9 kg in de rugzak zit, en er geen andere doos meer bij past. Er zit dan voor €15 in de rugzak.
De beste oplossing is om doos 2 en 3 in de rugzak te stoppen, voor een totaal van €17.
In dit geval heeft het algoritme helaas niet de beste oplossing gevonden.
Complexiteitsdiagram
Big O, ook wel Big O-notatie genoemd, vertegenwoordigt de worstcase-complexiteit van een algoritme.
Big O-notatie meet de efficiëntie en prestaties van een algoritme met behulp van tijd- en ruimtecomplexiteit.
Soorten tijdcomplexiteit
Van sneller naar langzamer:
Constant: O(1)
Logaritmisch: O(log n)
Lineair: O(n)
Lineair Logaritmisch: O(n log n)
Kwadratisch: O(n^2)
Exponentieel: O(2^n)
Factorieel: O(n!)
Soorten tijdscomplexiteit (prestatie)
n = aantal elementen
O(1) - Excellent / Best
O(log n) - Goed
O(n) - Redelijk
O(n log n) - Slecht
O(n^2), O(2^n) and O(n!) - Verschrikkelijk
Behandelde algoritmes
Het gaat dus om worst case.
O(log n) - Slim tellen, binair zoeken
O(n) - Lineair zoeken, doolhoven (BFS en DFS)
O(n log n) - Merge sort, rugzak-probleem (Dantzig), modderdorp (MST)
O(n^2) - Bubble sort
O(2^n) - Rugzakprobleem
O(n!) - BogoSort
Onoplosbare problemen?
Zijn er problemen die ook voor een computer moeilijk
zijn om op te lossen?
Welk van onderstaande problemen bevindt zich in de NP-klasse?
Het oplossen van een doolhof
Het sorteren van een lijst elementen
Het oplossen van een sodoku
Het uitvoeren van een vermenigvuldiging
Welk probleem bevindt zich in de NP-klasse?
De P-klasse omvat beslissingsproblemen waarvoor er een algoritme bestaat dat het probleem kan oplossen in polynomiale tijd.
NP omvat beslissingsproblemen waarvoor een oplossing kan worden geverifieerd in polynomiale tijd. Dit betekent dat als je een mogelijke oplossing voor het probleem hebt, je snel kunt controleren of deze oplossing correct is.
Dus het oplossen van een sudoku is een NP-probleem.
Leerdoel gehaald?
Aan het eind van deze les kun je uitleggen waarom brute-force bij het rugzakprobleem vastloopt en hoe een benaderingsalgoritme helpt. Ook rangschik je algoritmes op tijdcomplexiteit (Big O) en weet je hoe je $1.000.000 verdient met het P- vs. NP-probleem.
Doornemen en maken
Informatica Baas -> Grondslagen -> Algoritmen
2.8 Onoplosbare Problemen & rugzakalgoritmes
