Springen naar inhoud

optimalisatie netwerk


  • Log in om te kunnen reageren

#1

In physics I trust

    In physics I trust


  • >5k berichten
  • 7384 berichten
  • Moderator

Geplaatst op 08 mei 2012 - 18:10

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.

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 08 mei 2012 - 22:07

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.

#3

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 09 mei 2012 - 07:12

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.

#4

In physics I trust

    In physics I trust


  • >5k berichten
  • 7384 berichten
  • Moderator

Geplaatst op 09 mei 2012 - 21:49

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.

#5

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 09 mei 2012 - 22:07

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.

#6

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 10 mei 2012 - 07:34

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

#7

In physics I trust

    In physics I trust


  • >5k berichten
  • 7384 berichten
  • Moderator

Geplaatst op 12 mei 2012 - 14:48

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.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures