Eficiência de um processo sequencial

Question

Não tenho certeza se isso é mais uma questão de programação ou matemática. Informe o fórum adequado para fazer a pergunta, se não for esse.

Eu tenho um processo sequencial da seguinte forma:

1. tem $n$ moedas espalhadas em uma grade quadrada de $100 \times 100$ pontos.
2. tem $m$ agentes em uma localização central, ou seja, o ponto $(50,50)$.
3. Esses agentes podem fazer uma caminhada aleatória na grade, movendo um ponto da grade em uma etapa. Em uma etapa de tempo, todos os agentes movem-se uma etapa de sua posição atual.
4. Os agentes devem encontrar as moedas. Quando um agente encontra uma moeda, o intervalo de tempo é anotado. Em seguida, o agente passa a se mover para o local central ao longo do caminho mais curto a partir do ponto onde a moeda foi encontrada. Novamente, em uma etapa de tempo, o agente pode mover apenas um ponto de grade, enquanto outros agentes ainda podem estar procurando por outras moedas.
5. Quando o agente com a moeda chega ao local central, a moeda é deixada e o agente começa a procurar por outras moedas novamente.
6. O processo para quando um determinado número de etapas de tempo termina, independentemente de todas as moedas terem sido encontradas.

No processo geral, eu tenho controle sobre a distribuição de moedas, se todos os agentes saem de uma vez ou em determinados intervalos de tempo, e se eles podem interagir entre si para reduzir a exploração da mesma área novamente. No final, quero saber com que rapidez as moedas são encontradas pelos agentes. Estou procurando uma maneira de quantificar essa eficiência de encontrar moedas no caso generalizado de$n$ moedas e $m$agentes. Isso significa que, se eu quiser comparar 10 agentes que encontram 100 moedas com 5 agentes que encontram 50 moedas, essa quantidade deve ser capaz de me dizer em que caso os agentes foram mais eficientes em encontrar as moedas. Posso representar graficamente a porcentagem de moedas encontradas ao longo do tempo, e isso geralmente é uma curva em S, mas conforme meus parâmetros aumentam, acho que seria melhor se eu tivesse valores únicos para comparar em vez de linhas de gráfico.

Na minha opinião, acho que os três parâmetros que desempenham um papel na determinação dessa eficiência são a distância de uma moeda ao centro, os intervalos de tempo que um agente leva para encontrar a moeda a partir do centro e o número total de agentes na área em busca de moedas. Mas não tenho certeza de qual seria uma boa maneira de relacioná-los.

Answer 1

Resposta Parcial

Temos um gráfico de rede $G$ com um nó identificado como o nó central, $c$.

Deixei $$N=V \space \text{\\} \space \{c\},$$ ie, $N$ é o conjunto de nós de $G$ excluindo $c$.

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

Se restringirmos o problema dizendo o número de agentes $k$ que será implantado é determinado em $t = 0$ e permanece constante ao longo da simulação, podemos escolher $$k = |S|$$

Isso atribui um agente para cada caminho mais curto $p_n$ e podemos afirmar que não há contendas entre os agentes que devemos modelar.

Deixei $d_{n,0}, d_{n,1}, \dots, d_{n,j}$ ser as distâncias classificadas das moedas de $c$ para caminho $p_n$ ie, $d_{n,j} < d_{n,j+1}$.

Considere os caminhos $(c,x)$ e $(c,y)$. Poderíamos ter dois agentes nesses caminhos e eles poderiam ter coletado as moedas em$x, y$respectivamente. Quem tem prioridade ao retornar para$c$? A resposta é: não importa, pois ambos são equidistantes de$c$.

Portanto, assumiremos a convenção, sem perda de generalidade, de que o agente no caminho mais curto terá prioridade. Isso nos ajuda a simplificar nosso cálculo.

Deixei $m_n$ seja o número de moedas no caminho $p_n$. Deixei$c_n$ seja o número de moedas coletadas no caminho $p_n$.

$c_n$ é restringido por

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

O número total de moedas coletadas é dado por

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

Deixei $M$ser o número de agentes. Então, a produtividade média do agente é dada por

$$C \over M$$

Deixei $C_{total}$ser o número total de moedas. Eficiência$(\eta)$ da implantação em termos de moedas coletadas seria

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

Prólogo: Isso se torna muito complicado se você permitir mais agentes do que o número de caminhos mais curtos para as moedas, porque você então precisaria modelar quando esses agentes podem entrar no campo, quantos podem entrar no campo e como eles se coordenam com o agente principal no caminho mais curto sem causar contenção.

Em teoria, uma vez que o caminho mais curto é limpo de todas as moedas (isso ocorrerá se $c_k < t$ para qualquer $k$), todos os caminhos que estão conectados a ele por uma borda podem fazer uso dele para alinhar agentes em espera. Assim que um desses agentes vir uma moeda à distância$x$ dele deitado em um caminho mais curto conectado $p_m$ e a moeda está a uma distância de $d_{n,r}$ e não há outra moeda entre essa moeda e $c$ e o agente principal está se movendo em direção $c$, o agente em espera pode mover-se para coletar essa moeda.

Na figura acima, $r$ é um agente se movendo em direção $c$com uma moeda coletada. Os nós azuis claros são agentes em espera. O agente$a$ pode se mover para coletar moedas $j$ E siga $r$.

Isso ajudará a melhorar a eficiência. Poderíamos usar o caminho mais curto de um agente em espera até uma moeda e despachar o agente para essa moeda. No entanto, isso fica complexo muito rapidamente e não tenho certeza de uma maneira simples de calcular o número de moedas coletadas.