Meddelande

Du befinner dig just nu på en äldre version av Pluggakuten, gamla.pluggakuten.se. Nya Pluggakuten lanserades den 6 februari 2017 och du finner forumet på www.pluggakuten.se.

På gamla.pluggakuten.se kan du fortfarande läsa frågorna och svaren som ställts, men du kan inte skapa ett nytt konto eller nya trådar. Är du redan medlem kan du däremot fortfarande logga in och svara i befintliga trådar. Nya frågor och nytt konto skapar du på det nya forumet, välkommen dit!

Systembolagen

Peano
Medlem

Offline

Registrerad: 2015-09-17
Inlägg: 329

Systembolagen

God Jul på er! Så här i jultider ska vi tänka på samhällets olycksbarn lite extra. Här kommer ett litet problem på det temat.

Du har av socialen blivit tvångsförflyttad till en annan stad men där du i gengäld får välja fritt var du vill bo. Det enda du bryr dig om är att bo så nära stadens systembolag som möjligt. Du vet att när du väl blir portad från det närmaste systembolaget måste du börja gå till det näst närmaste, och när du blir portad även där måste du börja gå till det tredje närmaste osv. Därför vill du att den sammanlagda sträckan från din bostad till vart och ett av systembolagen i staden skall vara så litet som möjligt. Var ska du bo?


Man lär sig av sina misstag. Det gäller att göra så många som möjligt.
 
Luft
Medlem

Offline

Registrerad: 2014-09-18
Inlägg: 4794

Re: Systembolagen

En generell lösning eller?

Senast redigerat av Luft (2015-12-25 15:46)


A complicated thing is just a bunch of simple things put together.
 
Peano
Medlem

Offline

Registrerad: 2015-09-17
Inlägg: 329

Re: Systembolagen

Japp


Man lär sig av sina misstag. Det gäller att göra så många som möjligt.
 
sprite111
Medlem

Offline

Registrerad: 2011-02-08
Inlägg: 1002

Re: Systembolagen

[tar bort kommentaren då den inte hjälpte mkt.]

Senast redigerat av sprite111 (2015-12-25 19:16)


Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.
//John von Neumann
 
sthlmkille
Medlem

Offline

Registrerad: 2007-02-25
Inlägg: 1342

Re: Systembolagen

Antag att det finns n systembolag med koordinaterna (a_i, b_i), i=1,...,n. Bostadsortens koordinater betecknas (x,y).

Avståndet från bostadsorten till systembolag i är kvadratroten ur (a_i-x)^2 + (b_i -y)^2. Det är enklare att minimera kvadraten på avståndet och det ger även det minsta avståndet.

Uppgiften är att minimera det totala avståndet till de n systembolagen och vi väljer således att minimera det kvadratiska avståndet. Det ger följande uttryck att minimera:

LaTeX ekvation

Sätt derivatan med avseende på x till noll:

LaTeX ekvation

Således gäller att

LaTeX ekvation

För y gäller ett analogt resonemang.

 
Peano
Medlem

Offline

Registrerad: 2015-09-17
Inlägg: 329

Re: Systembolagen

Detta kan vara sant om det är fågelvägen till systembolagen du är intresserad av. Men du går till alla systembolag från din bostad i staden och flyger inte.


Man lär sig av sina misstag. Det gäller att göra så många som möjligt.
 
Henrik E
Medlem

Offline

Registrerad: 2015-09-22
Inlägg: 3189

Re: Systembolagen

Kvadratsummeinimum är inte detsamma som att minimera avståndssumman. Man kan till att börja med säga att bostaden måste ligga i en gatukorsning. För om den låg inne på gatan måste närmaste vägarna till gå åt ena eller andra hållet och eftersom 5 är udda är det flera närmstavägar åt ena hållet och då lönar det sej att flytta till den gatukorsningen. Gatukorsningen har minst tre vägar och närmstavägarna måste vara fördelade 2+2+1 eller 2+1+1+1 eller 1+1+1+1+1, annars skulle det löna sej att flytta åt majoritetens håll. Mycket mer kan man inte säga, vad jag kommer på. Det kan finnas lokala minima som inte är globala

 
Peano
Medlem

Offline

Registrerad: 2015-09-17
Inlägg: 329

Re: Systembolagen

Bostaden måste inte ligga i en gatukorsning. Om det tex bara finns två systembolag i staden och de ligger på samma gata så kan din port vara var som helst på gatan mellan systembolagen.


Man lär sig av sina misstag. Det gäller att göra så många som möjligt.
 
Henrik E
Medlem

Offline

Registrerad: 2015-09-22
Inlägg: 3189

Re: Systembolagen

Men det finns ju fem systembolag!

 
Peano
Medlem

Offline

Registrerad: 2015-09-17
Inlägg: 329

Re: Systembolagen

Vem har sagt att det finns fem systembolag? I vissa städer finns bara ett systembolag, i andra två osv. Kolla på en karta så ser du att antalet varierar från ort till ort.


