Pregunta ¿Cuál es el costo mínimo para conectar todas las islas?


Hay una grilla de tamaño N x M. Algunas celdas son islas denotado por '0' y los otros son agua. Cada celda de agua tiene un número que indica el costo de un puente hecho en esa celda. Debe encontrar el costo mínimo por el que se pueden conectar todas las islas. Una celda está conectada a otra celda si comparte un borde o un vértice.

¿Qué algoritmo puede usarse para resolver este problema?
Editar: ¿Qué se puede usar 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 celestes indican las celdas sobre las cuales se debe construir un puente. Por lo tanto, para la siguiente imagen, la respuesta será 17.

http://i.imgur.com/ClcboBy.png

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 a Á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 es 7(marcado en amarillo), por lo que al usar árboles de expansión mínima, la respuesta sería 14, pero la respuesta debería ser 11 (marcado en azul claro).

image2


75
2018-05-31 08:57


origen


Respuestas:


Para abordar este problema, usaría un marco de programación entero y definiría tres conjuntos de variables de decisión:

  • x_ij: Una variable indicadora binaria para si construimos un puente en la ubicación del agua (i, j).
  • y_ijbcn: Un indicador binario de si la ubicación del agua (i, j) es la n ° ubicación que une la isla b con la isla c.
  • l_bc: Una variable indicadora binaria para determinar si las islas b y c están directamente vinculadas (también se puede caminar solo en cuadrados de puente de b a c).

Para los costos de construcción de puentes c_ij, el valor objetivo para minimizar es sum_ij c_ij * x_ij. Necesitamos agregar las siguientes restricciones al modelo:

  • Necesitamos asegurarnos y_ijbcn las variables son validas Siempre podemos llegar a una plaza de agua si construimos un puente allí, entonces y_ijbcn <= x_ij para cada ubicación de agua (i, j). Promover, y_ijbc1 debe ser igual a 0 si (i, j) no limita con la isla b. Finalmente, para n> 1, y_ijbcn solo se puede usar si se utilizó una ubicación de agua vecina en el paso n-1. Definiendo N(i, j) para ser las casillas de agua vecinas (i, j), esto es equivalente a y_ijbcn <= sum_{(l, m) in N(i, j)} y_lmbc(n-1).
  • Necesitamos asegurarnos l_bc las variables solo se establecen si b y c están vinculadas. Si definimos I(c) para ser los lugares que bordean la isla c, esto se puede lograr con l_bc <= sum_{(i, j) in I(c), n} y_ijbcn.
  • Necesitamos asegurarnos de que todas las islas estén conectadas, ya sea directa o indirectamente. Esto se puede lograr de la siguiente manera: para cada subconjunto propio S no vacío de islas, se requiere que al menos una isla en S esté vinculada a al menos una isla en el complemento de S, que llamaremos S '. En restricciones, podemos implementar esto agregando una restricción para cada conjunto no vacío S de tamaño <= K / 2 (donde K es el número de islas), sum_{b in S} sum_{c in S'} l_bc >= 1.

Para una instancia problemática con K islands, W water squares y la longitud máxima especificada N de ruta, este es un modelo de programación entero mixto con O(K^2WN) variables y O(K^2WN + 2^K) restricciones Obviamente, esto se volverá intratable ya que el tamaño del problema se agranda, pero puede resolverse para los tamaños que te interesan. Para tener una idea de la escalabilidad, lo implementaré en python usando el paquete de pulpa. Primero comencemos con el mapa más pequeño de 7 x 9 con 3 islas en la parte inferior de la pregunta:

