algorithm optimization graph-theory graph-algorithm mathematical-optimization

algorithm - Conecte los nodos para maximizar el peso total del borde



optimization graph-theory (5)

Estoy trabajando en un problema que podría reducirse a un problema de optimización de gráficos como se muestra a continuación.

  • Se da un conjunto de nodos de colores. Todos están desconectados, es decir, no hay borde en el gráfico.

  • Los bordes deben insertarse entre los nodos.

  • Un nodo solo puede tener 4 aristas al máximo.

  • Una tabla proporciona reglas para la contribución de beneficios de los bordes.

    P.ej.,

    • Un borde que conecta rojo con rojo: el beneficio es 10

    • Un borde que conecta rojo con azul: el beneficio es 20

  • El número total de nodos es de alrededor de 100.

  • El número total de colores suele ser de 20 a 30, pero puede llegar a 50. En consecuencia, la tabla con fines de lucro (borde) sería una lista larga, pero no mostrará todas las combinaciones posibles. El beneficio para los bordes no especificados en la tabla se supone cero.

El problema es optimizar las conexiones (bordes) de modo que se maximice el beneficio total.

Me pregunto si este problema, tal vez de alguna otra manera, es conocido. Si es así, por favor proporcione cualquier sugerencia que pueda ser de ayuda. Gracias.

¿Pensaste tal vez en el enfoque codicioso? Para todos los colores y los valores correspondientes de colorA-> colorB, si para cada borde de color lo hará

edge_color : sort_in_descending_order(edge_color_To_color_Prices) example: red: red->black 30 red->white 20 red->yellow 10 black: black->green 15 black->grey 10

itere hasta que haya espacio para un nuevo borde (4 por nodo) y tome el mayor valor de borde posible (márquelo como visitado también lo ayudará) (Supongo que puede vincular nodeA con nodeB solo una vez). Podemos suponer que la ventaja no está dirigida por lo que ha dicho. En cada nodo, debe almacenar los valores elegidos, de modo que cuando esté iterando sobre el borde siguiente que ya usó, debe conocer los bordes elegidos (el nodo negro debe conocer el rojo -> negro 30 elegido por el rojo)

red: 1st edge: red->black 30 -> stores that in black node list as [red,30] 2nd edge: ...........20 ->... 3rd edge: ...........10 4th edge: ...........5 --------------------------- 5th edge: ...........4 (after update from black it will be 4th edge) black: 1st edge: black->white 50 > [red,30] 2nd edge: .............. 40 3rd edge: .............. 35 4th edge: .............. 34 --------------------------- 5th edge .............. 30 (this is our red->black edge)

reemplace por (negro-> blanco 50) y vaya al nodo rojo para actualizarlo con el siguiente máximo (porque eliminamos rojo-> negro 30 por negro-> blanco 50 - lo reemplazaremos solo si alcanzamos el límite de bordes) en el nodo Negro siguiendo los criterios de valor mínimo: estamos eliminando / reemplazando el borde con el precio más bajo del nodo Negro)

Eso debería funcionar

Aquí está la formulación de programación lineal para este problema: asigne una variable para cada par de colores presente en la tabla de "ganancias" (hasta c * (c + 1) / 2 variables necesarias, donde c es el número de colores), use c restricciones determinadas por la limitación de "4 bordes por nodo" y una restricción para cada variable para limitar el número de bordes posibles (excepto cuando hay al menos 4 nodos para cada uno de los colores de borde o 5 nodos para bordes de un solo color), y maximizar la suma de variable * términos de beneficio.

El solucionador de LP puede encontrar variables totalmente enteras para este problema (si tenemos suerte). O puede haber soluciones con variables fraccionarias, vea el contraejemplo a continuación.

Cuando obtenemos una solución LP (donde cada variable representa el número de bordes para alguna combinación de colores), deberíamos agregar bordes al gráfico. Use alguna estrategia para evitar bucles y bordes duplicados (como "elegir el nodo menos conectado" de los nodos del mismo color).

