Tri mestečká A,B,C ležia na spoločnej priamke, pričom vzdialenosť A a B je 2 a vzdialenosť B a C je tiež 2. Je potrebné vybudovať systém koľajníc, po ktorých bude nepretržite premávať vlak z A do B, z B do C, z C do A, z A do B atď. Konštrukcia vlaku (s lokomotívou len na jednom konci) si vyžaduje, aby zakrivenie koľajníc nebolo nikde väčšie ako 1, čím myslíme to, že žiadne tri blízke body na koľajnici nebudú ležať na kružnici, ktorá má polomer menší ako 1. Takže koľajnice môžu napríklad pozostávať z "hladko nadväzujúcich" úsečiek a častí kružníc s polomerom aspoň 1. Jeden možný návrh koľajníc je na ilustračnom obrázku. Nájdite taký systém koľajníc, ktorý umožní vlaku urobiť v priebehu dňa čo najväčší počet návštev všetkých troch miest. Na celkovej dĺžke koľajníc nezáleží a na železničnej trati môžu byť mosty a výhybky, nie však zariadenie na otáčanie vlaku do opačného smeru.
Táto úloha je samozrejme jednoduchá, avšak hľadanie najkratšej krivky s ohraničenou krivosťou prechádzajúcej zadanými bodmi je vo všeobecnosti veľmi ťažká úloha. (Upozorňujem, že riešením nášho problému, tak ako je formulovaný, nemusí byť jediná nepretínajúca sa sa krivka.) Keď Vás napadne nejaká iná úloha z tejto kategórie, budem rád, ak nám ju napíšete do komentárov.
3 komentáre:
Co takto dve kruznice kolajnic s priemerom 2 cez A+B a B+C, spojene dvomi useckami dlzky 2 na vrcholoch?
tiez ma napadlo to co Leva...
Lev, Rori: Ospravedlňujem sa za neskorú reakciu; máme tu ďalšiu konferenciu a aj inak je tu dosť veľa zhonu a roboty.
Máte pravdu, toto riešenie sa zdá byť optimálne, hoci dokázať, že je skutočne najlepšie, je asi veľmi ťažké. Zábavné je, že ak by týmto spôsobom chodil vlak, tak by prichádzal do každej stanice raz z jednej, raz z druhej strany.
Keď budem mať čas (možno cez vákend) pokúsim sa na túto tému vymyslieť trochu ťažšiu úlohu.
Zverejnenie komentára