Man lär sig av sina misstag. Det gäller att göra så många som möjligt.
 
Henrik E
Medlem

Offline

Registrerad: 2015-09-22
Inlägg: 3189

Re: Systembolagen

Ha! Läste jag så fel eller har texten redigerats? Ja om antalet inte behöver vara udda kan man nog inte säga mycket om lösningsmängden. Den kan bestå av flera osammanhängande gatstumpar och punkter.

 
Peano
Medlem

Offline

Registrerad: 2015-09-17
Inlägg: 329

Re: Systembolagen

Texten har inte redigerats.


Man lär sig av sina misstag. Det gäller att göra så många som möjligt.
 
Peano
Medlem

Offline

Registrerad: 2015-09-17
Inlägg: 329

Re: Systembolagen

Lösningsmängden är oberoende av om antalet systembolag är udda eller jämnt.


Man lär sig av sina misstag. Det gäller att göra så många som möjligt.
 
Henrik E
Medlem

Offline

Registrerad: 2015-09-22
Inlägg: 3189

Re: Systembolagen

Tre systembolag i (0,-1), (0,0) och (0,1), alla har raka vägar till (-1,0) och (1,0). Lösningen är två punkter, (-1,0) och (1,0). Kan man verkligen säga något generellt?

 
Peano
Medlem

Offline

Registrerad: 2015-09-17
Inlägg: 329

Re: Systembolagen

Ja man kan ju säga generellt att det finns minst en plats där du vill bo. Frågan är hur man hittar en sådan plats.


Man lär sig av sina misstag. Det gäller att göra så många som möjligt.
 
Henrik E
Medlem

Offline

Registrerad: 2015-09-22
Inlägg: 3189

Re: Systembolagen

Då skulle jag beräkna kortaste vägen från varje systembolag till varje korsning med Dijkstras algoritm. Det går i N log N om N är antal korsningar. Sen väljer jag den korsning som har lägst avståndssumma. Om mer än hälften av kortastevägarna kommer till korsningen via samma gata går jag in i den gatan och fram till första systembolag. Om det fortfarande är mer än hälften av kortastevägarna som går vidare går jag också vidare till nästa systembolag osv.

 
Peano
Medlem

Offline

Registrerad: 2015-09-17
Inlägg: 329

Re: Systembolagen

OK intressant! Visa gärna hur din algoritm fungerar i praktiken. Säg att det är Härnösand du skall tvångsförflyttas till. Var säger du då till socialsekreteraren att du vill bo?


Man lär sig av sina misstag. Det gäller att göra så många som möjligt.
 
Henrik E
Medlem

Offline

Registrerad: 2015-09-22
Inlägg: 3189

Re: Systembolagen

Jag läser in gatunätet som en graf med kantlängder och med korsningar och systembolag som hörn. Sen kör jag algoritmen och får veta vilken nod jag vill bo på.

 
Peano
Medlem

Offline

Registrerad: 2015-09-17
Inlägg: 329

Re: Systembolagen

Ok och vad heter gatan du vill bo på?


Man lär sig av sina misstag. Det gäller att göra så många som möjligt.
 
Henrik E
Medlem

Offline

Registrerad: 2015-09-22
Inlägg: 3189

Re: Systembolagen

Enligt min algoritm är bästa boplatsen Köpmangatan 1.

 
Peano
Medlem

Offline

Registrerad: 2015-09-17
Inlägg: 329

Re: Systembolagen

Bra, din algoritm verkar funka! :-)


Man lär sig av sina misstag. Det gäller att göra så många som möjligt.
 
Peano
Medlem

Offline

Registrerad: 2015-09-17
Inlägg: 329

Re: Systembolagen

Och om du blir tvångsförflyttad till Malmö eller Göteborg, var vill du bo då?


Man lär sig av sina misstag. Det gäller att göra så många som möjligt.
 
Robbas
Medlem

Offline

Registrerad: 2008-05-14
Inlägg: 4614

Re: Systembolagen

på gatan


Lajka Pluggakuten på Facebook!

Personlig hemsida finns här.
 
Russell
Moderator

Offline

Registrerad: 2013-08-22
Inlägg: 2608

Re: Systembolagen

Peano skrev:

Och om du blir tvångsförflyttad till Malmö eller Göteborg, var vill du bo då?

Systembolaget har hemleverans i både Gbg och Malmö. Problem solved. wink


The road to wisdom?—Well, it's plain and simple to express:
Err and err and err again, but less and less and less.
 
Robbas
Medlem

Offline

Registrerad: 2008-05-14
Inlägg: 4614

Re: Systembolagen

Russell skrev:

Systembolaget har hemleverans i både Gbg och Malmö. Problem solved. wink

whaaat.. måste finnas i sthlm också? måste kolla upp detta


Lajka Pluggakuten på Facebook!

Personlig hemsida finns här.
 


Sidfot

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson

Powered by Mattecentrum
 |  Denna sida använder cookies |  Kontakta oss |  Feedback |