A menos que a @TodorSimeonov se le ocurra algo grandioso, me he dado por vencido para determinar la solución exacta directamente. Lo que creé al final es un algoritmo iterativo que se aproxima a una distribución natural.
El código se puede encontrar aquí:
Aproximadamente se ejecuta de esta manera:
Paso 1
Para todo el conjunto de nodos, encuentre todos los subgrafos desconectados, es decir, encuentre todas las redes separadas.
Paso 2
Para cada red separada, calcule la posición de energía promedio. En el ejemplo, la posición de energía promedio es 0. Luego, calcule lo que cada nodo debería entregar a la red o recibir de la red. Esos son los +7, -2, etc. que vemos en la imagen de ejemplo.
Paso 3
Preparamos una lista de nodos que queremos procesar. Esta lista contiene inicialmente todos los nodos que desean distribuir cualquier energía a la red.
Luego, el algoritmo se ejecuta para un número específico de rondas. Cada ronda
- Recorrerá la lista preparada y distribuirá cualquier energía "excedente" a los nodos conectados. Estos nodos conectados almacenan la energía entrante en un cubo de 'energía entrante' por ahora.
- El algoritmo recorre todos los nodos y agrega toda la energía entrante para ese nodo y lo establece como la energía excedente para distribuir en la siguiente ronda.
Así que después de, por ejemplo. 50 rondas, la energía de un nodo específico ha saltado sobre 50 nodos y se ha distribuido a una red bastante grande.
Para mantener las cosas eficientes, utilizo algunos trucos
- Si hay menos de 1 energía para distribuir para un nodo, se eliminará de la lista de nodos que queremos procesar. Esto se debe a que no queremos distribuir cantidades de energía cada vez más pequeñas en la red. Se volverá a agregar un nodo a la lista si cualquier energía entrante para ese nodo mueve su energía excedente > 1.
- Si un nodo tiene solo 1 nodo conectado, entonces sabemos exactamente cuánta energía se transferirá entre ellos. Por ejemplo, el nodo A tiene +3 y se conecta solo al nodo B. Entonces, sabemos que A transferirá toda esa energía al nodo B, sin importar qué. Por lo tanto, confirmamos la distribución de energía entre esos nodos y eliminamos el nodo A de la lista que se procesará. Aún mejor, si esa conexión se confirma, eso podría significar que el nodo B podría quedarse solo con una conexión a un nodo C, que también puede confirmarse, etc.
- Si la lista de nodos que se procesarán es 0, obviamente se rompe.
El algoritmo parece lo suficientemente rápido en este momento (1-2 ms para algunas redes no tan complicadas).
Cualquier sugerencia aún muy apreciada!
De nuevo, el código completo se puede encontrar aquí: enlace