Mycket av det som g\u00f6rs i Gumt\u00e4kt och speciellt i Exactum handlar om n\u00e5gon form av probleml\u00f6sning. Redan under grundkursen i Analys presenteras man varje vecka med \u00e5tminstone sex problem man f\u00f6rv\u00e4ntas kunna l\u00f6sa. Problemen f\u00f6rf\u00f6ljer studerandena genom hela kandidat-,\u00a0 magisterexamen och f\u00f6r vissa \u00e4ven in i forskningsv\u00e4rlden. Ofta kritiseras dessa problem; jag \u00e4r n\u00e4stan s\u00e4ker p\u00e5 att s\u00e5 gott som alla som studerat matematik eller data har i n\u00e5got skede av studierna tyckt att problemen som skall l\u00f6sas \u00e4r helt f\u00f6r artificiella, eller abstrakta f\u00f6r att vara intressanta: vem bryr sig om varf\u00f6r man inte f\u00e5r dela med 
Varje probleml\u00f6sning b\u00f6rjar med ett problem. I v\u00e5rt fall b\u00f6rjade vi fr\u00e5n f\u00f6ljande scenario:<\/p>\n T\u00e4nk dig att du och tv\u00e5 av dina v\u00e4nner vid en given tidpunkt har f\u00e5tt en lapp med g\u00e5tor vars l\u00f6sningar \u00e4r sex olika barer i Helsingfors. Er uppgift \u00e4r, att snabbare \u00e4n 200 andra grupper p\u00e5 3 m\u00e4nniskor, ta er till alla av dessa sex barer, inmundiga 1.5l \u00f6l p\u00e5 varje st\u00e4lle, sedan ta er till Otn\u00e4s och inmundiga 1.5l \u00f6l till. Som f\u00e4rdmedel f\u00e5r endast allm\u00e4ntransport anv\u00e4ndas.\u201d<\/em> F\u00f6r enkelhetens skull kommer jag fr\u00e5n och med nu kalla detta scenario f\u00f6r \u201dProblem Y\u201d.<\/p>\n Probleml\u00f6sning i sig \u00e4r ett forskningsomr\u00e5de inom kognitiv psykologin. Inte ov\u00e4ntat s\u00e5 verkar det inte finnas ett absolut svar p\u00e5 fr\u00e5gan ”hur skall man g\u00f6ra f\u00f6r att l\u00f6sa problem?”. Det finns dock vissa standardtekniker f\u00f6r probleml\u00f6sning som dyker upp i olika unders\u00f6kningar. Den man ofta b\u00f6rjar med inom matematik och datavetenskap kallas abstraktion. Abstraktion g\u00e5r ut p\u00e5 att exakt definiera vad man f\u00f6rs\u00f6ker \u00e5stadkomma, samt identifiera vilka delar av den information man har som beh\u00f6vs f\u00f6r att utveckla en l\u00f6sning. Dessutom brukar man under abstraktion ofta identifiera begr\u00e4nsningar som s\u00e4tts p\u00e5 de metoder man kan anv\u00e4nda i sin l\u00f6sning. Ett s\u00e4tt att beskriva problemet efter abstraktion \u00e4r genom att anv\u00e4nda orden ”INPUT” f\u00f6r att beskriva den (viktiga) informationen man har, \u201dOBJECTIVE\u201d f\u00f6r att beskriva det man f\u00f6rs\u00f6ker \u00e5stadkomma och \u201dCONSTRAINTS\u201d f\u00f6r att beskriva de begr\u00e4nsningar ens l\u00f6sning m\u00e5ste f\u00f6lja. D\u00e5 det kommer till problem Y lyckades vi inte komma p\u00e5 ett s\u00e4tt att anv\u00e4nda (lagliga) datavetenskapliga\/matematiska metoder f\u00f6r att hj\u00e4lpa oss med inmundigandet av INPUT: startst\u00e4lle, g\u00e5tor till 6 barer<\/p>\n OBJECTIVE: Kortast m\u00f6jligast tid f\u00f6r att l\u00f6sa g\u00e5torna, ta sig runt till barerna och sedan ta sig till Otn\u00e4s.<\/p>\n CONSTRAINTS: Endast allm\u00e4nna f\u00e4rdmedel till\u00e5tna.<\/p>\n Efter abstraktion \u00e4r det sedan dags att b\u00f6rja s\u00f6ka en l\u00f6sning. En inom psykologin identifierad och inom Exactum utl\u00e4rd teknik f\u00f6r probleml\u00f6sning kallas divide and conquer<\/em>. Id\u00e9n \u00e4r att spj\u00e4lka upp ett komplext problem i mindre delar i hopp om att delarna skall vara l\u00e4ttare att l\u00f6sa. Ofta str\u00e4var man till att delproblemen \u00e4r oberoende av varandra, d\u00e5 kan n\u00e4mligen alla delproblem l\u00f6sas samtidigt.\u00a0 I b\u00e4sta fall kan optimala l\u00f6sningarna av delproblemen sen kombineras f\u00f6r att \u00e5stadkomma en optimal l\u00f6sning p\u00e5 ursprungliga problemet. Det finns ett ganska naturligt s\u00e4tt att dela in Y: l\u00f6sningen av g\u00e5torna samt best\u00e4mmande av rutten. Visserligen \u00e4r dessa tv\u00e5 problem inte riktigt oberoende, man kan inte best\u00e4mma rutten innan man har l\u00f6st alla barer. Vi best\u00e4mde oss \u00e4nd\u00e5 f\u00f6r att dela in Y s\u00e5h\u00e4r i hopp om att g\u00e5tl\u00f6saren skulle bli tillr\u00e4ckligt effektiv f\u00f6r oss att ha n\u00e5gon nytta av rutl\u00f6saren.\u00a0 Olyckligt nog visade det sig att g\u00e5tl\u00f6sning h\u00f6gst troligen \u00e4r f\u00f6r sv\u00e5rt f\u00f6r oss att automatisera. Det finns en dator vid namnet Watson som har\u00a0 lyckats sl\u00e5\u00a0 de b\u00e4sta m\u00e4nniskorna p\u00e5 Jeopardy, men att \u00e5stadkomma detta tog 7 \u00e5r f\u00f6r IBM:s topp ingenj\u00f6rer. F\u00f6r att vara effektiv m\u00e5ste Watson dessutom k\u00f6ras parallellt p\u00e5 70 datorer samtidigt. Eftersom vi inte k\u00e4nde f\u00f6r att b\u00f6rja b\u00e4ra omkring p\u00e5 70 datorer samt inte hade 7 \u00e5r att s\u00e4tta p\u00e5 projektet, var det b\u00e4sta vi kunde hoppas p\u00e5 ett hj\u00e4lpmedel f\u00f6r g\u00e5tl\u00f6sning, inte en automatisering. Det vill s\u00e4ga, vi skulle inte kunna kombinera l\u00f6sningarna av delproblemen f\u00f6r att f\u00e5 en optimal l\u00f6sare av Y. Liknande fenomen sker ofta inom datavetenskap\/matematik. Ifall ursprungliga problemet man l\u00f6ser \u00e4r \u201dtillr\u00e4kligt sv\u00e5rt\u201d kan man inte kombinera dell\u00f6sningarna f\u00f6r att \u00e5stadkomma en optimal l\u00f6sning. Men ofta visar det sig att den (lite s\u00e4mre) l\u00f6sningen man \u00e5stadkommer \u00e4nd\u00e5 \u00e4r \u201dtillr\u00e4kligt bra\u201d, vilket ocks\u00e5 kommer att vara fallet med Y. Resten av denna text kommer att koncentrera sig p\u00e5 rutt-l\u00f6snings problemet: ”givet 6 barer samt en startposition hitta snabbaste s\u00e4ttet att ta sig till alla 6 barer och Otn\u00e4s med hj\u00e4lp av allm\u00e4ntransport”. Detaljerna av g\u00e5tl\u00f6saren kommer eventuellt att publiceras i ett senare skede (l\u00e4s: ifall jag inte f\u00e5r en b\u00e4ttre id\u00e9 f\u00f6r en h\u00f6startikel).<\/p>\n D\u00e5 man s\u00f6ker efter en l\u00f6sning till ett ovanligare problem \u00e4r det alltid inte klart att det man f\u00f6rs\u00f6ker g\u00f6ra \u00e4r sv\u00e5rt. Detta kan vara bra att ta reda p\u00e5;\u00a0 det \u00e4r r\u00e4tt s\u00e5 on\u00f6digt att utveckla hemskt komplicerade l\u00f6sningar till problem som egentligen (bevisligen) \u00e4r simpla. \u201dHur sv\u00e5rt kan det vara?\u201d var allts\u00e5 n\u00e4sta fr\u00e5ga vi st\u00e4llde oss. En systematisk analys av olika problems sv\u00e5righet \u00e4r ett delomr\u00e5de inom komplexitetsteori och \u00e4r ett forskningsomr\u00e5de f\u00f6r sig. Tekniska detaljer \u00e5sido s\u00e5 g\u00e5r analyserna av problemsv\u00e5righeter ofta ut p\u00e5 att man f\u00f6rliknar sitt problem med andra k\u00e4nda problem som man vet \u00e4r sv\u00e5ra\/l\u00e4tta. Ofta \u00e4r dessa k\u00e4nda problem relativt abstrakta, mest p.g.a. att det skall vara enklare att se likheterna mellan dem och det egna problemet. D\u00e5 det kommer till v\u00e5rt problem: \u201dgivet en start position, 6 barer samt ett m\u00e5l, hitta snabbaste rutten till alla\u201d finns det ett relativt k\u00e4nt problem som man enkelt kan j\u00e4mf\u00f6ra med, n\u00e4mligen traveling salesman problem<\/em> (TSP). I ursprungliga formuleringen av TSP ing\u00e5r en f\u00f6rs\u00e4ljare som skall bes\u00f6ka alla st\u00e4der i Tyskland och\/eller Schweiz (ursprunget \u00e4r oklart) i hopp om att s\u00e4lja sina varor i var och en. Uppgiften \u00e4r att f\u00f6rs\u00f6ka hitta den kortaste m\u00f6jliga rutten att g\u00f6ra detta. I en mer abstrakt formulering av TSP\u00a0 har man en matematisk graf best\u00e5ende av n\u00e5got antal noder och kanter d\u00e4r varje kant har en given l\u00e4ngd. M\u00e5let \u00e4r att hitta den kortaste m\u00f6jliga rutten genom grafen som bes\u00f6ker varje nod \u00e5tminstone en g\u00e5ng. Ruttl\u00f6sningen f\u00f6r problem Y kan ses som travelling salesman d\u00e4r noderna i grafen \u00e4r de 8:a olika platserna som skall bes\u00f6kas och l\u00e4ngden p\u00e5 en kant mellan tv\u00e5 noder \u00e4r tiden som det tar att ta sig mellan dem med allm\u00e4ntransport. Denna j\u00e4mf\u00f6relse mellan problemen \u00e4r tillr\u00e4cklig f\u00f6r v\u00e5rt behov, men inte helt fullst\u00e4ndig, vilket vi kommer att m\u00e4rka lite senare.<\/p>\n <\/p>\n Efter att man \u201dk\u00e4nt igen\u201d sitt problem kan man sen dra slutsatser p\u00e5 huruvida man kan f\u00f6rv\u00e4nta sig att det g\u00e5r att komma fram till en l\u00f6sning som fungerar inom en rimlig tid. I v\u00e5rt fall skulle ju en rutt-l\u00f6sare inte hj\u00e4lpa hemskt mycket ifall det skulle ta 5 timmar att anv\u00e4nda den. Olyckligt nog \u00e4r traveling salesman ett NP-sv\u00e5rt problem. Igen tekniska detaljer \u00e5sido, betyder detta att det i allm\u00e4nna fallet knappast finns ett effektivt s\u00e4tt att l\u00f6sa TSP. Tur i oturen kommer dessa teoretiska begr\u00e4nsningar emot endast d\u00e5 man \u00f6kar m\u00e4ngden noder i grafen. Med andra ord s\u00e5 g\u00e5r det troligtvis inte att koda en effektiv ruttl\u00f6sare f\u00f6r att komma till 100 barer. Men detta var ju inte vad vi var ute efter; v\u00e5ra levrar skulle \u00e4nd\u00e5\u00a0 inte st\u00e5 ut med s\u00e5 mycket \u00f6l. Att l\u00f6sa rutten till 6 barer\u00a0borde d\u00e4remot inte vara en utmaning, ens \u00e5t Lasses minil\u00e4pp\u00e4re. Vi kunde allts\u00e5 forts\u00e4tta p\u00e5 projektet trots vissa teoretiska begr\u00e4nsningar.<\/p>\n Efter all f\u00f6rberedning visade sig sj\u00e4lva kodandet av ruttl\u00f6saren var relativt l\u00e4tt. Efter lite unders\u00f6kning m\u00e4rkte vi n\u00e4mligen att HSL bjuder p\u00e5 ett gratis gr\u00e4nssnitt till sin reittiopas, vilket i princip betyder att programmerandet av en normal reittiopas skulle (n\u00e4stan) kunna vara en uppgift under ohjelmoinnin jatkokurssi. Inspirerade av detta samt de tidigare teoretiska funderingarna d\u00f6pte vi v\u00e5r ruttl\u00f6sare till Drunken Salesman Opas (DSOPAS). Under kodandet av DSOPAS st\u00f6tte vi egentligen endast p\u00e5 ett till problem som f\u00f6rhindrade oss fr\u00e5n att l\u00f6sa rutten optimalt. Problemet har att g\u00f6ra med j\u00e4mf\u00f6relsen av v\u00e5rt problem och TSP. D\u00e5 det kommer till allm\u00e4n transportation kan det ju n\u00e4mligen h\u00e4nda att tiden det tar att komma fr\u00e5n bar X till Y \u00e4r olika beroende p\u00e5 vilken tid p\u00e5 dagen man reser. Mera matematiskt formulerat s\u00e5 \u00e4r l\u00e4ngden av varje kant i grafen inte konstant. Detta betyder att f\u00f6r en optimal l\u00f6sning av v\u00e5rt problem borde reittiopas ”fr\u00e5gas” skilt f\u00f6r vikten av alla kanter i varje rutt m\u00f6jlighet som unders\u00f6ks. I en rutt ing\u00e5r N\u00e4st borde vi kanske anlita en grafisk designer…<\/p>\n Efter att man l\u00f6st sitt problem s\u00e5 \u00e5terst\u00e5r ett sista steg: verifikation av l\u00f6sningen. Fast\u00e4n vi kunde testa DSOPAS p\u00e5 p\u00e5hittade rutter, var vi tvungna att v\u00e4nta p\u00e5 \u00e5rets Ylonz (som de flesta av er s\u00e4kert har fattat \u00e4r det Ylonz detta handlar om) innan vi kunde veta hur bra det skulle fungera p\u00e5 riktigt. (F\u00f6r att vara helt \u00e4rlig blev v\u00e4ntandet inte hemskt l\u00e5ngt, sista buggarna i DSOPAS fixades onsdagen innan Ylonz l\u00f6rdagen). Jag kommer inte att prata s\u00e5 hemskt mycket om hur det gick, m\u00e5nga av er vet det redan och f\u00f6r resten kan ju n\u00e4mnas att v\u00e5rt lag hette \u201d<script>alert (\u2018TechSupported\u2019);<\/script>\u201d samt att resultaten finns h\u00e4r<\/a>. Jag p\u00e5st\u00e5r inte att DSOPAS var \u00e4nda orsaken till att resultaten ser ut som de g\u00f6r, men jag kan med st\u00f6rsta s\u00e4kerhet s\u00e4ga att den tillsammans med v\u00e5rt g\u00e5tverktyg nog hj\u00e4lpte betydligt.<\/p>\n Det fanns en bar i \u00e5rets Ylonz rutt som fungerar v\u00e4l som exempel f\u00f6r nyttan vi hade av b\u00e5da verktygen:\u00a0 Park hotell. D\u00e5 vi, baserat p\u00e5 bilden av ett monopolhotell, slog in \u201dhotell\u201d i g\u00e5tl\u00f6saren var \u201dPark hotell\u201d det enda alternativet vi fick ut. Dumma som vi var trodde vi inte p\u00e5 v\u00e5rt eget program, men fortsatte ist\u00e4llet fundera.\u00a0 Fem minuter senare hade vi l\u00f6st resten av tipset och kom fram till att g\u00e5tl\u00f6saren hade r\u00e4tt fr\u00e5n b\u00f6rjan. Senare, d\u00e5 vi kom fram till baren, visade sig att den l\u00e5nga k\u00f6n skulle f\u00f6rhindra oss fr\u00e5n att hinna p\u00e5 den bussen som DSOPAS hade best\u00e4mt \u00e5t oss tidigare. D\u00e5, detta under tidigare \u00e5r skulle ha lett till en massa spekulationer p\u00e5 vad vi borde g\u00f6ra n\u00e4st, kunde vi nu helt enkelt mata in de \u00e5terst\u00e5ende barerna i DSOPAS p\u00e5 nytt. Den nya rutten vi fick av v\u00e5rt program visade sig sist och slutligen vara lika snabb som den f\u00f6rsta vi hade f\u00e5tt.<\/p>\n Den h\u00e4r texten har egentligen tv\u00e5 syften. Den ena \u00e4r ett exempel p\u00e5 hur \u201dviktiga problem\u201d\u00a0 kan modeleras och l\u00f6sas genom abstrakta vetenskapliga metoder. Den andra kan sammanfattas i form av en utmaning. \u00c5tminstone 1\/3 av laget TechSupported kommer inom snarast framtid att f\u00f6rsvinna utomlands och det verkar som vi inte kommer att ha m\u00f6jlighet att t\u00e4vla i Ylonz med samma lagupps\u00e4ttning igen. Men det \u00e4r inget i anv\u00e4ndningen av DSOPAS samt g\u00e5tl\u00f6saren som specifikt kr\u00e4ver att man kan programmera. Dvs. om det \u00e4r n\u00e5got annat Spektrum lag som k\u00e4nner sig intresserade av att pr\u00f6va hur l\u00e5ngt man kommer i Ylonz med lite teknikhj\u00e4lp \u00e4r det bara att ta kontakt. Som sagt p\u00e5st\u00e5r vi inte att programmen automatiskt leder till framg\u00e5ng, men f\u00e5r man tipsen l\u00f6st snabbt och \u00e4r f\u00e4rdig att springa, har man alla m\u00f6jligheter att klara sig mycket v\u00e4l. Spektrum har en fin vana att klara sig v\u00e4l i Ylonz, en vana som b\u00f6rjade l\u00e4nge f\u00f6re oss. Vad tycker ni, nog skall vi v\u00e4l h\u00e5lla segern inom Spektrum n\u00e5gra \u00e5r till?<\/p>\n Jeremias<\/p>\n K\u00c4LLOR:<\/p>\n http:\/\/en.wikipedia.org\/wiki\/Problem_solving<\/a><\/p>\n http:\/\/en.wikipedia.org\/wiki\/Watson_%28computer%29<\/a><\/p>\n http:\/\/mathworld.wolfram.com\/TravelingSalesmanProblem.html<\/a><\/p>\n http:\/\/mathworld.wolfram.com\/NP-HardProblem.html<\/p>\n http:\/\/staff.science.uva.nl\/~ulle\/teaching\/comsoc\/2012\/slides\/comsoc-complexity-tutorial.pdf<\/p>\n","protected":false},"excerpt":{"rendered":" Mycket av det som g\u00f6rs i Gumt\u00e4kt och speciellt i Exactum handlar om n\u00e5gon form av probleml\u00f6sning. Redan under grundkursen i Analys presenteras man varje vecka med \u00e5tminstone sex problem man f\u00f6rv\u00e4ntas kunna l\u00f6sa. Problemen f\u00f6rf\u00f6ljer studerandena genom hela kandidat-,\u00a0 magisterexamen och f\u00f6r vissa \u00e4ven in i forskningsv\u00e4rlden. Ofta kritiseras dessa problem; jag \u00e4r n\u00e4stan … Forts\u00e4tt l\u00e4sa Probleml\u00f6sning \u2013 sagan om att overkilla<\/span> ![\"very-hard-riddles\"](\"https:\/\/spektraklet.files.wordpress.com\/2014\/06\/very-hard-riddles.jpg\")
<\/a><\/p>\n<\/a>Intressant nog betyder abstraktion inom konst oftast inte ”g\u00f6ra saker klarare”.<\/p>\n<\/a> <\/a><\/p>\n<\/a> <\/a><\/p>\n