python - unam - Desafiante problema de programación dinámica.

programacion dinamica maximizacion

Question

Esta es una versión atenuada de un problema de visión de computadora que necesito resolver. Supongamos que se le asignan los parámetros n, qy tiene que contar el número de formas de asignar números enteros 0 .. (q-1) a los elementos de la cuadrícula n por n, de modo que para cada asignación lo siguiente sea verdadero

1. No hay dos vecinos (horizontal o verticalmente) que tengan el mismo valor.
2. El valor en las posiciones (i, j) es 0
3. El valor en la posición (k, l) es 0

Como no se dan (i, j, k, l), el resultado debe ser una serie de evaluaciones arriba, una para cada configuración válida de (i, j, k, l)

A continuación se muestra un enfoque de fuerza bruta. El objetivo es obtener un algoritmo eficiente que funcione para q <= 100 y para n <= 18.

def tuples(n,q):
  return [[a,]+b for a in range(q) for b in tuples(n-1,q)] if n>1 else [[a] for a in range(q)]

def isvalid(t,n):
  grid=[t[n*i:n*(i+1)] for i in range(n)];
  for r in range(n):
    for c in range(n):
      v=grid[r][c]
      left=grid[r][c-1] if c>0 else -1
      right=grid[r][c-1] if c<n-1 else -1
      top=grid[r-1][c] if r > 0 else -1
      bottom=grid[r+1][c] if r < n-1 else -1
      if v==left or v==right or v==top or v==bottom:
        return False
  return True

def count(n,q):
  result=[]
  for pos1 in range(n**2):
    for pos2 in range(n**2):
      total=0
      for t in tuples(n**2,q):
        if t[pos1]==0 and t[pos2]==0 and isvalid(t,n):
          total+=1

      result.append(total)

  return result

assert count(2,2)==[1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1]

Actualización 11/11 También pregunté esto en los forums TopCoder, y su solución es la más eficiente que he visto hasta ahora (alrededor de 3 horas para n = 10, cualquier q, según estimaciones del autor)

Answer 1

Actualización 11/11 También pregunté esto en los foros de TopCoder, y su solución es la más eficiente que he visto hasta ahora (alrededor de 41 horas por n = 10, cualquier q, según estimaciones del autor)

Yo soy el autor No 41, solo 3 horas de CPU vergonzosamente paralelizables. He counted simetrías. Para n = 10, solo hay 675 pares realmente distintos de (i, j) y (k, l). Mi programa necesita ~ 16 segundos por cada uno.

Answer 2

Algunas observaciones que podrían ayudar a otros que respondieron también:

1. Los valores 1..q son intercambiables, podrían ser letras y el resultado sería el mismo.
2. Las restricciones con las que los vecinos no coinciden son muy leves, por lo que un enfoque de fuerza bruta será excesivamente caro. Incluso si conociera los valores en todas las celdas menos en una, todavía habría al menos q-8 posibilidades para q> 8.
3. La salida de esto será bastante larga: cada conjunto de i, j, k, l necesitará una línea. El número de combinaciones es algo así como n ² (n ² -3), ya que los dos ceros fijos pueden estar en cualquier lugar excepto adyacentes entre sí, a menos que no tengan que obedecer la primera regla. Para n = 100 y q = 18, el caso máximo, esto es ~ 100 ⁴ = 100 millones. Así que esa es su complejidad mínima, y ​​es inevitable ya que el problema está actualmente establecido.
4. Hay casos simples: cuando q = 2, hay dos tableros de ajedrez posibles, por lo que para cualquier par de ceros dado, la respuesta es 1.

El punto 3 hace que todo el programa O (n ² (n ² -3)) como mínimo, y también sugiere que necesitará algo razonablemente eficiente para cada par de ceros, ya que simplemente escribir 100 millones de líneas sin ningún cálculo tomará un tiempo. Para referencia, a un segundo por línea, es 1x10 ⁸ s ~ 3 años, o 3 meses en una caja de 12 núcleos.

Sospecho que hay una respuesta elegante dado un par de ceros, pero no estoy seguro de que haya una solución analítica. Dado que puede hacerlo con 2 o 3 colores dependiendo de las posiciones de los ceros, puede dividir el mapa en una serie de regiones, cada una de las cuales usa solo 2 o 3 colores, y luego es solo el número de combinaciones diferentes de 2 o 3 en q (qC2 o qC3) para cada región multiplicado por el número de regiones, multiplicado por el número de formas de dividir el mapa.

Answer 3

Esto no es una respuesta, solo una contribución a la discusión que es demasiado larga para un comentario.

tl; Dr; Cualquier algoritmo que se reduzca a "Calcule las posibilidades y cuéntelas", como el enfoque de fuerza bruta de Eric Lippert, no funcionará para el objetivo de @ Yaroslav de q <= 100 n <= 18 .

Pensemos primero en una sola columna nx 1 . ¿Cuántas numeraciones válidas de esta columna existen? Para la primera celda podemos escoger entre q números. Como no podemos repetir verticalmente, podemos elegir entre los números q - 1 para la segunda celda y, por lo tanto q - 1 números q - 1 para la tercera celda, y así sucesivamente. Para q == 100 y n == 18 eso significa que hay q * (q - 1) ^ (n - 1) = 100 * 99 ^ 17 colorantes válidos, que son aproximadamente 10 ^ 36 .

Ahora considera dos columnas válidas (llámalas columnas de pan) separadas por una columna de búfer (llámala columna de mostaza). Aquí hay un algoritmo trivial para encontrar un conjunto válido de valores para la columna de mostaza cuando q >= 4 . Comience en la celda superior de la columna de mostaza. Solo tenemos que preocuparnos por las celdas adyacentes de las columnas de pan que tienen a lo sumo 2 valores únicos. Escoja cualquier tercer número para la columna de mostaza. Considere la segunda celda de la columna de mostaza. Debemos considerar la celda de mostaza anterior y las 2 celdas de pan adyacentes con un total de como máximo 3 valores únicos. Elija el 4to valor. Continuar para rellenar la columna de mostaza.

Tenemos a lo sumo 2 columnas que contienen una celda codificada rígida de 0. Usando columnas de mostaza, podemos por lo tanto hacer al menos 6 columnas de pan, cada una con aproximadamente 10 ^ 36 soluciones para un total de al menos 10 ^ 216 soluciones válidas, más o menos Un orden de magnitud para errores de redondeo.

Hay, según Wikipedia, alrededor de 10 ^ 80 átomos en el universo.

Por eso, sé más listo.

Answer 4

Estoy creando una contribución basada en la contribución a la discusión de Dave Aaron Smith.

No consideremos por ahora las dos últimas restricciones ( (i,j) y (k,l) ).

Con solo una columna (nx1) la solución es q * (q - 1) ^ (n - 1) .

¿Cuántas opciones para una segunda columna? (q-1) para la celda superior (1,2) pero luego q-1 o q-2 para la celda (2,2) si (1,2) / (2,1) tiene o no el mismo color.

Lo mismo para (3,2): soluciones q-1 o q-2 .

Podemos ver que tenemos un árbol binario de posibilidades y necesitamos sumar sobre ese árbol. Asumamos que el niño izquierdo siempre es "del mismo color en la parte superior e izquierda" y el niño derecho es "colores diferentes".

Al calcular sobre el árbol el número de posibilidades para la columna de la izquierda para crear tales configuraciones y el número de posibilidades para las nuevas celdas que estamos coloreando, contamos el número de posibilidades para colorear dos columnas.

Pero ahora consideremos la distribución de probabilidad para la coloración de la segunda columna: si queremos recorrer el proceso, necesitamos tener una distribución uniforme en la segunda columna, sería como la primera que nunca existió y entre toda la coloración de la columna. Las primeras dos columnas podríamos decir que cosas como 1/q de ellas tienen color 0 en la celda superior de la segunda columna.

Sin una distribución uniforme sería imposible.

El problema: ¿es la distribución uniforme?

Respuesta: Habríamos obtenido el mismo número de soluciones construyendo primero la segunda columna, la primera y luego la tercera. La distribución de la segunda columna es uniforme en ese caso, por lo que también lo es en el primer caso.

Ahora podemos aplicar la misma "idea de árbol" para contar el número de posibilidades para la tercera columna.

Trataré de desarrollar eso y construiré una fórmula general (ya que el árbol es de tamaño 2 ^ n, no queremos explorarlo explícitamente).

Answer 5

No soy matemático, pero se me ocurre que debería haber una solución analítica para este problema, a saber:

En primer lugar, ahora es posible calcular muchos colores diferentes para el tablero NxN con colores Q (incluido el de los vecinos, que se define como tener un borde común que no tiene el mismo color). Esta debe ser una fórmula bastante simple.

Luego calcule cuántas de estas soluciones tienen 0 en (i, j), esto debería ser la fracción de 1 / Q.

Luego calcule cuántas de las soluciones restantes tienen 0 en (k, l) según la distancia de manhattan | ik | + | jl |, y posiblemente la distancia al borde del tablero y la "paridad" de estas distancias, como en la distancia divisible por 2, Divisible por 3, divisible por Q.

La última parte es la más difícil, aunque creo que todavía podría ser factible si eres realmente bueno en matemáticas.

Answer 6

Tal vez esto suena demasiado simple, pero funciona. Distribuya aleatoriamente valores a todas las celdas hasta que solo dos estén vacías. Prueba de adyacencia de todos los valores. Calcule el promedio del porcentaje de lanzamientos exitosos frente a todos los lanzamientos hasta que la variación caiga dentro de un margen aceptable.

El riesgo se reduce a cero y lo que está en riesgo es solo un poco de tiempo de ejecución.