Csónak

A trivi megoldás az lenne, ha 10 km-t menne random irányba, majd egy kört a kiindulási helye körül. Csakhogy ez 10 + 10*2*PI távolság, ami durván 73 km. A trivi megoldást láttuk, kérdés, hogy hogyan lehetne ezen optimalizálni. Először is, kijelölök egy referencia irányt, (az ábrán felfelé), ez lenne az az irány, amelybe elindulnék a trivi megoldás esetén. Első opt. lehetőség: láthatóan fölösleges a teljes kört megtenni, jobb, ha egy Béta szöggel a kör vége előtt elhagyjuk azt, és egyenesen megyünk tovább. Teljes kör esetén a befejező szakasz hossza 2*Béta lenne, így elég tg(Béta)-t megtenni. Ki lehet számolni, a legtöbbet Béta=45 (PI/4 rad) foknál nyerünk. Második lehetőség: hasonló módszerrel tudunk nyerni utat az elején is, ha a ref. irányhoz képest Alfa szögben indulunk, és nem 10 km távolságba megyünk, hanem egy kicsit tovább, és 2*Alfa szögnél csatlakozunk be a körívbe. Itt egy kicsit más az optimum, mert az első egyenes eltávolodásnál is növekszik az út hossza. A becsatlakozásig 2*Alfa+1 út helyett (1/cos(Alfa))+tg(Alfa)-t kell megtenni. Itt Alfa=30 fokra (PI/6 rad) adódik az optimális megoldás. Így a teljes út hossza: 10km * (1/cos(PI/6) + tg(PI/6) + PI*7/6 + 1) = ... = = 10km * (1 + sqrt(3) + PI*7/6) = kb. 63,97 km Az út optimális, mert: az elején és a végén a legtávolabbi pontokba nem juthatunk el rövidebb úton, márpedig ezek a pontok feltétlen szükségesek ahhoz, hogy biztosak legyünk, nincs arra a part. A köríves szakaszon szintén nem lehet többet spórolni.

(Bocs, az ábra lemaradt!)

vissza