Les 6: Onoplosbare problemen?

• Informatica
• Middelbare school
• havo
• Leerjaar 4

Onoplosbare problemen?

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
  

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?

het rugzak probleem

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.

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. 

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
   

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.

Het Chinese postcodeprobleem

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

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.

Bij welk van de onderstaande tekeningen is de dubbele weg het meest efficient uitgevoerd?

1. Bij de linker afbeelding
2. Bij de middelste afbeelding
3. Bij de rechter afbeelding

Kan je nu het probleem hieronder oplossen?