Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Je zadán libovolný počet bodů, každý z nich je určen svou x a y souřadnicí.
Máme nalézt takový bod, že součet vzdáleností od tohoto bodu ke každému z dříve zadaných bodů, bude co nejmenší. Navíc "cesty" mezi těmi body mohou jít pouze pravoúhle. Zároveň ten bod, který musíme určit může být jeden z těch již zadaných, ale většinou to tak není.
Např. pro tuhle množinu zadaných bodů má vyjít nejmenší součet vzdáleností 237.
A[-90; 10]
B[ 84; 73]
C[ 57; 10]
Nevíte někdo co s tím? Potřeboval bych jenom malinko nakopnout, protože vůbec nevím jak na to. Řešení je údajně triviální.
Offline
Ahoj ↑ vuic:,
Pri citani tvojho problemu ( skoro z rekreacnej matematiky) ma napadlo ci nejde o spojenie dvoch bodov trojuholnika a vysku z tretieho bodu ( to je ta kolmost)
A z troch moznosti treba vybrat tu "najkratciu"
No urob vypocty
Offline
↑ vuic:
Můžeš, prosím tě, nakreslit pro to tvé zadání jak se vlastně může chodit?
(ten bod nemusíš nakreslit přesně, ale není jasné co se myslí "Navíc "cesty" mezi těmi body mohou jít pouze pravoúhle".
Myslí se to takto?
Offline
↑ Honzc:
Obecně se to myslí takto - viz obrázek
Hledaný bod je bod P a minimální vzdálenost je součet e až j
(Tady ten bod splyne s bodem C) - ještě nevím proč, ale zamýšlím se nad tím
Offline
↑ Honzc:
ano presne si aplikoval moju myslienku
S cim robis tie obrazky?
Offline
↑ Cheop:
Tvoje riesenie nemeni nic na dlzke ciest
Offline
Jde o tzv. taxikářskou metriku, kde vzdálenost dvou bodů [a,b] a [c,d] se bere jako |a-c|+|b-d|.
Pak je jasné, že se stačí zaměřovat na jednotlivé souřadnice (netřeba kombinovat x a y, jak by to bylo potřeba například při spojování bodů úsečkama).
Jsou-li tedy ve hře body Ai = [xi, yi] pro i = 1 až n, pak pro souřadnice hledaného bodu P = [px, py] musí nezávisle na sobě platit:
|x1 - px| + |x2 - px| + |x3 - px| + ... + |xn - px| --> min
|y1 - py| + |y2 - py| + |y3 - py| + ... + |yn - py| --> min
Stačí si tedy uvědomit, že minimum těch funkcí vlevo (jedna proměnné px a druhá proměnné py) se realizuje v některém z nulových bodů těch absolutních hodnot (grafem je lomená čára). No a teď se bavme o tom, v kterém.
Offline
↑ Honzc:
Představ si, že ty body jsou v mřížce a cesty mohou vést pouze po "čarách" té mřížky
↑ musixx:
Díky moc!
Co třeba si zvlášť seřadit x-ové souřadnice všech bodů a jako px vybrat medián, to samé udělat u y-ových souřadnic?
S tím, že u lichého počtu zadaných bodů vyberu hodnotu na místě (n+1)/2
Edit: Tak funguje mi to jak jsem psal :)
najdu si takhle ten bod a celkovou vzdálenost pak zjišťuju |px - x[i]| + |py - y[i]|
Díky za pomoc ;)
Offline