Hirdetés

  2. Fórumok
  3. Szoftverfejlesztés
  4. Programozás topic
  5. (kiemelt téma)
Legfrissebb anyagok
Mobilarena témák
PROHARDVER! témák
IT café témák
GAMEPOD témák

Új hozzászólás Aktív témák

  • P.H. P.H. senior tag
    #6947
    #6934 #89874944
    Új Válasz
    Új hozzászólás
    Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra
    P.H.
    P.H.
    senior tag
    #6934 #89874944
    #6934 #89874944

    Sziasztok!

    Az lenne a feladat, hogy adott pontokat(csomópontok, node) úgy kéne összekötni, hogy egy gyűrűt alkossanak.
    gyűrű topológia
    [minden csomópontnak pontosan két szomszédja van és a gyűrű körbe is ér]

    A pontok véletlenszerűen vannak leszórva.
    Akár olyan algoritmus is jó lenne, ami lerakás közben működik. Persze az lenne az igazi, ha már elhelyezett pontokat is össze tudna kötni gyűrűbe.

    Bárhogy próbálom, minden ötletem befuccsol vhol.
    Az alap ötlet volt, hogy mindig a legközelebbi pontot kösse be. Ez már akkor elvérzik, ha az egyik irányba a sűrű pontok mentén halad, ott elfogynak a pontok, és vissza kell térnie. (a topológiában nem lehetnek keresztező vonalak. Metszéspont számító függvényem már kész van.)

    Bármilyen segítségnek örülök. :(

    Előre is köszi.

    A gyűrű azt jelenti, hogy a lehető legrövidebb a 2D-távolság az összekötött pontok között, azaz az összekötések összhossza minimális, ezzel visszavezetted a TSP (Traveling Salesman Problem) szituációra a kérdést, ez pedig NP-teljes. Letehetsz róla, hogy egyszerűbb algoritmust találsz a pontos megoldásra, mint a TSP, ez a bonyolultságelmélet szépsége, a visszavezethetőség. NP-teljes problémára pedig n pont esetén - ahogy cucka és Jester01 is írta - n! nagyságrendű (azaz nem polinomiális) műveletigényű általános megoldás van. Ha találsz egyet, ami polinomiális lesz, akkor esély van a matematikai Nobel-díjra és pár egyéb nagy összegű pénzdíj elnyerésére is. :)

    Persze lehet keresni részben másképp is megoldást, nem kell végigpróbálni az összes n! megoldást - a metszés jó ötlet -, de akkor is kiszámíthatatlan lesz az időigény (pl. felveszel 100 pontot, arra x idő alatt talál megoldást a programod; elveszel belőle 20-at, azaz 80 marad és 3x-osára nő az időigénye).

Új hozzászólás Aktív témák