Matematické Fórum

↑ 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?

Skrytý text:

↑ 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

↑ Cheop:
Tvoje riesenie nemeni nic na dlzke ciest

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.