Contraejemplo : 5 rojos, 4 verdes, varios nodos azules, ganancia 100 para bordes rojo-verdes, 10 para rojo-rojo, 1 para rojo-azul. La solución LP proporciona 20 bordes rojo-verdes (correctos), 2,5 bordes rojo-rojos (deben ser 2) y cero bordes rojo-azules (deben ser 1).

Solución : la programación lineal entera es un enfoque correcto para este problema. Para hasta 50 colores necesitaremos hasta 1275 variables. Esto debería ser una tarea relativamente simple para un solucionador de ILP decente.

Esto suena similar al problema de la mochila 0-1 donde el máximo se calcula si un artículo se coloca en la mochila o no se coloca en la mochila. Aquí hay un ejemplo:

def knapsack(numItems, capacity, sizes, values): # if no more items left to put in knapsack or knapsack is full if (numItems == 0 or capacity == 0): return 0 # if can''t fit item into knapsack, try the next item if (sizes[numItems-1] > capacity): knapsack(numItems-1, capacity, sizes, values) # find the max of including or not including item in knapsack return max( values[values-1] + knapsack(numItems-1,capacity - weights[numitems-1], sizes, values), knapsack(numItems-1, capacity, sizes, values))

Aquí está buscando el máximo cuando un nodo está conectado con otro nodo o no. Cuando un nodo está conectado, el valor que resulta depende del color del nodo. El código se vería algo así como:

def ConnectNodes(numItems, capacity, sizes, values, nodeColor): # if no more items left to connect or capacity is full if (numItems == 0 or capacity == 0): return 0 # if can''t fit item into knapsack, try the next item if (sizes[numItems-1] > capacity): ConnectNodes(numItems-1, capacity, sizes, values, nodeColor) # find the max of connecting or not connecting node return max( RulesForProfit(numItems-1, nodeColor) + ConnectNodes(numItems-1,capacity - weights[numitems-1], sizes, values, nodeColor), ConnectNodes(numItems-1, capacity, sizes, values, nodeColor))

Puede convertir esto en un problema de encontrar una combinación perfecta de costo máximo, que se pueda resolver en tiempo polinomial (por ejemplo, utilizando una variante del algoritmo Blossom )

La conversión consiste en dividir cada nodo de grado d en d nodos izquierdos y d-4 nodos derechos.

Para cada par de vértices u, v en el gráfico original, agregue un borde entre un vértice no conectado u nodo izquierdo y un vértice no conectado v nodo izquierdo de peso equivalente al beneficio de unir u y v.

A continuación, agregue bordes adicionales (de peso 0) entre cada par de nodos izquierdo y derecho (para el mismo vértice).

Ahora construye la coincidencia perfecta de peso máximo en este nuevo gráfico.

El punto es que los bordes adicionales utilizan todos menos 4 de los nodos de la izquierda. Esto significa que cada vértice solo puede obtener ganancias de 4 de los bordes rentables.

Ejemplo

Supongamos que tenemos un problema con 7 nodos de colores. He dibujado la sección del gráfico expandido que corresponde a la parte para un solo nodo verde y un solo nodo rojo.

Tenga en cuenta que hay 6 nodos verdes a la izquierda, uno menos que el número total de nodos de color. Hay 2 nodos verdes derechos, cuatro menos que el número de nodos izquierdos. Hay un solo borde curvo que une un nodo greenleft y un nodo rojo izquierdo. Si este borde curvo se elige en la coincidencia perfecta, significa que el nodo rojo debe unirse al nodo verde.

Solo una idea, no tuve mucho tiempo para verificarla.
¿Qué tal comenzar con un gráfico ponderado G = (V, E) donde V es su conjunto de nodos y el peso E es el beneficio de su tabla? Sea O un conjunto vacío que será nuestra salida.

Luego use un algoritmo coincidente (algoritmo Blossom) en G. Agregue estos bordes a O.

Repita el algoritmo con la entrada G ''= (V, E / O). Nuevamente agregue estos bordes a O.

Repetir otras dos veces. Vuelve O.

Tiempo de ejecución:
El tiempo de ejecución del algoritmo Blossom es O (E * V ^ (1/2)) según wikipedia. Dado que el algoritmo se usa 4 veces, el tiempo total de ejecución también sería O (E * V ^ (1/2)).