Alguns dias atrás, Alguém me pergunta: se temos alguns agentes em nosso ambiente e eles querem ir de suas fontes até seus destinos, como podemos encontrar o caminho mais curto total para todos eles, para que não tenham conflitos durante a caminhada dele

O ponto de problema é que todos os agentes caminham simultaneamente no ambiente (que pode ser modelado por gráfico ponderado não direcionado) e não devemos ter nenhuma colisão. Pensei nisso, mas não consegui encontrar o caminho ideal para todos eles. Mas com certeza existem muitas idéias heurísticas para esse problema.

entrada @Assume é o gráfico G (V, E), m agentes que estão em: S1, S2, ..., Smós do gráfico na inicialização e eles devem ir para os nós D1, ... Dm no fim. Também pode haver conflito nos nósSi ouDi, ... mas esses conflitos não são importantes, eles não devem ter conflito quando estão nos nós internos do caminh

Se o caminho deles não tiver o mesmo nó interno, será meio quek-disjoint paths problema que é NPC, mas nesse caso os caminhos podem ter os mesmos nós, mas o agente não deve estar no mesmo nó no mesmo tempo. Não sei se posso dizer exatamente a afirmação do problema. Se estiver confuso, diga-me nos comentários para editá-l

xiste algum algoritmo ideal e rápido (por ideal, quero dizer que a soma do comprimento de todos os caminhos seja o menor possível e por rápido, quero dizer bom algoritmo de tempo polinomial