Kategoriarkiv: Blogg

De bättre spektrala artiklarna

2014, Blogg

Ren matematik, datamatematik och hur man kan lösa det olösliga

14 september, 2014 Spektraklet Lämna en kommentar

En betydande del av den nutida forskningen inom matematik använder datorer som hjälpmedel. Naturligtvis är användningen av datorer mest utspridd i tillämpad matematik och i statistik (bl.a. i form av Monte Carlo-metoder), men dataprogram kan även användas för att bevisa satser som känns väldigt teoretiska. Det mest välkända exemplet lär vara beviset på fyrfärgssatsen.

Datorer har dock ett antal begränsningar: man kan mekaniskt, genom att gå igenom fall ett för ett, bevisa något endast för ett ändligt antal fall. Beräkningar gjorda av en dator är dessutom inte exakta i alla fall. Detta beror på att det i de flesta fallen finns endast en begränsad mängd minne reserverat för decimaltal, och därmed tappar man i vissa fall precision då man utför beräkningar. Oftast är detta ej önskevärt, men i vissa specialfall kan man faktiskt utnyttja denna brist för att göra beräkningar som tekniskt sett inte borde vara möjliga!

Tänk dig att vi skulle i något sammanhang ha behov av en funktion som tar in två reella tal och ger som resultat dess summa, förutom om talen är lika. Ifall talen är lika ger den ut det ena av talen (vilket av dem spelar ingen roll eftersom de är lika). Uttryckt matematiskt är vi alltså intresserade av funktionen $f\colon \mathbb{R}^2 \rightarrow \mathbb{R}$ , där

$f(x, y) = x + y$ ifall $x \neq y$ , och
$f(x, y) = x$ ifall $x = y$ .

På en dator kan ovanstående konstruktion i vanliga fall lätt implementeras med hjälp av en if-sats, men låt oss nu anta att vi av någon orsak inte kan använda oss av konditionaler. Istället måste vi uttrycka ovanstående funktion med hjälp av endast de fyra grundräknesätten. Först skulle vi säkert försöka skapa en multiplikation med noll i något skede för att få en av termerna att försvinna i fallet där de båda är lika:

$x + (x-y)\cdot y \qquad \: (1)$ .

Detta fungerar ifall $x = y$ , men om $x \neq y$ får vi $x + xy - y^2$ , vilket vi inte ville. Vi borde alltså i fallet $x \neq y$ lyckas få den tillagda överloppstermen $x-y$ att försvinna. Ett sätt är att istället använda sig av formeln

$x + \frac{x-y}{x-y} \cdot y \qquad \: (2)$ .

Ifall $x \neq y$ , så ger ovanstående formel det korrekta resultatet $x + y$ . Tyvärr så fungerar den ej i fallet $x = y$ , eftersom vi då stöter på problemet att dividera med noll.

Eftersom de första, mest uppenbara försöken att skapa formeln misslyckades, kan det löna sig att fundera en stund över orsaken på varför vårt tillvägagångssätt ej fungerade. Vi märker att funktionen $f\colon \mathbb{R}^2 \rightarrow \mathbb{R}$ är definierad för alla par av reella tal. Därmed kan vi inte i något skede dela med ett uttryck som kan bli noll, eftersom vi då får till stånd ett par av reella tal där formeln ej är definierad.

Ifall vi undersöker funktionen $f$ närmare märker vi även att den inte är kontinuerlig i hela $\mathbb{R}^2$ . Problempunkterna är punkterna av typen $(a,a)$ där $a \neq 0$ . Om vi t.ex. slår fast x-koordinaten att vara 2, ser vi att det för gränsvärdena gäller att $\lim\limits_{y \to 2^{+}} f(2,y) = \lim\limits_{y \to 2^{-}} f(2,y) = 4$ , men att $f(2,2) = 2$ . Vårt mål var att beskriva funktionen $f$ endast med hjälp av de fyra grundräknesätten. Det är välkänt att funktioner som är uppbyggda endast med hjälp av de fyra grundräknesätten är kontinuerliga i hela sin definitionsmängd. Därmed är det omöjligt att beskriva funktionen $f$ endast med hjälp av grundräknesätten eftersom funktionen inte är kontinuerlig!

