Matematické Fórum

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
!! 17.06.2018 (Jel.) Khanova škola zve nadšence ke spolupráci na překladech návodů pro učitele a rodiče.
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
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

#1 23. 05. 2019 22:13

check_drummer
Příspěvky: 2794
Reputace:   75 
 

Posuň body a získej čtverec

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).


Jak dokázat, že nelze dokázat, že dané tvrzení nelze dokázat?

Offline

 

#2 03. 01. 2020 22:00

VaK
Příspěvky: 37
Reputace:   
 

Re: Posuň body a získej čtverec

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.

Offline

 

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

Bati
Příspěvky: 2227
Reputace:   176 
 

Re: Posuň body a získej čtverec

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

Offline

 

#4 04. 01. 2020 23:10

MichalAld
Moderátor
Příspěvky: 2372
Reputace:   73 
 

Re: Posuň body a získej čtverec

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íž).

Offline

 

#5 05. 01. 2020 00:41

Bati
Příspěvky: 2227
Reputace:   176 
 

Re: Posuň body a získej čtverec

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

Offline

 

#6 05. 01. 2020 20:37

VaK
Příspěvky: 37
Reputace:   
 

Re: Posuň body a získej čtverec

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.

Offline

 

#7 05. 01. 2020 22:56

MichalAld
Moderátor
Příspěvky: 2372
Reputace:   73 
 

Re: Posuň body a získej čtverec

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.

Offline

 

#8 10. 01. 2020 17:36

VaK
Příspěvky: 37
Reputace:   
 

Re: Posuň body a získej čtverec

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.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson