3-23 Money for Nothing.

Charlie brugte Dijkstras algoritme til at finde korteste vej. Han snakkede om Frank – Wolfe algoritmen til at finde ligevægt i transportnetværk og han foreslog Don at bruge det gamle logiske trick med at finde ud af, hvem der lyver, ved at lade dem udtale sig om hinanden. Der var også noget om “Vulture funds”. Det kan man læse om her, hvor præcis de data, der optræder i Numb3rs, er nævnt: Et firma køber dele af Zambias statsgæld til hugpris på et tidspunkt, hvor Zambia får eftergivet en del gæld til udlandet (firmaet giver 3,3 millioner dollars – gælden var oprindelig 15 millioner dollars, som Zambia skyldte Rumænien). Firmaet sagsøger derefter Zambia for 55 millioner dollars, som er gælden plus renter. Men det er vist ikke matematik, bortset fra rentesregningen…

Dijkstras algoritme.
Der er mange problemer, der kan formuleres som “korteste vej” problemer. Et helt oplagt eksempel er det, man f.eks. får løst i krak.dk eller andre ruteplanlægningsprogrammer. Man skal finde en effektiv vej fra A til Å, og man kender en masse mellemliggende stykker: fra A til K, fra K til M, fra K til U,…
Man ved, hvor lange, de mellemliggende stykker er, enten i tid – hvis jeg vil finde den hurtigste rute, eller i egentlig længde i km, hvis det er den korteste rute, jeg vil have. Her er et eksempel på dele af ruter tegnet ind mellem byerne a,b,c,d,e og f. Det er en graf med retning, der er pile på kanterne.

Man kan beskrive Dijkstra’s algoritme generelt, men lad mig nøjes med at give eksemplet. det generelle kan I Google jer til. Eller kig f.eks. i wikipedia. Man kan også nogenlunde regne det overordnede princip ud udfra eksemplet.
Mit udgangspunkt er a, og jeg vil gerne finde kortest afstand fra a til de andre byer. Dijkstras algoritme siger:
1. Kortest afstand til a er 0.
2. Gå til de byer, hvortil man kan komme med en kant fra a. (Det er b og c) Skriv den kortest kendte afstand til a, b og c indtil videre (0 til a, 25 til b og 76 til c). b er den by, der er tættest på a, og vi finder ikke en kortere vej til b, så nu kender vi kortest afstand til a og til b.
3. Gå til de byer, der kan nås med en kant længere fra b (den, der var tættest på a)  (Nu får vi to ruter til c, en til d og en til e.) Skriv de nye korteste afstande ind – bemærk, at vi bruger de afstande, vi har fundet i første skridt. Nu ser grafen sådan ud:

i mere avanceret grafik skulle b, som var tættest på i første step, males gul og pilen a til b, som er den korteste vej dertil skulle også males gul. Man maler desuden d gul nu, fordi den er tættest på a via b, og der kan ikke opstå kortere veje senere (overvej det – nye veje til d vil gå via nogen af de stumper, vi har fundet, og de er længere end den vej, vi har fundet til d via b). Og pilen fra b til d skal være gul.

I næste skridt bliver afstanden til e ændret til 80, fordi vejen a til b til d til e er 80 lang. Nu er der afstand 65 til c og 80 til e, så vi maler c gul, maler pilen fra b til c gul og ser på pile fra c. Det giver en pil til f, som så har afstand 65+80= 145 til a.

I sidste skridt er e nærmest, mal den gul, mal pilen fra d til e gul. Udregn afstand til f via e til 80 + 40=120. Det er mindre end før, så vi maler f gul, maler pilen fra e til f gul.

Vejen fra a til f bliver så fra a til b til d til e til f. Man skal følge de gule pile. Der kan godt være mere end en mulighed for den korteste vej, men det er der ikke i dette eksempel.

Jeg har lavet de “gule” pile lidt fede, men det er ikke let at se. Alle pile, undtagen de tre, der går skråt ned mod højre, er gule..:

Man kan lege med en java applet på denne side. Man kan selv lave sig grafer, men man kan også vælge knappen eksempel, hvor der allerede er lavet en graf.

Ligevægt i trafikflowproblemer. Frank-Wolfe
Charlie og hans far snakker om Frank-Wolfe algoritmen til at bestemme ligevægte i trafikflow.
Trafikflow ligevægtsproblemet drejer sig om at forudsige trafikken alle steder i et netværk, hvis man ved, hvor mange, der skal bevæge sig mellem hvert par af punkter. I grafen ovenfor ved man måske, at 100 personer tager fra a til f, 150 fra b til f etc. Nu vil trafikken, altså afstandsmålene i grafen afhænge af, hvor mange andre, der er på vejen, og så er den mest fordelagtige vej for de sidste , der tager afsted fra a, måske ikke den samme, som for de første. Frank-Wolfe algoritmen løser bestemte optimeringsproblemer (kvadratiske, nærmere bestemt), og den bruges i bl.a. trafiknetværksanalyse.