Det verkar alltså som vi skulle ha kört fast, eftersom det rent matematiskt är omöjligt att lösa problemet, givet de verktyg vi har. Detta är dock ett av de fall där vi kan utnyttja de begränsningar som datorer ställer på beräkningar av decimaltal. I vanliga fall beskrivs decimaltal av en dator på följande sätt:

$signifikand \cdot bas^{exponent}$ .

Eftersom varje decimaltal ges en konstant mängd utrymme i datorns minne, finns det en gräns på storleken på signifikanden (dvs. hur många signifikanta siffror talet kan ha) och även en gräns på hur stor exponenten kan vara. Detta leder till att datorn kan representera tal som är nära noll mycket noggrant, medan precisionen (absolut sett) blir allt mindre ju större talet är. Ifall vi som exempel slår fast basen att vara $10$ och antalet signifikanta siffror att vara $10$ och jämför exponenterna $-20$ och $20$ , ser vi att vi kring talet $10^{-20}$ kan representera skillnader av storleksordningen $0.000000001 \cdot 10^{-20} = 10^{-11}$ , medan vi kring talet $10^{20}$ endast kan representera skillnader av storleksordningen $0.000000001 \cdot 10^{20} = 10^{11}$ ! Därmed om vi t.ex. skulle göra beräkningnen $10^{20} + 1$ skulle resultatet vara $10^{20}$ , eftersom vi ej kan representera tal så noggrant kring $10^{20}$ .

Hur kan vi då utnyttja detta fenomen för att lösa vårt ursprungliga problem? Vi hade tidigare skapat formeln $(2)$ , som fungerar bra förutom att vi kan tvingas dela med noll. För att undvika division med noll kan vi modifiera formeln på följande sätt:

$x + \frac{x-y}{(x-y) + \varepsilon} \cdot y \qquad \: (2′)$ ,

där $\varepsilon$ är ett till absolutbeloppet mycket litet positivt tal (storleken på talet beror på representationen av decimaltalen). Matematiskt sett gäller naturligtvis inte att $(x-y) + \varepsilon = x-y$ , men p.g.a. bristerna i decimaltalsberäkningen kommer likheten att gälla ifall $x$ och $y$ är olika och är tillräckligt stora. Kvoten $\frac{x-y}{(x-y) + \varepsilon}$ är alltså $1$ ifall $x \neq y$ , och därmed uppfyller formeln $(2′)$ kravet att $f(x,y) = x + y$ om $x \neq y$ .

Å andra sidan ifall $x = y$ , så är naturligtvis $x - y = 0$ och därmed är $0 + \varepsilon = \varepsilon$ , eftersom vi kan representera tal noggrant kring noll. Därmed undviker vi division med noll och kvoten $\frac{x-y}{(x-y) + \varepsilon}$ blir 0. Alltså gäller det för formeln $(2′)$ även att $f(x,y) = x$ ifall $x = y$ .

Vi har alltså lyckats trolla fram en formel som med hjälp av datorberäkningar löser ett matematiskt sett omöjligt problem. Dock har formeln sina begränsningar; t.ex. får talen $x$ och $y$ ej vara för små, för då skulle additionen av talet $\varepsilon$ påverka det slutliga resultatet som formeln $(2′)$ ger. I de flesta fallen är precisionsproblemen i decimaltalsräkningen något man försöker undvika (se t.ex. Wikipedia-artiklen om ämnet), men i vissa fall kan man faktiskt dra nytta av dem. Det är bra att komma ihåg att begränsningar som datorer ställer inte alltid är endast negativa; i vissa fall kan vi p.g.a. begränsningarna lösa problem som annars vore olösliga.

Jag vill till sist tacka Lasse för idén till artikeln! Den som är intresserad att lära sig mer om ämnet kan börja t.ex. med Wikipedia-sidan IEEE floating point.

Sebbe

2014, Blogg

Helt skit artikel, del 2: Serotonin – En historia om diarré, LSD och antidepressanter

20 juli, 2014 Spektraklet Lämna en kommentar

I förra delen i skitserien behandlades det eventuella sambandet mellan nationella mängden intagen koffein och förbruket av toalettpapper. Även denna artikel tangerar ämnet, men ur neurokemisk synvinkel. Människan är ett komplext neurobiologiskt system som regleras med flera olika signalämnen, såsom serotonin, dopamin och acetylkolin. De reglerar humör, aptit, sömn, inlärning och minne, samt flera fysiologiska funktioner. Ja, men VARFÖR bry sig? I moderna tider utsätts vi för en ökande mängd olika preparat, som med eller utan avsikt påverkar våra handlingar i vardagliga situationer. Därmed är det viktigt att veta HUR de påverkar oss. Denna artikel har serotonin i focus.

