Hvordan skæres julekagerne bedst ud? Selv de kraftigste computere kan ikke finde løsningen

Man kan ikke regne med at videnskaben kommer én til undsætning, når det gælder om at skære julesmåkager ud. (Foto: Shutterstock)

Man kan ikke regne med at videnskaben kommer én til undsætning, når det gælder om at skære julesmåkager ud. (Foto: Shutterstock)

09 december 2020

Hvad er der på den anden side af sorte huller? Hvad er bevidsthed egentlig? Og hvordan spilder man mindst mulig dej, når man skærer julekager ud?

Ja, der er visse spørgsmål, som videnskaben ikke kan svare på… endnu.

Ifølge en pressemeddelelse fra Københavns Universitet (KU), kan datalogernes computere simpelthen ikke følge med, hvis de skal udregne, hvordan man skærer mere end fire-fem julekager ud på den mest optimale måde.

Pressemeddelelsen følger et nyt studie fra KU, som påviser den overvældende kompleksitet, der lige nu begrænser forskning inden for de såkaldte ‘pakningsproblemer’.

Pakningsproblemer har at gøre med, hvordan man bedst muligt kan pakke et antal objekter så tæt som muligt i enten to eller tre dimensioner, og problemerne har optaget matematikere i århundreder.

Siden computernes indtog har man også brugt dem til at hjælpe med udregningerne.

»Selvom vi er i stand til at løse ret komplekse problemer ved hjælp af algoritmer, er dette problem åbenbart stadig for stor en mundfuld for de computere, der findes i dag,« fortæller adjunkt Mikkel Abrahamsen, fra Datalogisk Institut, ifølge pressemeddelelsen.

»På nuværende tidspunkt er det ikke muligt at pakke mere end 5-10 objekter optimalt, og vores resultat indikerer, at det tal nok ikke kommer til at stige ret meget lige foreløbig.«

At pakke ting på den mest optimale måde er et problem, som, udover julekagerne, også er relevant for flere industrier, såsom shippingbranchen når man vil pakke mest muligt i en container, eller i metalforarbejdning når man skærer materialer ud med mindst mulig spild.

Selv pakningen af umiddelbart enkle former som firkanter, er besværligt. Her ses den mest optimale pakning af fem kvadratiske objekter (tv) og elleve kvadratiske objekter (th) (Illustration: Abrahamsen et al./KU)

Problemet er, at selv tilsyneladende simple foretagender som at tilføje en ekstra palle til en kvadratisk container, hvor man kan pakke op til 10 paller på 1x1 meter og regne den nye optimale størrelse ud, er umuligt.

»Beregningstiden vokser mere end eksponentielt, når man tilføjer flere paller, og så kan selv de bedste computere ikke følge med,« uddyber Mikkel Abrahamsen.

»Så teoretisk er det muligt, men ud fra den hastighed, som computeres regnekraft vokser med, vil det formentlig tage millioner af år, før vi kan håndtere nogle få ekstra objekter optimalt.«

Når der er næsten uendeligt mange kombinationsmuligheder, for hvor man kan placere pallerne, kan algoritmerne ikke blot afprøve de forskellige pakningsmuligheder, men må gå mere analytisk til værks, og det tager lang tid, ifølge pressemeddelelsen.

Har man at gøre med mere komplicerede former som julekager, der jo gerne skal ligne stjerner eller træer, vil man højst kunne finde en optimal løsning for op til fire objekter.

»Både industrien og småkagebagere må fortsat stille sig tilfreds med løsninger, som ikke er helt optimale, og hvile i visheden om, at vi mennesker trods alt stadig er bedre end computere til denne slags opgaver – indtil videre,« slutter Mikkel Abrahamsen.   

Studiet er blevet fortrykt på prepreting-serveren arXiv, hvor det kan læses i sin helhed. Studiet er endnu ikke fagfællebedømt, men det er blevet præsenteret på datalogi-konferencen FOCS 2020.

cll

Ovenstående er udvalgt og resumeret af Videnskab.dk, men redaktionen har ikke udført selvstændig research. Gå til den oprindelige kilde for flere detaljer.