Steinertræ-forskningen på DIKU får en renæssance – Københavns Universitet

SCIENCE > Presse > Nyheder > 2014 > Steinertræ-forskningen...

26. november 2014

Steinertræ-forskningen på DIKU får en renæssance

Forskning

I starten af december indtager DIKU-forskere USA's østkyst som deltagere i konferencen, DIMACS Challenge, hvor de skal præsenterer deres nye resultater om Steinertræ-problemet. Heriblandt er Pawel Winter, som er internationalt anerkendt som den førende ekspert inden for geometriske Steinertræer. Nu er han efter et sidespring til andre forskningsinteresser vendt tilbage til det felt, der for godt 30 år siden satte gang i hans forskerkarriere.

Steinerforskningsgruppen fik en noget tilfældig begyndelse

Steinertræ-problemet går ud på at finde den korteste vej mellem et sæt af punkter (se mere i højre side), og det har været kendt i over 200 år. Der har dog ikke altid været tradition for at forske i Steinertræer på DIKU. Faktisk tog forskningen i disse NP-hårde geometriske problemer først sin begyndelse med Pawel Winter, som fik vakt sin interesse for emnet på en noget usædvanlig måde:

“Jeg blev først introduceret til Steinertræ-problemet, da jeg skulle til at skrive speciale i 1980”, fortæller Pawel Winter, som i dag er professor på DIKU. “Min vejleder, Jakob Krarup, (i dag professor emeritus, red.) havde et stykke A-4 papir liggende i sin skrivebordsskuffe med en lang liste specialeemner. Den tog han frem og sagde “vælg ét!”. Jeg protesterede og sagde, at jeg ikke kendte emnerne tilstrækkeligt til at kunne tage et informeret valg, men han var ubøjelig og sagde bare, “Det er lige meget, bare peg på papiret og vælg et emne”. Og sådan gik det til, at bl.a. Steinerproblemet i dets forskellige udformninger blev emnet for mit professionelle virke som forsker”.

Pawel gik efter denne noget chokerende oplevelse hjem og læste op på problemet. Han kom hurtigt til den konklusion, at emnet var spændende og at han gerne ville arbejde videre med det. "Jeg var heldig", griner Pawel, "jeg ramte godt".

Siden har han forfattet bogen “The Steiner Tree Problem” (1992), som har fået kanonisk status på Steinerforskningens internationale scene. Også på DIKU spredte interessen for Steinertræet sig til Martin Zachariasen, Pawels tidligere ph.d.-studerende, som har gjort Steinerforskningen til det bærende element i sin forskerkarriere, og for nyligt har også den ellers bioinformatik-interesserede postdoc, Rasmus Fonseca, vendt sig mod Steinerforskningen. Sammen drager de mod USA til december for at deltage i konferencen, DIMACS Challenge, hvor de skal præsentere deres nyeste resultater: DIKU-forskerne har forladt det todimensionelle euklidiske plan og bevæget sig over i det langt vanskeligere problem at arbejde med Steinertræer i flere dimensioner - foreløbigt er det således lykkedes dem at forbinde 18 punkter i 3D.

Steinertræer har været kendt siden 1811 - og bruges i praksis i dag

Steinertræ-problemet blev første gang formuleret i 1811 af den franske matematiker og logiker, Joseph Diaz Gergonne (portrætteret på billedet til venstre).

Det var dog først i 1950'erne og 60'erne at Steinertræ-problemet fik status af andet og mere end en geometrisk kuriositet. Med muligheden for at løse problemet ved hjælp af computere, kunne man efterhånden finde optimale løsninger for meget store netværk. Dette åbnede op for at anvende Steinertræer på forskellige praktiske problemer. Fx havde det amerikanske Bell Telephone Company i løbet af 50'erne brug for at beregne, hvordan et optimalt netværk ville se ud for at fastslå, hvor meget kunderne skulle betale for deres forbindelse.

Det er dog først i nyere tid, at Steinertræ-algoritmer og -heuristikker er blevet så effektive og computernes beregningskraft så stor, at Steinertræer for alvor kan anvendes i praksis. I 1989 var det lykkedes amerikanske forskere at forbinde 29 byer ved hjælp af Steinertræet, men 11 år senere kunne Pawel Winter og Martin Zachariasen præsentere et noget mere imponerende resultat - et Steinertræ med hele 13509 byer.

At finde et netværk med optimale Steinertræer har en lang række anvendelsesmuligheder inden for især logistik og elektronik. Ud over at anvende Steinertræer i konstruktionen af kommunikations- og infrastrukturnetværk, er det i dag meget almindeligt at bruge Steinertræer til at designe layoutet af ledninger i computerchips, så man kan minimere forsinkelser og spare på strømmen.

For Pawel Winter er det ikke så meget anvendelsen men snarer den spændende teoretiske udfordring, som Steinertræ-problemet stiller, som har holdt ham ved ilden i alle disse år. Ikke desto mindre ser han flere muligheder for anvendelse af Steinertræer i 3D. Fx kunne man forestille sig nødvendigheden for at etablere netværk mellem satellitter i rummet, platforme på oceanerne eller et rektilineært netværk af vand- og elledninger i bygninger. I denne anvendte form må man imidlertid ofte tage højde for forhindringer, som netværket skal undgå, og så bliver problemet endnu mere vanskeligt.

Steinerforskningen i dag lever i bedste velgående

Selvom algoritmikere har beskæftiget sig med Steinertræ-problemet i mange år, er der stadig gang i feltet. Dette kan man se af den veletablerede DIMACS Challenge, som hvert 2. år fokuserer på et bestemt algoritmisk problem. I de seneste år har det således været korteste vej-problemet og traveling salesman-problemet, der har været på programmet, men i 2014 er turen kommet til Steinertræ-problemet.