Historien börjar inte direkt med skit, utan med själva tarmen. Ca år 1950 upptäckte italienska forskande att tarmcellerna innehöll ett nytt okänt ämne, serotonin. Ungefär samtidigt hittade två andra forskargrupper, oberoende av varandra, serotonin i trombocyter, dvs blodplättar, och i hjärnan. Det var uppenbart att serotonin hade en viktig biologisk roll.¹

Några år tidigare, 1943, hade schweizaren Albert Hofmann upptäckt de psykedeliska effekterna av LSD.² Många forskade gjorde iakttagelsen att LSD och serotonin hade en mycket liknande struktur, bild 2. Om LSD hade en mycket stark effekt på sinnet redan med små doser, så kanske även serotonin hade en neurologisk funktion? Hypotesen var alltså att patienter med tarmsjukdomar skulle ha höjda eller sänkta serotoninhalter, och därmed mentala problem. Mycket riktigt bevisade man 1954 att patenter med diarré pga en viss typ av tarmcancer hade höjda halter av serotonin, men ingen koppling till mentala sjukdomar kunde finnas. På 1950- och 1960-talet behandlades dessa cancerpatenter med fenklonin, ett ämne som inhiberar biosyntesen av serotonin. Behandlingen lättade på diarrésymptomen men patienterna fick symptom som liknade depression. Detta var början för hypotesen att depression orsakas av serotoninbrist i hjärnan. Med andra ord var tanken att depression kunde botas genom att höja halten av serotonin i hjärnan.

Bild 1: Albert Hofmann med en kemisk modell av LSD. Han dog år 2008 vid en mogen ålder av 102 år.

Bild 2: Jämförelse av serotonin, till vänster, och LSD, till höger. Gemensamma strukturen är märkt med rött.

Men hur borde man gå till väga för att öka halten serotonin? Lösningen till dilemmat kräver kunskap om serotoninets roll i centrala nervsystemet, bild 3. Nervceller är inte direkt kopplade till varandra, utan i stället förmedlar de signaler till varandra över små klyftor, s.k. synapser. Olika signaler förmedlas i synapserna med flera olika signalmolekyler, till vilka även serotonin hör. Nervcellerna lagrar serotonin i s.k. vesiklar, som är speciella membraner (”bubblor”). Vesiklarna transporteras till ytan när en nervcell skall förmedla en signal, vilket resulterar i en utlösning av serotonin. Serotonin binder sig till receptorer i mottagande cellen. Det finns sju kända receptortyper för serotonin, och dessa kan ha flera underklasser. Ju mer serotonin som binder sig till receptorerna, desto starkare är signalen som mottagande cellen förmedlar. Till slut lossnar serotonin från receptorerna och upptas tillbaka till ursprungliga nervcellen med ett transportprotein, som fungerar som en pump. Upptaget serotonin bryts ner i nervcellen. Upptagningsmekanismen ser till att signalen inte förmedlas en längre tid än vad är nödvändigt.

Bild 3: Schematisk representation av en synaps.

Med kännedom av synapsernas funktion blev ledande tanken bland forskare att låga serotoninhalter kunde kompenseras med att hålla serotonin längre mellan nervcellerna. Forskningens focus blev därmed att störa serotoninpumpens funktion med något lämpligt ämne. Det var önskvärt att utveckla läkemedel som inte påverkade andra signalämnespumpar, utan endast serotoninpumpen, s.k. selektiva serotoninåterupptagshämmare (selective serotonin reuptake inhibitor, SSRI). En svensk forskargrupp var år 1969 de första att utveckla en SSRI och bevisade dess effekt i behandling av depression.¹ Några år senare utvecklades fluoxetin, bättre känd under varunamnet Prozac, en liknande SSRI som godkändes för bruk år 1987 av FDA. Bruket av antidepressanter, till vilka SSRI hör, har ständigt ökat i hela världen. År 2000 var konsumtionen i Finland 36 dagliga doser per 1000 invånare (DDD), medan år 2011 hade siffran fördubblats till 70 DDD. Medeltalet för de undersökta länderna var 31 DDD år 2000 och 56 DDD år 2011.³