import itertools
import pulp
water = {(0, 2): 2.0, (0, 3): 1.0, (0, 4): 1.0, (0, 5): 1.0, (0, 6): 2.0,
         (1, 0): 2.0, (1, 1): 9.0, (1, 2): 1.0, (1, 3): 9.0, (1, 4): 9.0,
         (1, 5): 9.0, (1, 6): 1.0, (1, 7): 9.0, (1, 8): 2.0,
         (2, 0): 1.0, (2, 1): 9.0, (2, 2): 9.0, (2, 3): 1.0, (2, 4): 9.0,
         (2, 5): 1.0, (2, 6): 9.0, (2, 7): 9.0, (2, 8): 1.0,
         (3, 0): 9.0, (3, 1): 1.0, (3, 2): 9.0, (3, 3): 9.0, (3, 4): 5.0,
         (3, 5): 9.0, (3, 6): 9.0, (3, 7): 1.0, (3, 8): 9.0,
         (4, 0): 9.0, (4, 1): 9.0, (4, 2): 1.0, (4, 3): 9.0, (4, 4): 1.0,
         (4, 5): 9.0, (4, 6): 1.0, (4, 7): 9.0, (4, 8): 9.0,
         (5, 0): 9.0, (5, 1): 9.0, (5, 2): 9.0, (5, 3): 2.0, (5, 4): 1.0,
         (5, 5): 2.0, (5, 6): 9.0, (5, 7): 9.0, (5, 8): 9.0,
         (6, 0): 9.0, (6, 1): 9.0, (6, 2): 9.0, (6, 6): 9.0, (6, 7): 9.0,
         (6, 8): 9.0}
islands = {0: [(0, 0), (0, 1)], 1: [(0, 7), (0, 8)], 2: [(6, 3), (6, 4), (6, 5)]}
N = 6

# Island borders
iborders = {}
for k in islands:
    iborders[k] = {}
    for i, j in islands[k]:
        for dx in [-1, 0, 1]:
            for dy in [-1, 0, 1]:
                if (i+dx, j+dy) in water:
                    iborders[k][(i+dx, j+dy)] = True

# Create models with specified variables
x = pulp.LpVariable.dicts("x", water.keys(), lowBound=0, upBound=1, cat=pulp.LpInteger)
pairs = [(b, c) for b in islands for c in islands if b < c]
yvals = []
for i, j in water:
    for b, c in pairs:
        for n in range(N):
            yvals.append((i, j, b, c, n))

y = pulp.LpVariable.dicts("y", yvals, lowBound=0, upBound=1)
l = pulp.LpVariable.dicts("l", pairs, lowBound=0, upBound=1)
mod = pulp.LpProblem("Islands", pulp.LpMinimize)

# Objective
mod += sum([water[k] * x[k] for k in water])

# Valid y
for k in yvals:
    i, j, b, c, n = k
    mod += y[k] <= x[(i, j)]
    if n == 0 and not (i, j) in iborders[b]:
        mod += y[k] == 0
    elif n > 0:
        mod += y[k] <= sum([y[(i+dx, j+dy, b, c, n-1)] for dx in [-1, 0, 1] for dy in [-1, 0, 1] if (i+dx, j+dy) in water])

# Valid l
for b, c in pairs:
    mod += l[(b, c)] <= sum([y[(i, j, B, C, n)] for i, j, B, C, n in yvals if (i, j) in iborders[c] and B==b and C==c])

# All islands connected (directly or indirectly)
ikeys = islands.keys()
for size in range(1, len(ikeys)/2+1):
    for S in itertools.combinations(ikeys, size):
        thisSubset = {m: True for m in S}
        Sprime = [m for m in ikeys if not m in thisSubset]
        mod += sum([l[(min(b, c), max(b, c))] for b in S for c in Sprime]) >= 1

# Solve and output
mod.solve()
for row in range(min([m[0] for m in water]), max([m[0] for m in water])+1):
    for col in range(min([m[1] for m in water]), max([m[1] for m in water])+1):
        if (row, col) in water:
            if x[(row, col)].value() > 0.999:
                print "B",
            else:
                print "-",
        else:
            print "I",
    print ""

Esto lleva 1.4 segundos para ejecutarse utilizando el solucionador predeterminado del paquete de pulpa (el solucionador de CBC) y genera la solución correcta:

