MELLEMTRIN OG UDSKOLING * KOMBINATORIK OG ALGORITMER TIL DET * OPTIMERING

 

Problemet: En rejsende handelsmand skal besøge et antal byer på sin rejse og kender byernes indbyrdes afstand. Hvilken rute er den korteste, hvis han skal besøge alle byer nøjagtig én gang hver? Og hvor mange forskellige ruter kan han vælge?

 

Her begrænses løsningsalgoritmerne til følgende to:

  • Brute force
  • Nærmeste nabo

 

Brute force-algoritmen:

Løses problemer med brute force algoritmen afprøves ALLE de mulige kombinationer uden skelen til om nogle af kombinationerne af indlysende grunde er "åndssvage" at afprøve, fordi man logisk kan udelukke dem fra start. Hvis der findes en løsning på et kombinatorisk problem, er man med brute force sikker på at finde den, men det kan være et omstændigt arbejde, da man så at sige går "den slaviske vej".

 

Eksempel: Hvordan kan 8 dronninger placeres på et skakbræt, så ingen af dem truer hinanden?

Her findes 64*63*62*61*60*59*58*57 = 178.462.987.637.760 kombinationer af dronningernes kombinationer, der skal undersøges, og logisk vil mange af dem kunne udelukkes uden den store afprøvning, men med brute force gennemgås altså alle kombinationer.

 

Nærmeste nabo-algoritmen:

Inden for traveling salesman problemet findes en algoritme, der kaldes nærmeste nabo-algoritmen. Den går ud på, at man vælger en startby, og derefter finder den nærmeste naboby. Fra den naboby finder man derefter den nærmeste naboby igen, som ikke allerede har været besøgt osv., indtil man til slut kun har en by, man mangler at besøge, som man så tager til. I det tilfælde skal man undersøge ruter med startby i alle de givne byer, og derfra er resten af ruten faktisk givet, medmindre at to nabobyer ligger lige tæt.

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.

Traveling salesmans problem