På senare år har det blivit uppenbart att depression inte orsakas av serotoninbrist. Om antidepressanter fungerar, så är det inte för att de ökar serotoninhalten. Detta har lett till att bruket av antidepressanter har ifrågasatts.⁴ Situationen kan liknas med att Burana botar huvudvärk, men inte på grund av att kroppen har brist på Burana. Är det etiskt rätt att behandla patienter med läkemedel vars verkningsmekanism är okänd?

Situationen blev avsevärt mer komplex år 2006 då det upptäcktes att det finns två olika pumpar, serotonintransportprotein (SERT) och cellmembranmonoamintransportprotein (PMAT). SERT har länge varit känd och SSRI utvecklades för att störa denna, medan PMAT var en ny upptäckt. Serotonin binder sig ungefär 100 gånger bättre till SERT än till PMAT. Detta kan ge illusionen om att SERT ansvarar för största delen av upptagningen av serotonin. Faktum är att PMAT bidrar till upptaget med en avsevärd del, då den transporterar mycket fortare än SERT. Många SSRI blockerar även PMAT, men detta kräver mycket högre doser än vad som normalt används för depressionsbehandling.⁵

Vad lär vi oss om detta? Hjärnan är ett mycket komplext organ, som vi än idag inte fullt förstår. Upptäckten av PMAT-pumpen är ett bra exempel hur vår förståelse om en viss funktion, i detta fall upptagningen av serotonin, kan totalt förändras. En upptäckt kan ifrågasätta årtionden av medicinsk praktik, samt ställa läkemedelsindustrin i ett tvetydigt ljus. Kan man marknadsföra en produkt om den ”fungerar” men man vet inte hur?

[1] Sjoerdsma, A., Palfreyman M.G. Annals of the New York Academy of Sciences, 600 (1990) 1

[2] Bad trip, but thousands followed, The Saturday Morning Herald, 2.5.2008, <http://www.smh.com.au/news/obituaries/bad-trip-but-thousands-followed/2008/05/01/1209235053330.html>, hämtad 20.7.2014

[3] HEALTH AT A GLANCE 2013: OECD INDICATORS, 21.11.2013, s. 102-103, <http://www.oecd.org/els/health-systems/Health-at-a-Glance-2013.pdf>, hämtad 20.7.2014

[4] Lacasse, J.R., Leo J. PLoS Med, 2 (2005) 392

[5] McDuffie, J.E., Motley, E.D., Limbird, L.E., Maleque, M.A. J. Cardiovasc. Pharmacol. 35 (2000) 398–402

2014, Blogg

Problemlösning – sagan om att overkilla

13 juni, 2014 Joar Jensén Lämna en kommentar

Mycket av det som görs i Gumtäkt och speciellt i Exactum handlar om någon form av problemlösning. Redan under grundkursen i Analys presenteras man varje vecka med åtminstone sex problem man förväntas kunna lösa. Problemen förföljer studerandena genom hela kandidat-, magisterexamen och för vissa även in i forskningsvärlden. Ofta kritiseras dessa problem; jag är nästan säker på att så gott som alla som studerat matematik eller data har i något skede av studierna tyckt att problemen som skall lösas är helt för artificiella, eller abstrakta för att vara intressanta: vem bryr sig om varför man inte får dela med $0$ ? För att hålla kvar de få matematikstuderanden vi har tänkte jag i denna text dela med mig ett exempel av applicering av abstrakta problemlösningstekniker för att åstadkomma saker som på riktigt spelar någon roll. Som huvudpersoner i historien fungerar tre namnlösa spektrumiter som vi kallar för Lasse, Peter och Jeremias, alla med en matematisk/datavetenskaplig utbildning.

Varje problemlösning börjar med ett problem. I vårt fall började vi från följande scenario:

Tänk dig att du och två av dina vänner vid en given tidpunkt har fått en lapp med gåtor vars lösningar är sex olika barer i Helsingfors. Er uppgift är, att snabbare än 200 andra grupper på 3 människor, ta er till alla av dessa sex barer, inmundiga 1.5l öl på varje ställe, sedan ta er till Otnäs och inmundiga 1.5l öl till. Som färdmedel får endast allmäntransport användas.” För enkelhetens skull kommer jag från och med nu kalla detta scenario för ”Problem Y”.

