Benutzer-Werkzeuge
ss20:plagen-simulation
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen gezeigt.
| Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
|
ss20:plagen-simulation [2020/09/03 15:47] juanita.vos [3. Implementierung der Pestizide] |
ss20:plagen-simulation [2020/09/08 17:00] (aktuell) valentingiogoli [2.1 Performance Optimierung] |
||
|---|---|---|---|
| Zeile 115: | Zeile 115: | ||
| + | ===== 2.1 Performance Optimierung ===== | ||
| + | In der grundlegenden Implementierung des Algorithmus prüft jeder Boid alle anderen Boids aus der flock Liste, um zu berechnen, ob sie sich innerhalb eines vorgegebenen Radius befinden und somit als Nachbarn gelten. | ||
| + | Hierbei werden in jedem Schritt viele vermeidbare Berechnungen ausgeführt, weshalb der Code bei n > 50 Boids sehr langsam wird. Ohne weitere Bearbeitung wäre der Algorithmus sehr ineffizient mit einer Komplexität von O(n^2). | ||
| - | ===== 4. Implementierung der Gebiete ===== | + | Um dem Entgegen zu wirken haben wir uns entscheiden KD-Trees zu verwenden. KD-Trees sind Suchbäume um Punkte in einem k dimensionalen zu organisieren. In unserem Projekt ist k = 2. KD-Trees sind besonders praktisch für die Suche nach den nähsten Nachbarn oder der Suche innerhalb eines bestimmten Abstands. |
| + | In unserem Code haben wir sklearn library verwendet. Durch die Implementierung des KDTree aus sklearn.neighbors werden nur noch die Nachbarn eines Boids innerhalb eines Radius r = 50 betrachtet. | ||
| + | Hierdurch konnten wir, je nach verfügbarer Rechenleistung, Schwärme mit bis zu n = 500 Boids simulieren. | ||
| - | ===== 5. Fazit ===== | + | [[https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KDTree.html#sklearn.neighbors.KDTree| weitere Einzelheiten zu den KD-Trees von scikit-learn]] |
| + | |||
| + | ===== 3. Fazit ===== | ||
| Wir hatten uns mehr vorgenommen, als wir schlussendlich erreicht haben. Ursprünglich wir wollten eine interaktive Visualisierung von Heuschreckenplagen realisieren. Im Laufe der Zeit haben wir den interaktiven Aspekt etwas vernachlässigt und uns dafür auf die Simulation des Schwarmverhalten fokussiert. Dabei haben wir einiges über Schwärme und objektorientierte Programmierung in Phyton gelernt. | Wir hatten uns mehr vorgenommen, als wir schlussendlich erreicht haben. Ursprünglich wir wollten eine interaktive Visualisierung von Heuschreckenplagen realisieren. Im Laufe der Zeit haben wir den interaktiven Aspekt etwas vernachlässigt und uns dafür auf die Simulation des Schwarmverhalten fokussiert. Dabei haben wir einiges über Schwärme und objektorientierte Programmierung in Phyton gelernt. | ||
ss20/plagen-simulation.1599140869.txt.gz · Zuletzt geändert: 2020/09/03 15:47 von juanita.vos
Seiten-Werkzeuge
