Máme n+1 miest, pričom n z nich leží na vrcholoch pravidelného n-uholníka vpísaného do jednotkovej kružnice a jedno mesto leží v počiatku súradnicovej sústavy. Chceme vybudovať čo najkratšiu cestnú sieť tak, aby sa po nej dalo prejsť z každého mesta do každého iného mesta. Pre n=3 samozrejme nič nenašpekulujeme a jednoducho spojíme každé okrajové mesto priamou cestou s centrálnym mestom, ako je znázornené na obrázku. Ako by sme však vybudovali najkratšiu cestnú sieť pre n=4 (t.j. celkovo päť miest) a pre n=6 (t.j. celkovo sedem miest)?
24 februára 2008
Najkratšie prepojenie
Máme n+1 miest, pričom n z nich leží na vrcholoch pravidelného n-uholníka vpísaného do jednotkovej kružnice a jedno mesto leží v počiatku súradnicovej sústavy. Chceme vybudovať čo najkratšiu cestnú sieť tak, aby sa po nej dalo prejsť z každého mesta do každého iného mesta. Pre n=3 samozrejme nič nenašpekulujeme a jednoducho spojíme každé okrajové mesto priamou cestou s centrálnym mestom, ako je znázornené na obrázku. Ako by sme však vybudovali najkratšiu cestnú sieť pre n=4 (t.j. celkovo päť miest) a pre n=6 (t.j. celkovo sedem miest)?
Prihlásiť na odber:
Zverejniť komentáre (Atom)
8 komentárov:
však pre n=4 to je tak ako aj pre n=3 (kazde vonkajsie mesto so stredom) a pre n=6 spojim prve so stvrtym (cez stred - siedme) a potom spojim druhe so siestym a tretie s piatym. (1-6 su porade tie vonkajsie)
ci je v tom nejaky figel?
No podľa mňa je to vlastne problém minimálnej kostry grafu. Mestá sú vrcholy, cesty sú hrany, ohodnotenie hrany je vzdialenosť dvoch miest, ktoré táto hrana spája. Na to sa dá použiť napr. Kruskalov algoritmus. Pre n=4 to vyjde rovnako ako pre n=3, teda každé okrajové mesto bude spojené so stredným, lebo polovica uhlopriečky štvorca je kratšia ako strana štvorca. Podobne pre n=5. Pre n=6 majú všetky hrany grafu rovnakú váhu, takže máme viacero možností, každá kostra tohto grafu je minimálna. Pre n>6 je už polomer opísanej kružnice dlhší ako strana n-uholníka, preto treba jedno okrajové mesto spojiť so stredovým, a potom vždy dve susedné okrajové, pričom jednu stranu n-uholníka vynecháme.
Aha, neuvedomila som si jednu dôležitú vec, treba vziať do úvahy kompletný graf, t.j. ako keby bolo každé mesto spojené s každým priamou cestou, a až potom aplikovať algoritmus!
Ale na výsledku to aj tak nič nezmení, ostatné hrany majú totiž väčšiu váhu...
Zdravím. Zadaná úloha nie je problém euklidovskej minimálnej kostry (hoci tieto dva problémy majú veľa spoločné). Príklad: keby som mal tri mestá A,B,C na vrcholoch rovnostranného trojuholníka (bez stredového mesta), tak minimálna cestná sieť, ktorá tieto tri mestá spája, nie je priama cesta z A do B plus priama cesta z B do C, ale spojenie všetkých troch miest s ťažiskom trojuholníka. T.j. v našom probléme môžeme mať "križovatky" aj mimo miest.
Ešte som zabudol dodať, že práve v tom je tento príklad zaujímavý, že optimálne riešenie pre n=4 už nie je také priamočiare ako pre n=3. Návrh pre n=6 z prvého komentáru je síce celkom dobrý, ale tiež nie optimálny. :-)
Týmto sa úplne mení môj pohľad na daný problém, hneď je to o dosť komplikovanejšie, vyriešiť to všeobecne pre každé n>3 asi vôbec nebude ľahké. Ale aspoň pre n=6 sa mi to podarilo trochu vylepšiť: 6-uholník, ktorého vrcholy tvoria okrajové mestá, sa dá rozdeliť na 6 rovnostranných trojuholníkov. Vyberiem si 3 také "nesusedné" trojuholníky a do ich ťažísk umiestnim križovatku. Každú z týchto troch križovatiek spojím so stredovým mestom a s dvoma okrajovými mestami, ktoré sú k nej najbližšie. Takáto cestná sieť bude mať dĺžku 3*sqrt(3), kým tá pôvodne navrhovaná v komentároch mala dĺžku až 6.
katka: správne. Pre n=6 je Tvoje riešenie optimálne. Mám ho na obrázku tu. Skoro (ale nie úplne) optimálnych riešení je veľa, napríklad tu a tu.
Zverejnenie komentára