Problemlösning i sig är ett forskningsområde inom kognitiv psykologin. Inte oväntat så verkar det inte finnas ett absolut svar på frågan ”hur skall man göra för att lösa problem?”. Det finns dock vissa standardtekniker för problemlösning som dyker upp i olika undersökningar. Den man ofta börjar med inom matematik och datavetenskap kallas abstraktion. Abstraktion går ut på att exakt definiera vad man försöker åstadkomma, samt identifiera vilka delar av den information man har som behövs för att utveckla en lösning. Dessutom brukar man under abstraktion ofta identifiera begränsningar som sätts på de metoder man kan använda i sin lösning. Ett sätt att beskriva problemet efter abstraktion är genom att använda orden ”INPUT” för att beskriva den (viktiga) informationen man har, ”OBJECTIVE” för att beskriva det man försöker åstadkomma och ”CONSTRAINTS” för att beskriva de begränsningar ens lösning måste följa. Då det kommer till problem Y lyckades vi inte komma på ett sätt att använda (lagliga) datavetenskapliga/matematiska metoder för att hjälpa oss med inmundigandet av $7 \times 1.5$ liter vätska eller påverka de $200$ andra lagen. Därför bestämde vi oss för att ignorera dessa delar av Y och fokusera på lösningen av gåtorna samt bestämmandet av rutten att ta. Som begränsningar för problemet identifierade vi faktumet att rutten måste endast bestå av allmäntransport. Efter abstraktion såg Y alltså ut såhär:

INPUT: startställe, gåtor till 6 barer

OBJECTIVE: Kortast möjligast tid för att lösa gåtorna, ta sig runt till barerna och sedan ta sig till Otnäs.

CONSTRAINTS: Endast allmänna färdmedel tillåtna.

Intressant nog betyder abstraktion inom konst oftast inte ”göra saker klarare”.

Efter abstraktion är det sedan dags att börja söka en lösning. En inom psykologin identifierad och inom Exactum utlärd teknik för problemlösning kallas divide and conquer. Idén är att spjälka upp ett komplext problem i mindre delar i hopp om att delarna skall vara lättare att lösa. Ofta strävar man till att delproblemen är oberoende av varandra, då kan nämligen alla delproblem lösas samtidigt. I bästa fall kan optimala lösningarna av delproblemen sen kombineras för att åstadkomma en optimal lösning på ursprungliga problemet. Det finns ett ganska naturligt sätt att dela in Y: lösningen av gåtorna samt bestämmande av rutten. Visserligen är dessa två problem inte riktigt oberoende, man kan inte bestämma rutten innan man har löst alla barer. Vi bestämde oss ändå för att dela in Y såhär i hopp om att gåtlösaren skulle bli tillräckligt effektiv för oss att ha någon nytta av rutlösaren. Olyckligt nog visade det sig att gåtlösning högst troligen är för svårt för oss att automatisera. Det finns en dator vid namnet Watson som har lyckats slå de bästa människorna på Jeopardy, men att åstadkomma detta tog 7 år för IBM:s topp ingenjörer. För att vara effektiv måste Watson dessutom köras parallellt på 70 datorer samtidigt. Eftersom vi inte kände för att börja bära omkring på 70 datorer samt inte hade 7 år att sätta på projektet, var det bästa vi kunde hoppas på ett hjälpmedel för gåtlösning, inte en automatisering. Det vill säga, vi skulle inte kunna kombinera lösningarna av delproblemen för att få en optimal lösare av Y. Liknande fenomen sker ofta inom datavetenskap/matematik. Ifall ursprungliga problemet man löser är ”tillräkligt svårt” kan man inte kombinera dellösningarna för att åstadkomma en optimal lösning. Men ofta visar det sig att den (lite sämre) lösningen man åstadkommer ändå är ”tillräkligt bra”, vilket också kommer att vara fallet med Y. Resten av denna text kommer att koncentrera sig på rutt-lösnings problemet: ”givet 6 barer samt en startposition hitta snabbaste sättet att ta sig till alla 6 barer och Otnäs med hjälp av allmäntransport”. Detaljerna av gåtlösaren kommer eventuellt att publiceras i ett senare skede (läs: ifall jag inte får en bättre idé för en höstartikel).

