Efficienza di un processo sequenziale

Question

Non sono sicuro che sia più una questione di programmazione o matematica. Per favore fatemi sapere il forum appropriato in cui chiedere questo, se questo non è quello giusto.

Ho un processo sequenziale come segue:

1. Ci sono $n$ monete sparse in una griglia quadrata di $100 \times 100$ punti.
2. Ci sono $m$ agenti in una posizione centrale, ovvero il punto $(50,50)$.
3. Questi agenti possono fare una passeggiata casuale sulla griglia, spostando un punto della griglia in un unico passaggio. In un passo temporale, tutti gli agenti si spostano di un passo dalla loro posizione attuale.
4. Gli agenti dovrebbero trovare le monete. Quando un agente trova una moneta, viene annotato il passo temporale. Quindi, l'agente procede a spostarsi nella posizione centrale lungo il percorso più breve dal punto in cui è stata trovata la moneta. Ancora una volta, in una fase temporale, l'agente può spostare solo un punto della griglia, mentre altri agenti potrebbero ancora cercare altre monete.
5. Una volta che l'agente con la moneta raggiunge la posizione centrale, la moneta viene lasciata e l'agente ricomincia a cercare altre monete.
6. Il processo si interrompe al termine di un numero specificato di fasi temporali, indipendentemente dal fatto che tutte le monete siano state trovate.

Nel processo generale, ho il controllo sulla distribuzione delle monete, se tutti gli agenti escono contemporaneamente o in determinate fasi temporali e se possono interagire tra loro per ridurre l'esplorazione della stessa area. Alla fine, voglio scoprire quanto velocemente vengono trovate le monete dagli agenti. Sto cercando un modo per quantificare questa efficienza di trovare monete nel caso generalizzato di$n$ monete e $m$agenti. Ciò significa che, se voglio confrontare 10 agenti che trovano 100 monete con 5 agenti che trovano 50 monete, questa quantità dovrebbe essere in grado di dirmi in quale caso gli agenti sono stati più efficienti nel trovare le monete. Posso tracciare la percentuale di monete trovate nel tempo, e questa di solito è una curva a S, ma man mano che i miei parametri aumentano, penso che sarebbe meglio se avessi valori singoli da confrontare piuttosto che linee di trama.

A mio parere, penso che i tre parametri che avrebbero un ruolo nel determinare questa efficienza sono la distanza di una moneta dal centro, i passi di tempo che un agente impiega per trovare la moneta partendo dal centro e il numero totale di agenti nell'area alla ricerca di monete. Ma non sono sicuro di quale sarebbe un buon modo per metterli in relazione tra loro.

Answer 1

Risposta parziale

Abbiamo un grafico reticolare $G$ con un nodo identificato come nodo centrale, $c$.

Permettere $$N=V \space \text{\\} \space \{c\},$$ cioè $N$ è l'insieme dei nodi di $G$ escluso $c$.

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

Se limitiamo il problema dicendo il numero di agenti $k$ che verrà distribuito è determinato in $t = 0$ e rimane costante durante tutta la simulazione, possiamo scegliere $$k = |S|$$

Questo assegna un agente a ciascun percorso più breve $p_n$ e possiamo affermare che non ci sono contese tra agenti che dobbiamo modellare.

Permettere $d_{n,0}, d_{n,1}, \dots, d_{n,j}$ essere le distanze ordinate delle monete da $c$ per percorso $p_n$ cioè $d_{n,j} < d_{n,j+1}$.

Considera i percorsi $(c,x)$ e $(c,y)$. Potremmo avere due agenti su questi percorsi e avrebbero potuto raccogliere le monete a$x, y$rispettivamente. Chi ha la priorità mentre torna a$c$? La risposta è che non importa in quanto sono entrambi equidistanti da$c$.

Pertanto, assumeremo la convenzione senza perdita di generalità che l'agente sul percorso più breve avrà la priorità. Questo ci aiuta a semplificare il nostro calcolo.

Permettere $m_n$ essere il numero di monete sul percorso $p_n$. Permettere$c_n$ essere il numero di monete raccolte sul percorso $p_n$.

$c_n$ è vincolato da

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

Il numero totale di monete raccolte è dato da

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

Permettere $M$essere il numero di agenti. Quindi la produttività media dell'agente è data da

$$C \over M$$

Permettere $C_{total}$essere il numero totale di monete. Efficienza$(\eta)$ dell'impiego in termini di monete raccolte sarebbe

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

Prologo: questo diventa molto complicato se consenti più agenti rispetto al numero di percorsi più brevi per le monete, perché dovresti quindi modellare quando quegli agenti possono entrare nel campo, quanti possono entrare nel campo e come si coordinano con l'agente principale sul percorso più breve senza causare contese.

In teoria, una volta che un percorso più breve è stato cancellato da tutte le monete (ciò avverrà se $c_k < t$ per ogni $k$), tutti i percorsi ad esso collegati da un bordo possono utilizzarlo per allineare gli agenti in attesa. Non appena uno di quegli agenti vede una moneta in lontananza$x$ da esso sdraiato su un percorso più breve collegato $p_m$ e la moneta è a una distanza di $d_{n,r}$ e non c'è altra moneta tra quella moneta e $c$ e l'agente principale si sta muovendo verso $c$, l'agente in attesa può spostarsi per ritirare quella moneta.

Nella figura sopra, $r$ è un agente che si sta muovendo verso $c$con una moneta raccolta. I nodi azzurri sono agenti in attesa. L'agente$a$ può spostarsi per raccogliere monete $j$ e segui $r$.

Ciò contribuirà a migliorare l'efficienza. Potremmo utilizzare il percorso più breve da un agente in attesa a una moneta e inviare l'agente a quella moneta. Tuttavia, questo diventa complesso molto rapidamente e non sono sicuro di un modo semplice per calcolare il numero di monete raccolte.