Hace unos días, alguien me pregunta, si tenemos algunos agentes en nuestro entorno y quieren ir de sus fuentes a sus destinos, cómo podemos encontrar el camino más corto para todos ellos de modo que no tengan conflictos durante su paseo.

El punto del problema es que todos los agentes caminan simultáneamente en el entorno (que puede modelarse mediante un gráfico ponderado no dirigido), y no deberíamos tener ninguna colisión. Pensé en esto pero no pude encontrar el camino óptimo para todos ellos. Pero seguro que hay demasiadas ideas heurísticas para este problema.

La entrada del supuesto es el gráfico G (V, E), m agentes que están en: S1, S2, ..., Sm nodos de gráfico en el inicio y deben ir a los nodos D1,...Rm al final. También puede haber conflicto en los nodosSi oDi, ... pero estos conflictos no son importantes, no deberían tener conflicto cuando están en sus nodos internos de su camino.

Si su ruta no debe tener el mismo nodo interno, será una especie dek-disjoint paths problema que es NPC, pero en este caso las rutas pueden tener los mismos nodos, pero el agente no debería estar en el mismo nodo al mismo tiempo. No sé si puedo decir el enunciado exacto del problema o no. Si es confuso, dígame en los comentarios para editarlo.

Existe algún algoritmo óptimo y rápido (por óptimo quiero decir que la suma de la longitud de todas las rutas sea lo más pequeña posible, y por rápido quiero decir un buen algoritmo de tiempo polinómico).