Hay una rejilla de tamaño N x M . Algunas celdas son islas indicadas por '0' y las otras son agua . Cada celda de agua tiene un número que indica el costo de un puente hecho en esa celda. Tienes que encontrar el costo mínimo por el que se puedan conectar todas las islas. Una celda está conectada a otra celda si comparte un borde o un vértice.
¿Qué algoritmo se puede utilizar para resolver este problema? ¿Qué se puede utilizar como enfoque de fuerza bruta si los valores de N, M son muy pequeños, digamos NxM <= 100?
Ejemplo : en la imagen dada, las celdas verdes indican islas, las celdas azules indican agua y las celdas azul claro indican las celdas en las que se debe hacer un puente. Por lo tanto, para la siguiente imagen, la respuesta será 17 .
Inicialmente pensé en marcar todas las islas como nodos y conectar cada par de islas por un puente más corto. Entonces el problema podría reducirse al árbol de expansión mínimo, pero en este enfoque me perdí el caso donde los bordes se superponen. Por ejemplo , en la siguiente imagen, la distancia más corta entre dos islas cualesquiera es 7 (marcada en amarillo), por lo que al usar Árboles de expansión mínimos la respuesta sería 14 , pero la respuesta debería ser 11 (marcada en azul claro).
Respuestas:
Para abordar este problema, usaría un marco de programación de enteros y definiría tres conjuntos de variables de decisión:
Para los costos de construcción de puentes c_ij , el valor objetivo a minimizar es
sum_ij c_ij * x_ij. Necesitamos agregar las siguientes restricciones al modelo:y_ijbcn <= x_ijpor lo que para cada ubicación de agua (i, j). Además,y_ijbc1debe ser igual a 0 si (i, j) no limita con la isla b. Finalmente, para n> 1,y_ijbcnsolo se puede usar si se usó una ubicación de agua vecina en el paso n-1. DefiniendoN(i, j)como los cuadrados de agua vecinos (i, j), esto es equivalente ay_ijbcn <= sum_{(l, m) in N(i, j)} y_lmbc(n-1).I(c)las ubicaciones que bordean la isla c, esto se puede lograr conl_bc <= sum_{(i, j) in I(c), n} y_ijbcn.sum_{b in S} sum_{c in S'} l_bc >= 1.Para una instancia de problema con K islas, W cuadrados de agua y una longitud de ruta máxima especificada N, este es un modelo de programación de enteros mixtos con
O(K^2WN)variables yO(K^2WN + 2^K)restricciones. Obviamente, esto se volverá intratable a medida que el tamaño del problema aumente, pero puede resolverse para los tamaños que le interesan. Para tener una idea de la escalabilidad, la implementaré en Python usando el paquete pulp. Primero comencemos con el mapa más pequeño de 7 x 9 con 3 islas al final de la pregunta:Esto tarda 1,4 segundos en ejecutarse utilizando el solucionador predeterminado del paquete de pulpa (el solucionador CBC) y genera la solución correcta:
A continuación, considere el problema completo en la parte superior de la pregunta, que es una cuadrícula de 13 x 14 con 7 islas:
Los solucionadores de MIP a menudo obtienen buenas soluciones con relativa rapidez y luego pasan mucho tiempo tratando de demostrar la optimización de la solución. Usando el mismo código de resolución que el anterior, el programa no se completa en 30 minutos. Sin embargo, puede proporcionar un tiempo de espera al solucionador para obtener una solución aproximada:
Esto produce una solución con valor objetivo 17:
Para mejorar la calidad de las soluciones que obtiene, puede utilizar un solucionador de MIP comercial (esto es gratis si se encuentra en una institución académica y probablemente no lo sea de otra manera). Por ejemplo, aquí está el rendimiento de Gurobi 6.0.4, nuevamente con un límite de tiempo de 2 minutos (aunque en el registro de la solución leemos que el solucionador encontró la mejor solución actual en 7 segundos):
¡Esto realmente encuentra una solución de valor objetivo 16, una mejor que la que el OP pudo encontrar a mano!
fuente
Un enfoque de fuerza bruta, en pseudocódigo:
En C ++, esto podría escribirse como
// map = linearized map; map[x*n + y] is the equivalent of map2d[y][x] // nm = n*m // bridged = true if bridge there, false if not. Also linearized // nBridged = depth of recursion (= current bridge being considered) // cost = total cost of bridges in 'bridged' // best, bestCost = best answer so far. Initialized to "horrible" void findBestBridges(char map[], int nm, bool bridged[], int nBridged, int cost, bool best[], int &bestCost) { if (nBridged == nm) { if (connected(map, nm, bridged) && cost < bestCost) { memcpy(best, bridged, nBridged); bestCost = best; } return; } if (map[nBridged] != 0) { // try with a bridge there bridged[nBridged] = true; cost += map[nBridged]; // see how it turns out findBestBridges(map, nm, bridged, nBridged+1, cost, best, bestCost); // remove bridge for further recursion bridged[nBridged] = false; cost -= map[nBridged]; } // and try without a bridge there findBestBridges(map, nm, bridged, nBridged+1, cost, best, bestCost); }Después de hacer una primera llamada (supongo que está transformando sus mapas 2d en matrices 1d para facilitar la copia),
bestCostcontendrá el costo de la mejor respuesta ybestcontendrá el patrón de puentes que lo produce. Sin embargo, esto es extremadamente lento.Optimizaciones:
bestCost, porque no tiene sentido seguir buscando después. Si no puede mejorar, no sigas investigando.Un algoritmo de búsqueda general como A * permite una búsqueda mucho más rápida, aunque encontrar una mejor heurística no es una tarea sencilla. Para un enfoque más específico del problema, usar los resultados existentes en árboles Steiner , como sugiere @Gassa, es el camino a seguir. Sin embargo, tenga en cuenta que el problema de construir árboles Steiner en cuadrículas ortogonales es NP-Complete, según este artículo de Garey y Johnson .
Si "suficientemente bueno" es suficiente, un algoritmo genético probablemente pueda encontrar soluciones aceptables rápidamente, siempre que agregue algunas heurísticas clave en cuanto a la ubicación preferida del puente.
fuente
2^(13*14) ~ 6.1299822e+54iteraciones. Si asumimos que puede hacer un millón de iteraciones por segundo, eso solo tomaría ... ~ 194380460000000000000000000000000000000000` años. Esas optimizaciones son muy necesarias.Este problema es una variante del árbol de Steiner llamado árbol de Steiner ponderado por nodos , especializado en una determinada clase de gráficos. De manera compacta, el árbol Steiner ponderado por nodos, dado un gráfico no dirigido ponderado por nodos donde algunos nodos son terminales, encuentra el conjunto de nodos más barato que incluye todos los terminales que inducen un subgrafo conectado. Lamentablemente, parece que no puedo encontrar ningún solucionador en algunas búsquedas superficiales.
Para formular como un programa entero, haga una variable 0-1 para cada nodo no terminal, luego para todos los subconjuntos de nodos no terminales cuya eliminación del gráfico inicial desconecta dos terminales, requiera que la suma de las variables en el subconjunto sea en al menos 1. Esto induce demasiadas restricciones, por lo que tendrá que hacerlas cumplir de manera perezosa, utilizando un algoritmo eficiente para la conectividad del nodo (flujo máximo, básicamente) para detectar una restricción violada al máximo. Perdón por la falta de detalles, pero esto va a ser complicado de implementar incluso si ya está familiarizado con la programación de enteros.
fuente
Dado que este problema tiene lugar en una cuadrícula y tiene parámetros bien definidos, abordaría el problema con la eliminación sistemática del espacio del problema creando un árbol de expansión mínimo. Al hacerlo, para mí tiene sentido si aborda este problema con el algoritmo de Prim.
Desafortunadamente, ahora se encuentra con el problema de abstraer la cuadrícula para crear un conjunto de nodos y bordes ... ergo, el problema real de esta publicación es ¿cómo puedo convertir mi cuadrícula nxm en {V} y {E}?
Este proceso de conversión es, de un vistazo, NP-Hard debido a la gran cantidad de combinaciones posibles (suponga que todos los costos de las vías navegables son idénticos). Para manejar instancias donde las rutas se superponen, debería considerar la posibilidad de crear una isla virtual.
Una vez hecho esto, ejecute el algoritmo de Prim y debería llegar a la solución óptima.
No creo que la programación dinámica se pueda ejecutar de manera efectiva aquí porque no existe un principio observable de optimización. Si encontramos el costo mínimo entre dos islas, eso no significa necesariamente que podamos encontrar el costo mínimo entre esas dos y la tercera isla, u otro subconjunto de islas que será (según mi definición, encontrar el MST a través de Prim) conectado.
Si desea que el código (pseudo o de otro tipo) convierta su cuadrícula en un conjunto de {V} y {E}, envíeme un mensaje privado y analizaré la posibilidad de unir una implementación.
fuente