Matematické Fórum

check_drummer · 23. 05. 2019 22:13

Ahoj,
při hře s míči mě napadl tento úkol:
V rovině jsou dány 4 body. Přesuňte je tak, aby tvořily vrcholy čtverce a aby součet vzdáleností, o které byly posunuty, byl co nejmenší.
Úlohu lze zobecnit, např. uvažovat vážený součet vzdáleností nebo obecně "odpor" terénu, kdy v každém bodě roviny je dána jakási funkce "neprostupnosti" (a pak může být výhodnější posuvat bod nikoli po úsečce, ale po nějaké křivce).

VaK · 03. 01. 2020 22:00

Dobrý den,
úloha mě zaujala., tak jsem si (za dlouhých zimních večerů) udělal prográmek
(ve Fortranu), který ji řeší podle následujícího algoritmu:
Vybereme 2 body (tj. 6 možností) a doplníme na čtverec (tj. celkem 6*3=18
možností. U každého čtverce zjistíme součet vzdáleností (minimální ze všech
kombinací). Minimum z těchto hodnot určuje čtverec - tzv. první přiblížení.
Pak kolem příslušných 2 bodů uděláme mřížky s určitým krokem (na př. 5*5 bodů,
vybereme vždy 2 body (tj. 25*25 možností a určíme (stejným způsobem, jak bylo
popsáno dříve) tzv. druhé přibližné řešení. Mohou nastat 2 případy: oba optimální
body jsou uvnitř mřížky, pak kolem těchto bodů uděláme jemnější mřížku a
pokračujeme předchozím způsobem, nebo nějaký z bodů je na kraji mřížky, pak
tento bod zařadíme do výběru a pokračujeme se stejnou mřížkou, až budou oba
body uvnitř mřížky. Tím dostaneme řešení s libovolnou přesností.
Pozn.: když další zjemňování mřížky vede na stejné výsledky, tak máme
konečné přesné řešení.
Na ukázku několik příkladů:

Zadane body:
2.0000000000E+00 2.0000000000E+00
7.0000000000E+00 1.0000000000E+00
7.0000000000E+00 6.0000000000E+00
3.0000000000E+00 1.0000000000E+01

Vychozi body:
2.0000000000E+00 2.0000000000E+00
7.0000000000E+00 1.0000000000E+00

Hledany ctverec:
2.0000000000E+00 2.0000000000E+00
7.0000000000E+00 1.0000000000E+00
8.0000000000E+00 6.0000000000E+00
3.0000000000E+00 7.0000000000E+00
SUMMIN= 4.0000000000E+00

----------------------------------------------

Zadane body:
2.0000000000E+00 2.0000000000E+00
7.0000000000E+00 1.0000000000E+00
1.2000000000E+01 6.0000000000E+00
3.0000000000E+00 1.0000000000E+01

Vychozi body:
7.0000000000E+00 1.0000000000E+00
3.0000000000E+00 1.0000000000E+01

Hledany ctverec:
5.6000000000E-01 3.0800000000E+00
7.4800000000E+00 6.4000000000E-01
9.9200000000E+00 7.5600000000E+00
3.0000000000E+00 1.0000000000E+01
SUMMIN= 5.0000000000E+00

----------------------------------------------

Zadane body:
2.0000000000E+00 2.0000000000E+00
7.0000000000E+00 1.0000000000E+00
9.0000000000E+00 5.0000000000E+00
3.0000000000E+00 1.0000000000E+01

Vychozi body:
2.0000000000E+00 2.0000000000E+00
9.0000000000E+00 5.0000000000E+00

Hledany ctverec:
2.0000000000E+00 2.0000000000E+00
7.1764615000E+00 2.9410050000E-01
8.8823610000E+00 5.4705620000E+00
3.7058995000E+00 7.1764615000E+00
SUMMIN= 4.1231056258E+00

V tomto případě to ale není přesné řešení.
Postupné iterace jsou:

2.0000000000E+00 2.0000000000E+00
7.1000000000E+00 1.0000000000E-01
9.0000000000E+00 5.2000000000E+00
3.9000000000E+00 7.1000000000E+00
SUMMIN= 4.1419838040E+00

2.0000000000E+00 2.0000000000E+00
7.1500000000E+00 2.5000000000E-01
8.9000000000E+00 5.4000000000E+00
3.7500000000E+00 7.1500000000E+00
SUMMIN= 4.1241958953E+00

2.0000000000E+00 2.0000000000E+00
7.2000000000E+00 3.0000000000E-01
8.9000000000E+00 5.5000000000E+00
3.7000000000E+00 7.2000000000E+00
SUMMIN= 4.1240868782E+00

2.0000000000E+00 2.0000000000E+00
7.1800000000E+00 3.0000000000E-01
8.8800000000E+00 5.4800000000E+00
3.7000000000E+00 7.1800000000E+00
SUMMIN= 4.1231259520E+00

2.0000000000E+00 2.0000000000E+00
7.1750000000E+00 2.9500000000E-01
8.8800000000E+00 5.4700000000E+00
3.7050000000E+00 7.1750000000E+00
SUMMIN= 4.1231129538E+00

2.0000000000E+00 2.0000000000E+00
7.1765000000E+00 2.9450000000E-01
8.8820000000E+00 5.4710000000E+00
3.7055000000E+00 7.1765000000E+00
SUMMIN= 4.1231057190E+00

2.0000000000E+00 2.0000000000E+00
7.1765000000E+00 2.9450000000E-01
8.8820000000E+00 5.4710000000E+00
3.7055000000E+00 7.1765000000E+00
SUMMIN= 4.1231057190E+00

2.0000000000E+00 2.0000000000E+00
7.1765000000E+00 2.9430000000E-01
8.8822000000E+00 5.4708000000E+00
3.7057000000E+00 7.1765000000E+00
SUMMIN= 4.1231056439E+00

2.0000000000E+00 2.0000000000E+00
7.1764500000E+00 2.9415000000E-01
8.8823000000E+00 5.4706000000E+00
3.7058500000E+00 7.1764500000E+00
SUMMIN= 4.1231056284E+00

2.0000000000E+00 2.0000000000E+00
7.1764500000E+00 2.9405000000E-01
8.8824000000E+00 5.4705000000E+00
3.7059500000E+00 7.1764500000E+00
SUMMIN= 4.1231056278E+00

2.0000000000E+00 2.0000000000E+00
7.1764500000E+00 2.9407000000E-01
8.8823800000E+00 5.4705200000E+00
3.7059300000E+00 7.1764500000E+00
SUMMIN= 4.1231056267E+00

2.0000000000E+00 2.0000000000E+00
7.1764550000E+00 2.9408500000E-01
8.8823700000E+00 5.4705400000E+00
3.7059150000E+00 7.1764550000E+00
SUMMIN= 4.1231056261E+00

2.0000000000E+00 2.0000000000E+00
7.1764600000E+00 2.9410000000E-01
8.8823600000E+00 5.4705600000E+00
3.7059000000E+00 7.1764600000E+00
SUMMIN= 4.1231056258E+00

2.0000000000E+00 2.0000000000E+00
7.1764615000E+00 2.9410050000E-01
8.8823610000E+00 5.4705620000E+00
3.7058995000E+00 7.1764615000E+00
SUMMIN= 4.1231056258E+00

Je vidět, že konvergence je poměrně slušná.

Ačkoli uvedený algoritmus místy používá hrubou sílu je výpočet krátký,
např. poslední příklad trvá 0.078 s.

Ale, jak pravil klasik, sotva vyřešíš jednu úlohu už zas tu máš jiné, např.:
- je nalezené minimum globální nebo lokální,
- když jsou zadané body mřížové, v jakém případě jsou i body čtverce mřížové,
- shoduje se v zadaných bodech a bodech čtverce alespoň jeden bod,
- lze analyticky vyjádřit souřadnice čtverce v posledním případě
pro přesné řešení,
- atd.

S pozdravem VaK.

Bati · 04. 01. 2020 21:34 — Editoval Bati (04. 01. 2020 21:35)

↑ VaK:
Ahoj,
a jak vis, ze prvni krok vybere ty spravne body? Tomu moc neverim...

↑ check_drummer:
Nevim, jestli sis to pocital, ale vyjde to hezky, pokud misto klasicke vzdalenosti vezmes jen ctverce (tj. vynechas odmocniny). Pak se da vsechno napsat vzoreckem i pro libovolny pocet bodu. V ostatnich pripadech se ale obbavam, ze bude potreba nejaka fixed point iterace nebo nejaky pseudovypocet typu ↑ VaK:

MichalAld · 04. 01. 2020 23:10

Vidím to jako Bati. Pokud by kritérium nebylo "součet vzdáleností" ale "součet druhých mocnin vzdáleností" tak by to mohlo jít i analyticky. Ony se ty absolutní hodnoty blbě derivují...

Takto je to standardní výpočet vázaného extrému. Tj

$Q = (\Delta A_x)^2 + (\Delta A_y)^2 + (\Delta B_x)^2 + (\Delta B_y)^2 + ...$

K tomu musíme přidat ještě ty vazební podmínky, že body tvoří čtverec. To já přesně nevím, jak to elegantně matematicky popsat, předpokládám, že by mohlo stačit, že délky všech stran jsou stejné (takže i druhé mocniny délek všech stran budou stejné) a navzájem ortogonální. Nevím.

A pak klasika - Lagrangeovy multiplikátory, zderovovat podle těch 8 posunutí, a vyřešit soustavu 8 algebraických rovnic (což určitě půjde velmi snadno, hi...).

Nebo vyjádřit čtverec pomocí 4 parametrů (x, y, délka uhlopříčky a natočení) - a napsat kriteriální funkci Q přímo pro tyhle 4 parametry. Ta už pak bude bez vazebních podmínek.

Tohle lze řešit minimálně numericky - například iterovat ve směru gradientu, nevidím důvod, proč by to nemělo jít...

Já mmch řeším zrovna podobnou úlohu - akorát že ten čtverec (či mnoho úhelník) je pevně daný, a potřebuji jen najít pozici, kde budou jeho vrcholy k těm zadaným bodům nejblíže. Věc ale komplikuje to, že není dáno, které body si mají navzájem odpovídat - tedy že nemám body A, A', B, B', C, C' .... musí se vzít bod, co je v daném místě nejblíž ... a to je trochu problém, protože se to musí pro každou pozici znova hledat (který bod je každému vrcholu nejblíž).

Bati · 05. 01. 2020 00:41

↑ MichalAld:
Lag. multiplikatory v tehle situaci je silenost, ctverec je urcen 4 cisly, jak pak pises - stred, polomerem kr. opsane a uhel natoceni. Pak proste polozis
$\nabla_{(S_1,S_2,r,\alpha)}\sum_k\|A_k-(S+r(\cos(\alpha+\tfrac{2\pi k}n),\sin(\alpha+\tfrac{2\pi k}n)))\|^2=0$
a jednoduchy strankovy vypocet ti da $S_1,S_2,r,\alpha$ . Zadna numerika. Ta by byla potreba az kdyz se vezme "neprirozena" metrika.

Taky moc nechapu v cem je tva uloha obtiznejsi... co presne hledas? Uhel natoceni daneho (pravidelneho?) mnohouhelniku, jeho polomer? Co vsechno je fixni?

VaK · 05. 01. 2020 20:37

Dobrý den,
upravil jsem ten prográmek na hledání minima součtu kvadrátů vzdáleností
a dostal jsem samozřejmě jiné řešení, ale také na mřížových bodech.
Porovnáme-li obě řešení pro první příklad:

Zadane body:
2.0000000000E+00 2.0000000000E+00
7.0000000000E+00 1.0000000000E+00
7.0000000000E+00 6.0000000000E+00
3.0000000000E+00 1.0000000000E+01

Hledany ctverec pri minimu souctu vzdalenosti:
2.0000000000E+00 2.0000000000E+00
7.0000000000E+00 1.0000000000E+00
8.0000000000E+00 6.0000000000E+00
3.0000000000E+00 7.0000000000E+00
SUMMIN= 4.0000000000E+00

Hledany ctverec pri minimu souctu kvadratu vzdalenosti:
1.2500000000E+00 2.7500000000E+00
6.7500000000E+00 1.2500000000E+00
8.2500000000E+00 6.7500000000E+00
2.7500000000E+00 8.2500000000E+00
SUMMIN= 6.5000000000E+00

Jestli někdo budete dělat analytické řešení, zkuste přepočítat tento příklad.
Zdá se mi, že i při hledání minima součtu vzdáleností by mohlo mít rozumný
tvar, protože (v tomto případě) vychází "kulatá" čísla (:-)).
S pozdravem VaK.

MichalAld · 05. 01. 2020 22:56

Bati napsal(a):
... co presne hledas? Uhel natoceni daneho (pravidelneho?) mnohouhelniku, jeho polomer? Co vsechno je fixni?

No, máš nějaký N-úhelník (to N bude v řádu stovek až tisíců), jinak řečeno máš dáno těch N bodů, v nějaké rovině ...a pak máš jiných obecně M bodů v jiné rovině...

Cílem je ten N-úhelník umístit tak (tj najít x, y a natočení) aby "co nejvíce odpovídal" tomu druhému M-úhelníku.

Slovně řečeno - máš jednu čmáranici na papíře, a druhou na druhém - a je třeba je umístit na sebe tak, aby si co nejvíce odpovídaly.

VaK · 10. 01. 2020 17:36

Dobrý den,
analytický výpočet podle Bati (drobně modifikováno) pro případ součtu kvadrátů
vzdáleností:
Označme souřadnice zadaných bodů: pi , qi , i= 1 - 4
a souřadnice vrcholů hledaného čtverce: xi , yi, ,i= 1 - 4
Pak můžeme např. vybrat souřadnice 2 diagonálních bodů čtverce jako parametry.
Označme je (x1,y1) , (x3,y3). Pak další body čtverce mají souřadnice:
x2=( x1-y1+x3+y3)/2 y2=( x1+y1-x3+y3)/2
x4=( x1+y1+x3-y3)/2 y4=(-x1+y1+x3+y3)/2
Z podmínek nulových parciálních derivací dostaneme přímo vztahy pro souřadnice
vrcholů hledaného čtverce (je zajímavé, že se všechno vyruší a zůstane - jak
píše Bati - jen vztah pro hledanou proměnnou):
x1=(2p1+p2+q2+p4-q4)/4 y1=(2q1-p2+q2+p4+q4(/4
x2=(2p2+p1-q1+p3+q3)/4 y2=(2q2+p1+q1-p3+q3)/4
x3=(2p3+p2-q2+p4+q4)/4 y3=(2q3+p2+q2-p4+q4)/4
x4=(2p4+p1+q1+p3-q3)/4 y4=(2q4-p1+q1+p3+q3)/4
Z těchto vztahů vyplývá, že hypotéza o mřížových bodech platí.
Pozor: vztahy jsou odvozeny za předpokladu určité orientace vrcholů, takže
pro jistotu je třeba zadat různé kombinace pořadí a z výsledků určit minimum.
S pozdravem VaK.

Matematické Fórum

#1 23. 05. 2019 22:13

Posuň body a získej čtverec

#2 03. 01. 2020 22:00

Re: Posuň body a získej čtverec

#3 04. 01. 2020 21:34 — Editoval Bati (04. 01. 2020 21:35)

Re: Posuň body a získej čtverec

#4 04. 01. 2020 23:10

Re: Posuň body a získej čtverec

#5 05. 01. 2020 00:41

Re: Posuň body a získej čtverec

#6 05. 01. 2020 20:37

Re: Posuň body a získej čtverec

#7 05. 01. 2020 22:56

Re: Posuň body a získej čtverec

Bati napsal(a):

#8 10. 01. 2020 17:36

Re: Posuň body a získej čtverec

Zápatí