Matematické Fórum

halogan · 26. 08. 2011 17:44

Dobrý den,

mě tak napadá. Mějme skupinu lidí, která bydlí ve městě, známe GPS souřadnice jednotlivých bydlišť. A teď bychom chtěli nějak naplánovat sraz, nejlépe tak, aby se dohromady ujelo co nejméně kilometrů. Napadá mě:

Pokud hledáme jeden konkrétní bod (či více): Jednoduše si vyjádřit vzdálenosti každého od bodu [x,y] (zakřivení země zanedbejme, GPS souřadnice převedeme do plochy) a budeme derivovat součet podle x, pak y a nějak to zoptimalizujeme. Teoreticky.

Pokud hledáme oblasti, kde dále hledat vhodný podnik: Nechat si vizualizovat heatmapu, která by ukazovala součet vzdáleností od všech účastníků. (Tady by to podlě mě šlo jako nějaký mashup s využitím vlastních map na Google Maps.)

Pokud nehledíme jen na průměrnou spokojenost: Problém je, když sice 99 lidí pojede 3 minuty, ale poslední bude cestovat 3 hodiny. Jestli to nepojímat lineárně, ale spíš nějak... nevím jak.

---

Určitě se to řešilo 100x někde na internetech, tak mě kdyžtak nějak naveďte. Asi to bude nějaká základní úloha z lineárního programování (bohužel jsem neměl a mít nebudu, takže ocením jednodušší materiál).

Díky a hezký zbytek srpna přeji.

Stýv · 26. 08. 2011 19:20

s metodou nejmenších čtverců (least squares) ses už určitě setkal;)

Honzc · 26. 08. 2011 20:35

↑ halogan:
Zdravím,
nevím nevím, nedjdeš na to moc složitě? Jestli to chceš dělat pro plánované setkání, tak já jsem to tady zkoušel spočítat a dělal jsem to docela jednoduše. Spočítal jsem průměry (vážené) z jednotlivých GPS souřadnic pro každou souřadnici (x,y) zvlášť.

Pavel Brožek · 26. 08. 2011 21:41

↑ Honzc:

Obyčejný průměr je přesně to, co vyjde po minimalizaci součtu čtverců jednotlivých vzdáleností. :-)

Nechť (x,y) jsou souřadnice setkání a $(x_i,y_i)$ souřadnice bydliště i-tého účastníka. Pak

$\frac{\partial$\sum_{i=1}^{n}\sqrt{(x-x_i)^2+(y-y_i)^2}^2$}{\partial x}=\sum_{i=1}^{n}2(x-x_i)=2$nx-\sum_{i=1}^{n}x_i$$

Z podmínky nulovosti derivace v minimu máme

$x=\frac1n\sum_{i=1}^n x_i$ .

Analogicky to vyjde pro y.

halogan · 27. 08. 2011 14:39

↑ Honzc:

Netýká se to srazu, mám to pro jinou situaci, ale chtěl jsem znát obecné řešení.

↑ Stýv:

Ano, ale brali jsme jich více a nevím, zda sem použít klasické OLS nebo nějakou jinou variantu.

↑ Pavel Brožek:

Ano, početně to je hezké, spíš mi jde o princip a výběr správné techniky. Jelikož to nebude děláno ručně, tak můžu použít i absolutní vzdálenosti a budu mít možná robustnější odhad. Asi záleží na počtu osob a požadované vlastnosti cílového bodu (zda brát tolik ohledy na outliery a tak).

---

Stále ještě přemýšlím nad tou heat mapou. Asi to trochu pogooglím, něco by už mělo být hotové.

Stýv · 27. 08. 2011 19:12

↑ halogan: není jediný správný řešení, je jenom na tobě, který si vybereš

halogan

↑ Stýv:

To mi je jasný, jde mi o nějaké osvědčené (případně víc jich), kde bych se dozvěděl o nějakých výhodách a nevýhodách (co se týče vhodnosti použití vzhledem k počtu osob, robustnost, ...).

Takové úlohy se většinou nějak jmenují (blízký je třeba obchodní cestující/dopravní problém) a člověk si o tom dost počte. Tak mě právě zajímalo, jestli se tomuhle taky nějak říká.

Stýv · 27. 08. 2011 20:02

↑ halogan: nepřijde mi, že by to mělo blízko k problému obchodního cestujícího nebo dopravnímu problému. navíc v těch úlohách je vždycky zřejmý, co je třeba minimalizovat a otázka je jak to upočítat. tebe naopak zajímá, jaký kriterium zvolit

Matematické Fórum

#1 26. 08. 2011 17:44

Nejkratší celková vzdálenost

#2 26. 08. 2011 19:20

Re: Nejkratší celková vzdálenost

#3 26. 08. 2011 20:35

Re: Nejkratší celková vzdálenost

#4 26. 08. 2011 21:41

Re: Nejkratší celková vzdálenost

#5 27. 08. 2011 14:39

Re: Nejkratší celková vzdálenost

#6 27. 08. 2011 19:12

Re: Nejkratší celková vzdálenost

#7 27. 08. 2011 19:24 — Editoval halogan (27. 08. 2011 19:24)

Re: Nejkratší celková vzdálenost

#8 27. 08. 2011 20:02

Re: Nejkratší celková vzdálenost

Zápatí