Les 6: Onoplosbare problemen?

Onoplosbare problemen?
1 / 15
next
Slide 1: Slide
InformaticaMiddelbare schoolhavoLeerjaar 4

This lesson contains 15 slides, with interactive quiz, text slides and 1 video.

time-iconLesson duration is: 45 min

Items in this lesson

Onoplosbare problemen?

Slide 1 - Slide

Leerdoelen:
  • Na deze les kan je voorbeelden geven van moeilijk oplosbare problemen
  • Kan je voor- en nadelen van brute-forcing en benaderingsalgoritmen benoemen bij moeilijke problemen

Slide 2 - Slide

Onoplosbare problemen?
Welke zakken stop je in je rugzak om zoveel mogelijk waarde mee te kunnen nemen, terwijl je rugzak maar maximaal 12 kilogram kan dragen?
Een handelsreiziger wil alle steden bezoeken, maar wil daarnaast zo weinig mogelijk reizen. Wat is zijn route?

Slide 3 - Slide

het rugzak probleem

Slide 4 - Slide

Je kunt je afvragen welke dozen je in je rugzak moet stoppen zodat er zo veel mogelijk waarde (in euro's) in zit. Dit probleem is beroemd en wordt het rugzakprobleem genoemd. Het is een heel eenvoudig probleem, maar er bestaat geen snel algoritme om het op te lossen. In dit voorbeeld is dat niet zo erg. Want er zijn maar vijf dozen en er mag maar 12 kg mee.

Slide 5 - Slide

Best mogelijke oplossing
  • Bereken per doos de waarde per kg
  • Zet aflopend op waarde/kg neer
  • Pak als eerste de doos met de hoogste waarde per kg
  • Kijk of je de volgende doos er bij kunt hebben, zo niet dan de eerstvolgende. 

Slide 6 - Slide

Correctheid en efficientie
Alle mogelijkheden afgaan
wel correct
Niet efficient
Brute Force Algoritme
Oplossing benaderen
efficient
Niet de beste oplossing
Wiskundige Dantzig bedacht algoritme voor rugzakprobleem:
  1. Bereken voor elke doos de waarde per kilogram
  2. Sorteer de dozen vervolgens op die waarde van groot naar klein
  3. Vul de rugzak in diezelfde volgorde tot het niet meer past

Slide 7 - Slide

Het Chinese Postbodeprobleem
Een postbode moet brieven bezorgen in een bepaalde stad. Hij moet daarbij vertrekken vanuit het postkantoor, alle straten doorlopen om vervolgens weer in het postkantoor te eindigen. Daarbij is het de bedoeling om de totaal afgelegde afstand minimaal te houden. 

Ook strooiwagens in de winter kennen dit probleem, nu niet minimale afstand, maar zo min mogelijk tijd.

Slide 8 - Slide

Slide 9 - Video

Het Chinese postcodeprobleem
"Als er meer dan twee kruispunten met een oneven aantal aangesloten straten zijn, moeten sommige straten meerdere keren worden doorlopen"

Slide 10 - Slide

Slide 11 - Slide

Het Chinese postcodeprobleem
  1. De oneven punten zijn: A, B, F en E
  2. De oneven paren zijn: AF, AB, FE,BE
  3. Het totale gewicht van de enkele graaf (het parcours) is : 2 + 5 + 4 + 6 + 5 + 7 + 10 + 6  + 8 = 53
  4. AF en BE dubbel lopen kost 10 + 9 = 19
    AB en EF dubbel lopen kost 2 + 8 = 10, dit is voordeliger.
  5. We lopen dus AB en FE dubbel.


Slide 12 - Slide


Bij welk van de onderstaande tekeningen is de dubbele weg het meest efficient uitgevoerd?
A
Bij de linker afbeelding
B
Bij de middelste afbeelding
C
Bij de rechter afbeelding

Slide 13 - Quiz

Kan je nu het probleem hieronder oplossen?

Slide 14 - Slide

Slide 15 - Slide