optimalisatie netwerk

Moderators: jkien, Xilvo

Reageer
Gebruikersavatar
Berichten: 7.390

optimalisatie netwerk

Ik heb een netwerk van knopen. Elk knoop kan een waarde true of false hebben. Elke 'turn' vindt er een nieuwe evaluatie plaats waarbij de waarde van de knopen verandert. Deze verandering is consistent in die zin dat er geen knopen temidden van true-waarden een false zullen krijgen.

Ik zoek nu naar een algoritme dat naar de knoop beweegt die het aantal wegen maximaliseert, rekening houdend met de afstand tussen de knopen (die is verschillend tussen de verschillende knopen). Concreet zal ik eerder het pad kiezen naar een naburige knoop die op zijn beurt toegang geeft tot 4 toegankelijke knopen dan een pad naar een toegankelijke knoop die zelf maar naar 3 toegankelijke knopen leidt.

De moeilijkheid zit erin dat het soms beter is om niet naar de knoop met de meeste toegankelijke knopen te bewegen als die knoop op zijn beurt wel aanzienlijk meer mogelijkheden bevat.

Bestaan hier standaardoplossingen voor?

Alvast bedankt!
"C++ : Where friends have access to your private members." Gavin Russell Baker.

Gebruikersavatar
Berichten: 2.609

Re: optimalisatie netwerk

Ik denk dat je daarvoor Dijkstra nodig hebt (genereer alle paden die vertrekken vanuit een bepaald startpunt). En probeer het resultaat daarvan de maximaliseren, maar ik denk niet dat je dat je daar veel mee kan doen binnen de tijdslimiet die je hebt, das nogal duur om te berekenen.

Berichten: 7.068

Re: optimalisatie netwerk

Deze verandering is consistent in die zin dat er geen knopen temidden van true-waarden een false zullen krijgen.
Wat betekent dit?
Ik zoek nu naar een algoritme dat naar de knoop beweegt die het aantal wegen maximaliseert,
Wat tel je hier als weg?
Bestaan hier standaardoplossingen voor?
Waarschijnlijk niet. Dit is echter moeilijk met zekerheid te zeggen aangezien je omschrijving van je probleem nogal vaag is. Beschrijf exact wat je wilt.

Gebruikersavatar
Berichten: 7.390

Re: optimalisatie netwerk

Ik denk dat je daarvoor Dijkstra nodig hebt (genereer alle paden die vertrekken vanuit een bepaald startpunt). En probeer het resultaat daarvan de maximaliseren, maar ik denk niet dat je dat je daar veel mee kan doen binnen de tijdslimiet die je hebt, das nogal duur om te berekenen.
Mijn initiële gedacht, maar dan hoopte ik dat er iets minder duur zou bestaan ;)
Wat betekent dit?
Dat er niet temidden van een groep knopen met waarde 'true' bij de volgende turn een waarde 'false' zal staan. de veranderingen vinden plaats aan de grens tussen knopen met true-waarde en knopen met false-waarde.
Wat tel je hier als weg?
Als je uitgaat van een graaf, dan is elke verbinding tussen twee knopen een weg. Als een van de twee knopen een waarde false draagt, dan vervalt het als weg.
Beschrijf exact wat je wilt.
Iets als het volgende:

Neem de wegen in een stad als graaf. Ik ben een misdadiger en probeer agenten te ontwijken. Elke agent geef ik een invloedscirkel, en als die een kruispunt bevat, dan geef ik het kruispunt een waarde false. Om mijn positie zo goed mogelijk te houden om te kunnen ontsnappen, laat ik de misdadiger bewegen naar het kruispunt dat true draagt en dat het maximaal aantal ontspanningsroutes openhoudt.
"C++ : Where friends have access to your private members." Gavin Russell Baker.

Gebruikersavatar
Berichten: 2.609

Re: optimalisatie netwerk

In physics I trust schreef: wo 09 mei 2012, 22:49
Mijn initiële gedacht, maar dan hoopte ik dat er iets minder duur zou bestaan ;)


Je kan altijd eens testen met een beperkte afstand, dat zou moeten meevallen qua kost.

Berichten: 7.068

Re: optimalisatie netwerk

Moet ik het probleem zien als een potje Scotland Yard? (waarbij jij dan Mr. X. bent.)

Gebruikersavatar
Berichten: 7.390

Re: optimalisatie netwerk

Ja, exact (al was het me niet bekend onder die naam), maar dat is inderdaad waarover ik aan het nadenken ben.
"C++ : Where friends have access to your private members." Gavin Russell Baker.

Reageer