Konzeptsuche: Abstandsberechnung vieler Agenten

SimProtect

Aktives Mitglied
Hallo Leute,
Ich habe wieder mal ein Problem mitgebracht.

Ich arbeite an einer Multiagentensimulation, die ihre Grundparameter aus aktuellen Geodaten bezieht.
Wir sprechen hier von ca. 25.000 Agenten pro Simulation.
Dabei handelt es sich bereits um die reduzierte Anzahl, aber auch gleichzeitig um die Mindestvorgabe. Weiter dürfen wir nicht runtergehen, weil die Simulation dadurch an Aussagekraft verlieren würde - so zumindest unsere Analysten........ - mir macht diese Zahl an Agenten Bauchschmerzen.

Im Rahmen der Simulation interagieren die Agenten jeweils mit dem Agenten, der ihnen am nächsten ist. (Interaktionen sind hierbei sowohl Bewegungen, als auch z.B. Kommunikation).
Dazu muss jeder Agent natürlich zunächst einmal herausfinden, welcher Agent denn der nächste ist.
Und genau hier liegt mein Problem:
Verschiedene Operationen kosten bereits viel Rechenzeit und machen die Simulation dementsprechend langsam.
Ich möchte daher vermeiden, dass jeder Agent zu Beginn jeder Aktionsrunde erstmal durch alle anderen Agenten iterieren muss. Das wären dann 25.000 x 24.999 abfragen und das in jeder einzelnen Runde...

Jetzt suche ich nach einem möglichst effizienten Konzept, diese Abfrage durchzuführen. Hat da einer eine gute Idee für mich?

Im Wesentlichen kann ich von jedem Agenten die Koordinate (x,y) erhalten.
 

stg

Top Contributor
Das ist ein Standard-Problem und längst gelöst.
Mittels Delaunay-Triangulierung deines Graphen kannst du alle nächsten Nachbarn (gleichzeitig) in Quasi-Linearer Zeit (hier n*log(n)) bestimmen. Besser geht's auch nicht.

Unter den Stichworten
  • nearest neighbour seach
  • Delaunay triangulation

findest du alles, was du brauchst. Mit Sicherheit auch fertige Lösungen in Java. Bei konkreten Fragen, frag gerne noch einmal nach!
 
Zuletzt bearbeitet:

SimProtect

Aktives Mitglied
Hoppala... da war ich offensichtlich zu blöde, eine vernünftige Suchanfrage bei Google zu formulieren. Wieder mal viel zu verquer gedacht -.-

Danke auf alle Fälle für den Input. Ich bin sicher, dass das schon ausreichend wird.

Ich bitte an dieser Stelle die unnötige Frage zu entschuldigen. Offensichtlich waren Hirn und Verstand schon im Bett.
Beim nächsten Mal werde ich vorher eine Nacht darüber schlafen - das hätte das Problem sicherlich auch gelößt ^^

Lieben Gruß und nochmals vielen, vielen Dank.
 

Neue Themen


Oben