Då man söker efter en lösning till ett ovanligare problem är det alltid inte klart att det man försöker göra är svårt. Detta kan vara bra att ta reda på; det är rätt så onödigt att utveckla hemskt komplicerade lösningar till problem som egentligen (bevisligen) är simpla. ”Hur svårt kan det vara?” var alltså nästa fråga vi ställde oss. En systematisk analys av olika problems svårighet är ett delområde inom komplexitetsteori och är ett forskningsområde för sig. Tekniska detaljer åsido så går analyserna av problemsvårigheter ofta ut på att man förliknar sitt problem med andra kända problem som man vet är svåra/lätta. Ofta är dessa kända problem relativt abstrakta, mest p.g.a. att det skall vara enklare att se likheterna mellan dem och det egna problemet. Då det kommer till vårt problem: ”givet en start position, 6 barer samt ett mål, hitta snabbaste rutten till alla” finns det ett relativt känt problem som man enkelt kan jämföra med, nämligen traveling salesman problem (TSP). I ursprungliga formuleringen av TSP ingår en försäljare som skall besöka alla städer i Tyskland och/eller Schweiz (ursprunget är oklart) i hopp om att sälja sina varor i var och en. Uppgiften är att försöka hitta den kortaste möjliga rutten att göra detta. I en mer abstrakt formulering av TSP har man en matematisk graf bestående av något antal noder och kanter där varje kant har en given längd. Målet är att hitta den kortaste möjliga rutten genom grafen som besöker varje nod åtminstone en gång. Ruttlösningen för problem Y kan ses som travelling salesman där noderna i grafen är de 8:a olika platserna som skall besökas och längden på en kant mellan två noder är tiden som det tar att ta sig mellan dem med allmäntransport. Denna jämförelse mellan problemen är tillräcklig för vårt behov, men inte helt fullständig, vilket vi kommer att märka lite senare.

Efter att man ”känt igen” sitt problem kan man sen dra slutsatser på huruvida man kan förvänta sig att det går att komma fram till en lösning som fungerar inom en rimlig tid. I vårt fall skulle ju en rutt-lösare inte hjälpa hemskt mycket ifall det skulle ta 5 timmar att använda den. Olyckligt nog är traveling salesman ett NP-svårt problem. Igen tekniska detaljer åsido, betyder detta att det i allmänna fallet knappast finns ett effektivt sätt att lösa TSP. Tur i oturen kommer dessa teoretiska begränsningar emot endast då man ökar mängden noder i grafen. Med andra ord så går det troligtvis inte att koda en effektiv ruttlösare för att komma till 100 barer. Men detta var ju inte vad vi var ute efter; våra levrar skulle ändå inte stå ut med så mycket öl. Att lösa rutten till 6 barer borde däremot inte vara en utmaning, ens åt Lasses miniläppäre. Vi kunde alltså fortsätta på projektet trots vissa teoretiska begränsningar.

Efter all förberedning visade sig själva kodandet av ruttlösaren var relativt lätt. Efter lite undersökning märkte vi nämligen att HSL bjuder på ett gratis gränssnitt till sin reittiopas, vilket i princip betyder att programmerandet av en normal reittiopas skulle (nästan) kunna vara en uppgift under ohjelmoinnin jatkokurssi. Inspirerade av detta samt de tidigare teoretiska funderingarna döpte vi vår ruttlösare till Drunken Salesman Opas (DSOPAS). Under kodandet av DSOPAS stötte vi egentligen endast på ett till problem som förhindrade oss från att lösa rutten optimalt. Problemet har att göra med jämförelsen av vårt problem och TSP. Då det kommer till allmän transportation kan det ju nämligen hända att tiden det tar att komma från bar X till Y är olika beroende på vilken tid på dagen man reser. Mera matematiskt formulerat så är längden av varje kant i grafen inte konstant. Detta betyder att för en optimal lösning av vårt problem borde reittiopas ”frågas” skilt för vikten av alla kanter i varje rutt möjlighet som undersöks. I en rutt ingår $7$ kanter, allt som allt finns det $6! = 720$ olika ruttmöjligheter. Totalt skulle algoritmen vid varje körning vara tvungen att fråga reittiopas efter längden av $5040$ kanter. Detta skulle annars inte vara ett problem, men HSL tillåter endast $5000$ frågor i timmen. Så fast det skulle vara helt möjligt att koda DSOPAS såhär, skulle det ta minst en timme att köra den. För att komma över detta problem bestämde vi oss för att än en gång approximera optimala lösningen genom att helt enkelt skita i att tiderna eventuellt ändrar. Den slutgiltiga DSOPAS börjar alltså med att fråga reittiopas efter tiden det tar att röra sig mellan alla 8 platser (6 barer, start och mål) vid en fixerad tidpunkt ( $\frac{6 \times 5}{2}$ kanter mellan barerna, $6$ från startpunkten till de olika barerna och $6$ från de olika barerna till målet, allt som allt $27$ ). Efter det löser DSOPAS den kortaste rutten i denna ”approximeringsgraf” med hjälp av en sofistikerad algoritm känd som ”prova alla möjligheter”. Under lösningen behöver DSOPAS inte fråga reittiopas alls. Slutligen väljer DSOPAS ut de 5 snabbaste rutterna, vilka sen körs på nytt genom reittiopas för att få egentliga tiderna det tar att använda var och en. Dessa fem rutter visas sen åt användaren. Att fråga reittiopas om tiderna för en fixerad rutt kräver ju alltså $7$ frågor. Allt som allt $27 + 5 \times 7 = 62$ frågor, betydligt bättre än ursprungliga $5040$ .

