Opgave 1: Opvarmning - 3 byer

Hvad er de indlysende korteste veje rundt mellem de tre byer A, B og C?

Hvormange kombinationer af ruter, hvor de tre byer besøges én gang hver findes der?

Hvordan kan denne udfordring løses med brute force?

Hvordan kan den løses med nærmeste nabo-metoden?

Opgave 2: 4 byer

Hvor mange rutekombinationer findes der mellem byerne A, B, C og D? Og hvordan kan dette beregnes?

Hvilken rute synes du ved første øjekast virker som den mest optimale (den korteste)?

Find alle de mulige ruters længde (brute force) og afgør, hvilke(n) rute(r) der er kortest.

Vælg på skift A, B, C og D som startby og benyt nærmeste nabo-metoden til at finde de fire ruteafstande. Hvilke(n) af byerne er gode som startbyer, hvis man ønsker kortest mulig rute.

Sammenlign brute force-løsningen med nærmeste nabo-løsningen - hvilke fordele har den ene fremfor den anden? Er der ligheder i løsningerne?

Opgave 3: 5 byer

Arbejdet med denne opgave bør være i en gruppe, så det slaviske arbejde med brute force-metoden kan deles ud på gruppens medlemmer.

Hvor mange rutekombinationer findes der mellem byerne A, B, C, D og E? Og hvordan kan dette beregnes?

Hvilken rute synes du ved første øjekast virker som den mest optimale (den korteste)?

Find alle de mulige ruters længde (brute force) og afgør, hvilke(n) rute(r) der er kortest.

Vælg på skift A, B, C, D og E som startby og benyt nærmeste nabo-metoden til at finde de fire ruteafstande. Hvilke(n) af byerne er gode som startbyer, hvis man ønsker kortest mulig rute.

Sammenlign brute force-løsningen med nærmeste nabo-løsningen - hvilke fordele har den ene fremfor den anden? Er der ligheder i løsningerne?

Opgave 4: Undersøg scenarier med 4 byer

Lav en fil i Geogebra magen til billedet her, hvor du selv kan flytte på byerne A, B, C og D. Husk at sætte afrundede længder på linjestykkerne.

Find en by-formation, hvor metoden nærmeste nabo-metoden med start i A giver den korteste rute.

Find en by-formation, hvor nærmeste nabo-metoden med start i A ikke giver den korteste rute.

Kan der findes en by-formation, hvor nærmeste nabo-metoden med start i A faktisk giver den længste rute rundt mellem de 4 byer?

Undersøg scenarier som det til højre for her, hvor den ene by ligger inde i den trekant som forbinder de tre andre byer.

Kan der siges noget generelt om, hvorvidt det er en fordel at starte i midterbyen, eller om det er en ulempe? Eller kommer det an på de indbyrdes afstande?

Se på by-formationen til højre her. Løs den med brute force-metoden og find alle de mulige ruters længde.

Hvad kan man generelt sige, om de ruter, der er kortest at gå?

Lav selv en by-formation til din makker, og lav nogle arbejdsspørgsmål til. Fx. "Hvor mange veje kan du vælge mellem, hvis du ikke må gå mellem A og B?"

Opgave 5: Flere byer - hvad så?

Hvis traveling salesman problemet gradvist udvides med flere byer, ændres antallet af mulige rutekombinationer også. Overvej følgende spørgsmål:

Hvordan beregnes antallet af mulige rutekombinationer ved hhv. 6, 7, 8, 9 og 10 byer?

Hvor beregnes det ved n byer?

Hvilken opgave står man overfor, hvis man med brute force vil finde den korteste rute mellem 10 byer?

Sammenlign brute force-metoden med nærmeste nabo-metoden i tilfældet hvor by-formationen består af 10 byer?

Opgave 6: Optimering - 4 byer - men med udfordringer

De 4 byer skal besøges netop én gang. Du må selv vælge startbyen.

Hvor mange forskellige ruter findes der? Og hvordan beregnes dette?

Beregn de fire ruters længde med startby i hhv. A, B, C og D, der fremkommer, hvis man går frem efter "nærmeste nabo"-metoden.

Hvilken rute er den korteste?

Nu ændres der i vilkårene på kortet på følgende måde:

Det koster 1 kr at rejse 1 km i brændstof.

På ruten A-D er en bro, hvor broafgiften er 10 kr uanset hvilken vej, der køres.

På ruten D-C er en tunnel, hvor tunnelafgiften er 6 kr uanset hvilken vej, der køres.

På ruten B-C er en vejafgift på 2 kr uanset hvilken vej, der køres.

Hvis man vil køre fra A til B koster det en grænsetold på 4 kr, men fra B til A er det gratis.

Hvad koster de korteste ruter at køre?

Hvilken rute er den dyreste at køre?

Hvilken rute er den billigste at køre?

(En rute angives på følgende måde: ABDC, hvor det så er underforstået at A er startby og C er slutby)

Aktivitet: Traveling salesman problem i skolegården

Med 6.klasse lød opgaven på, at de med kridt i gården skulle tegne fem krydser (byer) med forskellige indbyrdes afstande. For at få en hensigtsmæssig opgave at undersøge på efterfølgende, skulle de 5 krydser placeres efter følgende regel:

"I skal se et koordinatsystem for jer på jorden, hvor det første kryds skal sættes i (0,0), og de fire andre skal placeres tilfældigt i hver sin kvadrant i koordinatsystemet". Eksempelvis srm vist til højre.

Opgaven er nu for eleverne i grupper (optimalt 3 stykker, vil jeg mene) at undersøge deres mulige ruter. Der er mange konkrete opgaveformuleringer at arbejde med ud fra de fem krydser (byer). Her er et par eksempler:

Hvor mange ruter kan der kombineres?

Hvilke(n) rute er den korteste?

Hvilke(n) by er smartest at starte i?

Hvilken rute er kortest fra A til B, hvis alle andre byer skal besøges undervejs?

Hvor mange ruter findes der fra A til B, hvis du aldrig må gå mellem C og A?

Findes der en god metode til at finde den korteste rute?

Mine elever nød aktiviteten og var meget optaget af det.