Onoplosbare problemen

Wat is het rugzakprobleem?

• Het probleem dat de rugzak kapot gaat door overbelasting.

• Het probleem wanneer je een inhoud met een zo groot mogelijke waarde wil meenemen maar vast zit aan een limiet van inhoud.

• Het probleem dat je een zo groot mogelijke inhoud wilt meenemen maar je vast zit aan een limiet van waarde.

• Het probleem dat de waarde van de rugzak niet hoog genoeg is waardoor je niet met de rugzak wil lopen.

Bestaat er een algoritme voor het rugzakprobleem.

• Ja, dat het het rugzakalgoritme.

• Nee, dat is er niet.

Hoe heet het algoritme waarbij je alle mogelijkheden bij langsgaat?

• forcebrute-algoritme

• force-algoritme

• brute-algoritme

• bruteforce-algoritme

Wat is volgens Dantzig de beste oplossing voor het rugzakprobleem?

• Waarde berekenen -> van groot naar klein sorteren -> in die volgorde in de rugzak doen.

• Gewoon zo veel mogelijk in je tas doen.

• Waarde berekenen -> van klein naar groot sorteren -> in die volgorde in de rugzak doen.

Wat is het Chinese postbodeprobleem?

• Het probleem dat Chinese postbodes de adressen niet kunnen vinden.

• Het probleem dat Chinese postbodes de kortste route willen lopen, zonden straten dubbel te moeten lopen.

• Het probleem dat Chinese postbodes de langste routes willen lopen, met zo veel mogelijk dubble straten.

• Het probleem dat Chinese postbodes de meest efficiënte route willen lopen, zonder tijd en afstand te verspillen

Welke stelling is juist, bij het Chinese postbodeplobleem.

• Als er meer dan twee kruispunten met een oneven aantal aangesloten straten zijn, moeten alle straten meerdere keren worden doorlopen.

• Als er meer dan twee kruispunten met een oneven aantal aangeslopen straten zijn, hoeft elke straat maar een keer worden doorlopen.

• Als er meer dan twee kruispunten met een oneven aantal aangeslopen straten zijn, moeten sommige straten meerdere keren worden doorlopen.

Welk van deze routes is NIET in één keer te doorlopen, zonder dubbel te lopen?

• 
• 
• 
• 

Welk algoritme lijkt erg veel op een bruteforce-algoritme?

• mergesort

• bubblesort

• quicksort

Waarom is het erg moeilijk een algoritme op te stellen voor het Chinese postbodeprobleem?

• Je moet rekening houden met bijvoorbeeld autowegen.

• Je moet rekening houden met bijvoorbeeld spelende kinderen.

• Je moet rekening houden met overstekend wild.

• Je moet rekening houden met bijvoorbeeld eenrichtingsstraten.

Bij welke is de dubbele het meest efficiënt uitgevoerd?

• 
• 
•