Mi problema es así:
Tengo un diseño físico representado como un gráfico. Los nodos representan ganchos / conductos donde un cable puede anclarse y los bordes son la posible conexión entre 2 nodos desde donde puede ir el cable.
Hay algunos nodos especiales, llamados divisores, desde donde un solo cable se puede dividir en 2 o más hasta k. La k se puede tomar constante por ahora, pero varía de un nodo a otro. No todos los nodos son divisores.
Hay una fuente de energía de donde emergerá un cable. Es la fuente. El cable tiene que ser llevado a n sumideros.
Un borde puede tomar cualquier cantidad de cables que lo atraviesen en cualquier dirección.
La longitud total del cable debe minimizarse.
Se desconoce la naturaleza del gráfico, plano o euclidiano.
Ejemplo : a continuación se muestra una red de muestra. Los nodos se nombran como números y las aristas se proporcionan con pesos iguales de 1. La fuente es Nodo1 y los sumideros son Nodo5, Nodo9 y Nodo13. En el caso 1, el nodo 6 es el nodo divisor. En el caso 2, Nodo6 y Nodo4 son nodos divisores. El nodo divisor k = 3, es decir, puede tomar un cable y dividirlo en 3 cables.
Caso 1 . Solo un nodo divisor. Tiene sentido dividirse en el Nodo 6.
Caso 2 . Nodo divisor de dos. Tiene sentido dividirse en el Nodo4 en lugar del Nodo6.
Estoy buscando diferentes estrategias para encontrar una solución genérica para este problema. El gráfico presentado aquí es de menor escala en comparación con el problema en cuestión. El gráfico es estático y no se puede cambiar (es decir, la solución no debe sugerir ningún borde nuevo ni proponer una nueva ubicación del divisor). Cualquier referencia al trabajo de investigación publicado sobre este tipo de problema también es bienvenida.
Caso 3 . Nodo divisor de dos. Tiene sentido dividirse en Node4 y Node14. Tenga en cuenta que este caso tiene pesos de borde cambiados para Edge 8-12, 6-10 y 10-11. Lo importante en este caso es volver a trazar un cable después de separarse del Nodo 14.
fuente
@ Chao Xu, también encontré que Steiner es la aproximación más cercana a mi problema. Estoy explorando sistemas basados en Ant para resolver este problema.
fuente