I I - - - - - I I 
- - B - - - B - - 
- - - B - B - - - 
- - - - B - - - - 
- - - - B - - - - 
- - - - B - - - - 
- - - I I I - - - 

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:

water = {(i, j): 1.0 for i in range(13) for j in range(14)}
islands = {0: [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)],
           1: [(9, 0), (9, 1), (10, 0), (10, 1), (10, 2), (11, 0), (11, 1),
               (11, 2), (12, 0)],
           2: [(0, 7), (0, 8), (1, 7), (1, 8), (2, 7)],
           3: [(7, 7), (8, 6), (8, 7), (8, 8), (9, 7)],
           4: [(0, 11), (0, 12), (0, 13), (1, 12)],
           5: [(4, 10), (4, 11), (5, 10), (5, 11)],
           6: [(11, 8), (11, 9), (11, 13), (12, 8), (12, 9), (12, 10), (12, 11),
               (12, 12), (12, 13)]}
for k in islands:
    for i, j in islands[k]:
        del water[(i, j)]

for i, j in [(10, 7), (10, 8), (10, 9), (10, 10), (10, 11), (10, 12),
             (11, 7), (12, 7)]:
    water[(i, j)] = 20.0

N = 7

Los solucionadores de MIP a menudo obtienen buenas soluciones con relativa rapidez y luego pasan una gran cantidad de tiempo tratando de probar la optimalidad de la solución. Usando el mismo código de solució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:

mod.solve(pulp.solvers.PULP_CBC_CMD(maxSeconds=120))

Esto produce una solución con el valor objetivo 17:

I I - - - - - I I - - I I I 
I I - - - - - I I - - - I - 
I I - - - - - I - B - B - - 
- - B - - - B - - - B - - - 
- - - B - B - - - - I I - - 
- - - - B - - - - - I I - - 
- - - - - B - - - - - B - - 
- - - - - B - I - - - - B - 
- - - - B - I I I - - B - - 
I I - B - - - I - - - - B - 
I I I - - - - - - - - - - B 
I I I - - - - - I I - - - I 
I - - - - - - - I I I I I I 

Para mejorar la calidad de las soluciones que obtiene, puede usar un solucionador de MIP comercial (esto es gratis si se encuentra en una institución académica y es probable que no sea gratis). Por ejemplo, aquí está el rendimiento de Gurobi 6.0.4, nuevamente con un límite de tiempo de 2 minutos (aunque del registro de la solución leemos que el solucionador encontró la mejor solución actual en 7 segundos):

mod.solve(pulp.solvers.GUROBI(timeLimit=120))

¡Esto realmente encuentra una solución de valor objetivo 16, uno mejor de lo que el OP pudo encontrar a mano!

I I - - - - - I I - - I I I 
I I - - - - - I I - - - I - 
I I - - - - - I - B - B - - 
- - B - - - - - - - B - - - 
- - - B - - - - - - I I - - 
- - - - B - - - - - I I - - 
- - - - - B - - B B - - - - 
- - - - - B - I - - B - - - 
- - - - B - I I I - - B - - 
I I - B - - - I - - - - B - 
I I I - - - - - - - - - - B 
I I I - - - - - I I - - - I 
I - - - - - - - I I I I I I 

57
2018-06-24 21:51



Este problema es una variante del árbol Steiner llamado Nodo ponderado Steiner tree, especializado una cierta clase de gráficos. Compactamente, el árbol Steiner ponderado de nodos, dado un gráfico no dirigido ponderado de nodos donde algunos nodos son terminales, encuentra el conjunto más barato de nodos, incluidos todos los terminales que induce un subgrafo conectado. Tristemente, 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 terminales cuya eliminación del gráfico inicial desconecta dos terminales, exija que la suma de variables en el subconjunto esté en menos 1. Esto genera demasiadas restricciones, por lo que tendrá que aplicarlas de forma perezosa, utilizando un algoritmo eficiente para la conectividad de nodos (máximo flujo, básicamente) para detectar una restricción violada al máximo. Perdón por la falta de detalles, pero va a ser complicado implementarlo incluso si ya está familiarizado con la programación entera.


