Fórum: Találjunk jobb megoldást!

Nem csak ugyanazt az úthosszt (), hanem pont ugyanazt a rajzot is. Kiszámoltam a tiedet is, erre 7.557 jött ki.

Csak egy ötlet (nem számoltam utána): mi lenne, ha az ábrádon látható 4 db 120 fokos kereszteződést (ezek egy négyzet csúcsain vannak ugye) a leni538-féle, a 92. hsz-ben adott módon kötnénk össze? Ez automatikusan tartalmazná a középső pontot is, és rövidebb lenne a 90 fokos változatnál.

Ez nem hangzik rosszul. Viszont extra kereszteződésből nem lehet nagyon sok, legyen belőlük k. A 9 csúcs mindegyike legalább elsőfokú, az extra csúcsok pedig garantáltan 3-adfokúak, különben el lehet őket hagyni. A csúcsok száma 9+k, és mivel fáról van szó, az élek száma 8+k. Másrészt a fokszámokra adott alsó becslések összegének fele mindenképp alulról becsli az élek számát, tehát:

(9+3k)/28+k

Innen k7, legfeljebb ennyi extra kereszteződés lehet a minimális összhosszú hálózatban (általában, n terminál-csúcs esetén is igaz, hogy (n+3k)/2n+k-1, ahonnan kn-2).

Sirpi: Ha a közepét kijavítod, akkor ugyanazt az úthosszt kapod, mint jonas.

Én találtam egyet, ami egész jó, de még mindíg csak kb. 7,55-öt tud.

Szerintem erre lehetne írni programot ami megközelítőleg megoldaná. Itt található egy jegyzet: http://www.cs.elte.hu/ frank/jegyzet/kombalg.ps 31.oldalon az 5.példa dinamikus programozásra a Steiner fa probléma. Arról szól hogy adott egy G irányítatlan gráf. Minden élnek van egy költsége. Illetve ki van jelölve csúcsoknak egy T halmaza (terminálok). És olyan minimális költségű összefüggő részgráfot keresünk, mely tartalmazza a terminál csúcsokat. Az algoritmus ami itt szerepel a gráf csúcsszámában polinomiális idejű, |T|-ben exponenciális, de az most mindegy, mert jelen esetben |T|=9 konstans. És akkor lehetne azt csinálni hogy csinálunk egy jó sűrű beosztást (mondjuk 100 egyenlő részre osztjuk az egységet, ekkor lesz 40000 "rácspontunk", mindegyiknek megfeleltetjük a gráf egy csúcsát), bármely két csúcs között menjen él és a költsége legyen a két pont távolsága (a koordinátákból Pit. tétellel gyorsan számoolható). Akkor az algoritmus megadná a legrövidebb úthálózatot melyben az út szakaszok végpontjai e közül a 40000 rácspont közül kerülnek ki, ez szerintem már elég finom lenne, hogy megsejtsünk valamit (pl. hogy az eddig megtalált megoldás az optimális). Ma reggel vizsgáztam ebből a tárgyból, azért is jutott eszembe, meg ezért is vagyok fáradt és néztem be a Sin/Cos-t az előbb :-P

Áhh nem jó :-( Sin van a Cos helyett :-)

Na, az nem lenne rossz.

Én is kb. arra jutottam, mint amiket eddig írtatok (kivéve ezt az új legjobb eredményt). Ezt a képet azért beteszem, mert annyi mindenképp látszik belőle, hogy ez a 4^.1,937,72-es (nem túl jó) eredmény tovább javítható, hiszen vannak benne 90^o-os szögek, amiket ha kicserélünk egy 120^o-os 3-as útkereszteződésre, akkor a széleken változik meg a szög így ott lehet tovább javítani stb. Bár azt ki kellene számolni, hogy ennek az ábrának a javítás utáni "határértéke" milyen eredményt ad.

Ha nem néztem el, akkor lehet csinálni

~ 6.38134

hosszút is.

Másrészt vegyük észre, hogy ha egy négyzetnek csak három csúcsát kell összekötni, akkor ezt 1.93185 hosszúságú úttal megtehetjük. Ez lehet, hogy segít a nehezebb feladatban.

Akkor kilenc városra biztosan elég, de lehet, hogy kevesebbel is megoldható.

A könnyebbik kérdésre szerintem a válasz és itt az úthálózat. A közbülső kereszteződésekben mindenkébb 120°-osak az utak által bezárt szögek, mivel ezek a pontok megfelelő háromszögek izogonális pontjai.

Kezdeném egy egyszerű feladattal:

Adott 4 város, egy négyzet négy csúcsában, a négyzet oldala 1km. Mennyi a minimális úthálózat hossza, ha el akarunk jutni bármely városból bármely másikba? Értelemszerűen beiktathatunk további kereszteződéseket.

Ezután pedig az igazi kérdés: Mennyi a minimális úthálózat hossza, ha 9 városunk van egy 3x3-as rácsba rendezve és a szomszédos városok távolsága 1km?

Köszi! Éreztem, hogy ennek jobbnak kell lennie :-)

s=0,9265+

Egy átfedést nem korrigáltam. Gyanús is volt. De a gratuláció jogos.

Gratulálok!

s=0,9911+

És ez mennyi?

Lefele kell tolni, vagy fölfele? Én azt sem látom, milyen alakúak lesznek a részek az eltolásnál.

Most vizsgálom a függőleges eltolást, s javítható. Ha nem rontottam el valamit, akkor már s=0,89 fölött van.

Középen van és alul érint. Nincs forgatva és vízszintesen eltolva, mert azok két oldalt is csökkentenek. Az ilyen faladatok legjobb megoldása sokszor lokális szimmetriát igényel. Talán vizsgálatm a fölfelé eltolást, de már nem emlékszem. Ez már akkor megvolt, amikor föltettem. Másrészt, ha más változókat is behozok, rengeteg esetet kellene megvizsgálnom, s erre sem időm, sem idegrendszerem nincs. Egy elmozdításból következő változások végig vitele rossz esetben pár percig is eltarthat. Így általában a megérzésem után a legcélravezetőbbnek tűnő irányban haladok. Tisztában vagyok vele persze, hogy ezzel bizony akár a jó megoldás mellett szépen el is mehetek.

Itt a kék rész középre van igazítva, vagy lokálisan is elmozgattad úgy, hogy a kapott terület maximális legyen? Három szabadsági foka van, valahogy talán lehet javítani, csak akkor az alakja is nagyon ronda lesz.

Ja, 0.0014-gyel :-) De még kicsit agyolok a dolgon, hátha megdönthető a rekord.

Ezek szerint ez tényleg rosszabb a fejsze alakú megoldásnál.

A magasságot én körülbelül 0.260147-nek választanám, mert valahol itt maximális, itt a terület 0.292354, aminek a háromszorosa 0.877061.

Hú de megszapodorodtak a hsz-ek :-) Mindig olyanra reagálok, ami már rég nem aktuális, de sebaj.

Igen, így tényleg jobb, akkor az enyém sztornó :-)

Viszont Jonas 0.2918-at írt 1/4-es magasság mellett az előző ötletemre, az 3-mal felszorozva 0.8754, lehet, hogy máshogy választva meg a vastagságot kijön belőle még 0.003-as növelés...