Näst borde vi kanske anlita en grafisk designer…

Efter att man löst sitt problem så återstår ett sista steg: verifikation av lösningen. Fastän vi kunde testa DSOPAS på påhittade rutter, var vi tvungna att vänta på årets Ylonz (som de flesta av er säkert har fattat är det Ylonz detta handlar om) innan vi kunde veta hur bra det skulle fungera på riktigt. (För att vara helt ärlig blev väntandet inte hemskt långt, sista buggarna i DSOPAS fixades onsdagen innan Ylonz lördagen). Jag kommer inte att prata så hemskt mycket om hur det gick, många av er vet det redan och för resten kan ju nämnas att vårt lag hette ”<script>alert (‘TechSupported’);</script>” samt att resultaten finns här. Jag påstår inte att DSOPAS var ända orsaken till att resultaten ser ut som de gör, men jag kan med största säkerhet säga att den tillsammans med vårt gåtverktyg nog hjälpte betydligt.

Det fanns en bar i årets Ylonz rutt som fungerar väl som exempel för nyttan vi hade av båda verktygen: Park hotell. Då vi, baserat på bilden av ett monopolhotell, slog in ”hotell” i gåtlösaren var ”Park hotell” det enda alternativet vi fick ut. Dumma som vi var trodde vi inte på vårt eget program, men fortsatte istället fundera. Fem minuter senare hade vi löst resten av tipset och kom fram till att gåtlösaren hade rätt från början. Senare, då vi kom fram till baren, visade sig att den långa kön skulle förhindra oss från att hinna på den bussen som DSOPAS hade bestämt åt oss tidigare. Då, detta under tidigare år skulle ha lett till en massa spekulationer på vad vi borde göra näst, kunde vi nu helt enkelt mata in de återstående barerna i DSOPAS på nytt. Den nya rutten vi fick av vårt program visade sig sist och slutligen vara lika snabb som den första vi hade fått.

Den här texten har egentligen två syften. Den ena är ett exempel på hur ”viktiga problem” kan modeleras och lösas genom abstrakta vetenskapliga metoder. Den andra kan sammanfattas i form av en utmaning. Åtminstone 1/3 av laget TechSupported kommer inom snarast framtid att försvinna utomlands och det verkar som vi inte kommer att ha möjlighet att tävla i Ylonz med samma laguppsättning igen. Men det är inget i användningen av DSOPAS samt gåtlösaren som specifikt kräver att man kan programmera. Dvs. om det är något annat Spektrum lag som känner sig intresserade av att pröva hur långt man kommer i Ylonz med lite teknikhjälp är det bara att ta kontakt. Som sagt påstår vi inte att programmen automatiskt leder till framgång, men får man tipsen löst snabbt och är färdig att springa, har man alla möjligheter att klara sig mycket väl. Spektrum har en fin vana att klara sig väl i Ylonz, en vana som började länge före oss. Vad tycker ni, nog skall vi väl hålla segern inom Spektrum några år till?

Jeremias

KÄLLOR:

http://en.wikipedia.org/wiki/Problem_solving

http://en.wikipedia.org/wiki/Watson_%28computer%29

http://mathworld.wolfram.com/TravelingSalesmanProblem.html

http://mathworld.wolfram.com/NP-HardProblem.html

http://staff.science.uva.nl/~ulle/teaching/comsoc/2012/slides/comsoc-complexity-tutorial.pdf

Spektrum rfs medlemstidning