Japp

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:



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



Således gäller att



För y gäller ett analogt resonemang.

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

Men det finns ju fem systembolag!

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.

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

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.

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?

Ok och vad heter gatan du vill bo på?

Bra, din algoritm verkar funka! :-)

på gatan

Russell skrev:

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

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