3
2018-06-16 16:58



Un enfoque de fuerza bruta, en pseudo-código:

start with a horrible "best" answer
given an nxm map,
    try all 2^(n*m) combinations of bridge/no-bridge for each cell
        if the result is connected, and better than previous best, store it

return best

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 de 1d para facilitar la copia), bestCost contendrá el costo de la mejor respuesta, y best contendrá el patrón de puentes que lo produce. Esto es, sin embargo, extremadamente lento.

Optimizaciones:

  • Al usar un "límite de puente" y ejecutar el algoritmo para aumentar el número máximo de puentes, puede encontrar respuestas mínimas sin explorar todo el árbol. Encontrar una respuesta de 1 puente, si existiera, sería O (nm) en lugar de O (2 ^ nm), una mejora drástica.
  • Puede evitar la búsqueda (al detener la recursión, también se llama "poda") una vez que ha excedido bestCost, porque no tiene sentido seguir cuidando. Si no puede mejorar, no continúe cavando.
  • La poda anterior funciona mejor si observa los candidatos "buenos" antes de mirar los "malos" (ya que es así, todas las células se miran de izquierda a derecha, de arriba hacia abajo). Una buena heurística sería considerar que las células que están cerca de varios componentes no conectados tienen mayor prioridad que las que no lo están. Sin embargo, una vez que agregas heurística, tu búsqueda comienza a parecerse UN* (y también necesitas algún tipo de cola de prioridad).
  • Puentes duplicados y puentes a ninguna parte deben ser evitados. Cualquier puente que no desconecte la red de la isla si se elimina es redundante.

Un algoritmo de búsqueda general como UN* 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, utilizando los resultados existentes en Árboles de Steiner, como lo sugirió @Gassa, es el camino a seguir. Sin embargo, tenga en cuenta que el problema de construir árboles Steiner en cuadrículas ortogonales es NP-Completo, según este papel de Garey y Johnson.

Si es suficiente "lo suficientemente bueno", un algoritmo genético probablemente pueda encontrar soluciones aceptables rápidamente, siempre y cuando agregue algunas heurísticas clave en cuanto a la ubicación preferida del puente.


3
2018-06-08 16:42



Dado que este problema tiene lugar en una grilla, y tiene parámetros bien definidos, abordaría el problema con la eliminación sistemática del espacio problemático mediante la creación de un árbol de expansión mínimo. Al hacerlo, tiene sentido para mí si aborda este problema con el Algoritmo de Prim.

Lamentablemente, ahora se encuentra con el problema de abstraer la cuadrícula para crear un conjunto de nodos y bordes ... ergo, el verdadero problema de esta publicación es ¿Cómo convierto mi cuadrícula n x m en {V} y {E}?

Este proceso de conversión es, a simple vista, probable NP-Hard debido a la gran cantidad de combinaciones posibles (suponiendo que todos los costos de la vía navegable son idénticos). Para manejar instancias donde los caminos se superponen, debe considerar hacer una isla virtual.

Cuando haya terminado, ejecute el Algoritmo de Prim y deberá llegar a la solución óptima.

No creo que la Programación Dinámica se pueda ejecutar efectivamente aquí porque no existe un principio observable de optimalidad. Si encontramos el costo mínimo entre dos islas, eso no necesariamente significa que podemos encontrar el costo mínimo entre esas dos y la tercera isla, u otro subconjunto de islas que será (por mi definición para 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é cómo empalmar una implementación.


-1
2018-06-16 17:24



Estoy de acuerdo en que este es un problema de vendedor ambulante, pero puede ser forzado con n = 7. Calcula la ruta de costo mínimo entre cada isla y solo tendrás n (n-1) / 2 soluciones = 21 cálculos


-6
2018-06-08 14:42