Effizienz eines sequentiellen Prozesses

Question

Ich bin mir nicht sicher, ob dies eher eine Programmierfrage oder eine mathematische Frage ist. Bitte lassen Sie mich das richtige Forum wissen, in dem Sie dies fragen können, wenn dies nicht das richtige ist.

Ich habe einen sequentiellen Prozess wie folgt:

1. Es gibt $n$ Münzen in einem quadratischen Raster von verstreut $100 \times 100$ Punkte.
2. Es gibt $m$ Agenten an einem zentralen Ort, dh dem Punkt $(50,50)$.
3. Diese Agenten können einen zufälligen Spaziergang auf dem Gitter machen und einen Gitterpunkt in einem Schritt verschieben. In einem Zeitschritt bewegen sich alle Agenten einen Schritt von ihrer aktuellen Position.
4. Die Agenten sollen die Münzen finden. Sobald ein Agent eine Münze findet, wird der Zeitschritt notiert. Dann bewegt sich der Agent auf dem kürzesten Weg von dem Punkt, an dem die Münze gefunden wurde, zum zentralen Ort. Wiederum kann der Agent in einem Zeitschritt nur einen Gitterpunkt verschieben, während andere Agenten möglicherweise noch nach anderen Münzen suchen.
5. Sobald der Agent mit der Münze die zentrale Stelle erreicht hat, bleibt die Münze übrig und der Agent beginnt erneut, nach anderen Münzen zu suchen.
6. Der Vorgang wird beendet, wenn eine bestimmte Anzahl von Zeitschritten abgelaufen ist, unabhängig davon, ob alle Münzen gefunden wurden.

Im allgemeinen Prozess habe ich die Kontrolle über die Verteilung von Münzen, ob alle Agenten gleichzeitig oder zu bestimmten Zeitschritten abreisen und ob sie miteinander interagieren können, um die Erkundung desselben Gebiets zu reduzieren. Am Ende möchte ich herausfinden, wie schnell die Münzen von den Agenten gefunden werden. Ich suche nach einer Möglichkeit, diese Effizienz des Findens von Münzen im allgemeinen Fall von zu quantifizieren$n$ Münzen und $m$Agenten. Das heißt, wenn ich 10 Agenten, die 100 Münzen finden, mit 5 Agenten vergleichen möchte, die 50 Münzen finden, sollte diese Menge mir sagen können, in welchem ​​Fall die Agenten die Münzen effizienter gefunden haben. Ich kann den Prozentsatz der im Laufe der Zeit gefundenen Münzen darstellen, und dies ist normalerweise eine S-Kurve, aber wenn meine Parameter zunehmen, denke ich, wäre es besser, wenn ich einzelne Werte zum Vergleichen hätte, anstatt Linien zu zeichnen.

Meiner Meinung nach sind die drei Parameter, die bei der Bestimmung dieser Effizienz eine Rolle spielen würden, der Abstand einer Münze vom Zentrum, die Zeitschritte, die ein Agent benötigt, um die Münze vom Zentrum aus zu finden, und die Gesamtzahl der Agenten in der Gegend auf der Suche nach Münzen. Aber ich bin mir nicht sicher, was eine gute Möglichkeit wäre, sie miteinander in Beziehung zu setzen.

Answer 1

Teilantwort

Wir haben einen Gittergraphen $G$ mit einem identifizierten Knoten als zentralem Knoten, $c$.

Lassen $$N=V \space \text{\\} \space \{c\},$$ dh $N$ ist die Menge der Knoten von $G$ ohne $c$.

Lassen $$S = \{ p_n | p_n \text{is the shortest path between } c, n \in N \}$$

Wenn wir das Problem einschränken, indem wir die Anzahl der Agenten angeben $k$ das wird bereitgestellt wird bestimmt bei $t = 0$ und bleibt während der gesamten Simulation konstant, können wir wählen $$k = |S|$$

Dadurch wird jedem kürzesten Pfad ein Agent zugewiesen $p_n$ und wir können bestätigen, dass es keine Streitigkeiten zwischen Agenten gibt, die wir modellieren müssen.

Lassen $d_{n,0}, d_{n,1}, \dots, d_{n,j}$ seien die sortierten Abstände der Münzen von $c$ für den Weg $p_n$ dh $d_{n,j} < d_{n,j+1}$.

Betrachten Sie die Pfade $(c,x)$ und $(c,y)$. Wir könnten zwei Agenten auf diesen Wegen haben und sie hätten die Münzen bei sammeln können$x, y$beziehungsweise. Wer bekommt Priorität bei der Rückkehr zu$c$? Die Antwort ist, es spielt keine Rolle, da beide gleich weit voneinander entfernt sind$c$.

Daher gehen wir von der Konvention ohne Verlust der Allgemeinheit aus, dass der Agent auf dem kürzeren Pfad Vorrang hat. Dies hilft uns, unsere Berechnung zu vereinfachen.

Lassen $m_n$ sei die Anzahl der Münzen auf dem Weg $p_n$. Lassen$c_n$ ist die Anzahl der auf dem Weg gesammelten Münzen $p_n$.

$c_n$ wird eingeschränkt durch

$$\sum_{k=1}^{m_n} 2d_{n, k} \le t$$

Die Gesamtzahl der gesammelten Münzen ist gegeben durch

$$C = \sum_{i=1}^{n} c_i$$

Lassen $M$sei die Anzahl der Agenten. Dann ist die durchschnittliche Produktivität des Mittels gegeben durch

$$C \over M$$

Lassen $C_{total}$sei die Gesamtzahl der Münzen. Effizienz$(\eta)$ des Einsatzes in Bezug auf gesammelte Münzen wäre

$$\eta = {C \over C_{total} } \times 100 \text{%}$$

Prolog: Dies wird sehr kompliziert, wenn Sie mehr Agenten als die Anzahl der kürzesten Wege zu Münzen zulassen, da Sie dann modellieren müssten, wann diese Agenten das Feld betreten können, wie viele das Feld betreten können und wie sie mit dem primären Agenten auf dem Feld koordinieren kürzester Weg ohne Streit.

Theoretisch wird ein kürzester Weg von allen Münzen befreit (dies tritt auf, wenn $c_k < t$ für jeden $k$) können alle Pfade, die durch eine Kante mit ihr verbunden sind, sie verwenden, um wartende Agenten auszurichten. Sobald einer dieser Agenten in einiger Entfernung eine Münze sieht$x$ von dort auf einem verbundenen kürzesten Weg liegen $p_m$ und die Münze ist in einer Entfernung von $d_{n,r}$ und es gibt keine andere Münze zwischen dieser Münze und $c$ und der primäre Agent bewegt sich in Richtung $c$kann sich der wartende Agent bewegen, um diese Münze abzuholen.

In der obigen Abbildung $r$ ist ein Agent, der sich in Richtung bewegt $c$mit einer gesammelten Münze. Die hellblauen Knoten warten auf Agenten. Der Agent$a$ kann sich bewegen, um Münzen zu sammeln $j$ und folgen $r$.

Dies wird dazu beitragen, die Effizienz zu verbessern. Wir könnten den kürzesten Weg von einem wartenden Agenten zu einer Münze benutzen und den Agenten zu dieser Münze schicken. Dies wird jedoch sehr schnell komplex und ich bin mir nicht sicher, wie ich die Anzahl der gesammelten Münzen auf einfache Weise berechnen kann.