Avatar billede peterfa Nybegynder
09. december 2007 - 17:39 Der er 1 kommentar og
1 løsning

Algoritme spg, balanceret rooted træ fra uni-directional graf

Hej

Har et spg der på sin vis nok er off-topic, idet det mere handler om algoritmer end en opgave i java. Java er dog sproget jeg sidder og roder med det i, og har tidligere set at der er nogle skarpe hoveder herinde, så håber det går =)

Jeg sidder og arbejder med et problem, hvor jeg har en uni-directional graf der beskriver netværksknuder og forbindelser mellem dem. En af disse knuder er en gate-way node, og mit problem er nu at få dannet et distributions-træ således at data fra alle noder indirekte, eller direkte, kan nå gate-way noden. Dette træ skal dog ikke være et arbitrært spanning-tree, men skal søge at optimere "belastningen" på de enkelte edges.

Jeg vil med andre ord gerne konstruere et spanning-tree med rod i gateway noden, og hvor hvert subtræ (set fra gateway-noden) har nogenlinde ligemange nodes. (Denne optimering kan så gælde flere niveauer ud også). Har været ved at google lidt for forskellige netværks optimerings algoritmer, men har ikke kunne finde en der har dette optimeringskriterie. Nogle ideer til hvordan man kan angribe dette problem?
Avatar billede peterfa Nybegynder
09. december 2007 - 17:44 #1
For lige at præcisere. Det primære kriterie er ikke, som ofte er tilfældet, at minimere længden af ruten til målet. Længere ruter er fortrukne, hvis det kan udjævne mængden af trafik der går igennem en node, således at de får nogenlinde ligelig belastning.
Avatar billede peterfa Nybegynder
15. april 2008 - 16:22 #2
Lukker
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester