algorithm - tiempo - rompecabezas deslizante

¿Cómo puedo mejorar este algoritmo para resolver un rompecabezas de sello postal modificado?

Question

El problema de Son of Darts fue un concurso en los concursos de programación de Al Zimmermann que terminó el 20 de junio de 2010:

• Supongamos que tienes una diana que está dividida en R regiones. Cada región de tablero de dardos tiene un valor entero positivo asociado. Supongamos, además, que tienes dardos D y que arrojas cada uno de ellos al tablero de dardos. Cada dardo cae en una de las regiones R de la junta o pierde la junta por completo. Su puntaje es la suma de los valores para las regiones en las que aterrizan los dardos. Un dardo que pierde el tablero no contribuye en nada a tu puntuación. Si varios dardos caen en la misma región, acumulará el valor de esa región varias veces.

• Por ejemplo, suponga que R = 5, que las regiones de tablero de dardos tienen valores (1, 2, 4, 7, 11) y que D = 3. Si sus tres dardos aterrizan en las regiones 2, 4 y 11, obtiene 17 puntos. Si un dardo pierde el tablero y los otros dos aterrizan en la región 7, obtienes 14 puntos.

• El problema de los dardos es el siguiente: para una R y una D determinadas, determine qué valores deben asociarse con las regiones R de un tablero de dardos para maximizar la puntuación más pequeña inalcanzable al lanzar dardos D.

  D = number of darts R = number of dartboard regions
  3 1 through 40
  4 1 through 30
  5 1 through 20
  6 1 through 10

================================================== ================================

ALGORITMO BÁSICO UTILIZADO (explicado para D = 3 )

• Comienzo con la matriz de resultados que se muestra a continuación. 0 y 1 son las puntuaciones que deberían estar allí en las regiones de la diana. 0 indica que el dardo perdió el tablero. Por lo tanto, voy a generar esta matriz para 41 elementos (uno extra para compensar 0 ). 1 es obligatorio porque de lo contrario no hay otra forma de generar 1 .

   ____ ____
  | | |
  | 0 | 1 |
  |____|____|

• Genero la matriz de raspado que muestra lo que todos los totales son alcanzables utilizando las puntuaciones de dardos en la matriz de resultados, en tres tiros. Los elementos subrayados son los que se utilizaron para generar el scratch .

  0 = 0 + 0 + 0
  1 = 1 + 0 + 0
  2 = 1 + 1 + 0
  3 = 1 + 1 + 1
  ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____
  | * | * | * | * | | | | | | | | | |
  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
  |__-_|__-_|____|____|____|____|____|____|____|____|____|____|____|

• Ahora los candidatos para el siguiente elemento en la matriz de resultados son 2 , 3 o 4 .

  • 2 = elemento uno mayor que el elemento más grande actual

  • 4 = el elemento inalcanzable pequeño

• Intento con cada uno de estos candidatos y veo lo que es el máximo de elementos inalcanzables más pequeños en cada caso. Por ejemplo

  (0, 1, 2 )

   ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____
  | * | * | * | * | * | * | * | | | | | | |
  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
  |__-_|__-_|__-_|____|____|____|____|____|____|____|____|____|____|

  (0, 1, 3 )

   ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____
  | * | * | * | * | * | * | * | * | | * | | | |
  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
  |__-_|__-_|____|__-_|____|____|____|____|____|____|____|____|____|

  (0, 1, 4 )

   ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____
  | * | * | * | * | * | * | * | | * | * | | | * |
  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
  |__-_|__-_|____|____|__-_|____|____|____|____|____|____|____|____|

• max (7, 8, 7) = 8 . Entonces, 3 es elegido como el siguiente elemento.

• Si supongo que hubo un empate, por ejemplo, si tuviera que elegir entre (0, 1, 2 ) y (0, 1, 4 ), para romper el empate contaría el número de números alcanzables, que es más en el caso de (0, 1, 4 ). Por lo tanto, elegiría (0, 1, 4 ) sobre (0, 1, 2 ).

• Pero en este caso, (0, 1, 3 ) es el ganador y el conjunto de resultados se ve a continuación. Luego, repito los pasos hasta que tenga 41 elementos.

   ____ ____ ____
  | | | |
  | 0 | 1 | 3 |
  |____|____|____|

• El algoritmo es codicioso en el sentido de que asume que (solución para R = 20) es un subconjunto de (solución para R = 30). Entonces, no calculo resultados para cada valor de R, pero sí calculo resultados para cada valor de D. Entonces, para D = 3, compagino el resultado para R = 40 y luego tomo los primeros 30 elementos del resultado para R = 30, por ejemplo.

• El algoritmo es codicioso en el sentido de que asume que el objetivo en cada paso (al crear la matriz de resultados ) es lograr el total mínimo inalcanzable en la etapa.

• Para poder rendir mejor que la fuerza bruta, el algoritmo elimina algunos candidatos para la matriz de resultados. Por ejemplo, en el caso que se muestra en el diagrama a continuación (para una matriz de resultados (0, 1, 4)), solo considero a 5, 6 y 7 como candidatos para el siguiente elemento y excluyo 2 y 3 aunque todavía no se utilicen. . Esta suposición podría darme resultados subóptimos en algunos casos, pero reduce mucho el cálculo cuando el rasguño crece a miles de elementos.

   ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____
  | * | * | * | * | * | * | * | | * | * | | | * |
  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
  |__-_|__-_|____|____|__-_|____|____|____|____|____|____|____|____|

MEJORAS AL ALGORITMO.

• Como esto no daba resultados demasiado buenos, intenté generar conjuntos de resultados para cada valor de D. Por ejemplo, en lugar de elegir el mejor siguiente elemento para el resultado , también podría elegir el segundo mejor o el tercer mejor elemento. Por lo tanto, para los 39 pasos a seguir (a 41 elementos en el resultado), podría generar alrededor de 3 ^ 39 (para cada elección, puedo tener el mejor o el segundo mejor o el tercer mejor elemento) casos, lo cual es demasiado. Por lo tanto, decidí apostar por un segundo mejor y por un tercio de las mejores opciones. Eso redujo el número de casos a alrededor de ⁴⁰ C ₁ * ³⁹ C ₁ = 577980 resultados. Más de lo que esto llevaría a un número enorme de casos para valores más altos de R (para valores más altos de D).

• De estos ~ 6E5 resultados que tengo, calculo el elemento mínimo inalcanzable para cada valor de R de 1 a 40. Entonces, cada uno de los valores de R elige el mejor de estos valores de 6E5.

PROBLEMAS

• Este algoritmo no produce los mejores conjuntos de resultados , ni siquiera se cierra.

• Incluso fui a la cuarta y quinta mejor opción para D = 3, y no dieron ninguna mejora importante en los resultados. Por lo tanto, no sabía dónde debería ajustar mi algoritmo.

¿Dónde puedo ajustar este algoritmo para obtener mejores resultados?

¿Hay errores obvios que hace el algoritmo?

Cualquier comentario / sugerencia son bienvenidos.

_{Había otra pregunta sobre el mismo tema here . Estoy más interesado en saber dónde se puede mejorar mi algoritmo.}

Answer 1

De hecho, participé en este concurso, ya que notaste que obtuve el puesto 100 con 87.00 puntos acumulados. De hecho, utilicé su método porque me di cuenta de que generar una solución "razonable" para cada problema era el primer obstáculo que debía superar. En el momento en que lo ejecuté, los puntos generados fueron suficientes para acumularme alrededor de 94 puntos, pero a medida que las personas con mayores ingresos mejoraron sus puntajes, ese número cayó rápidamente a alrededor de 75.

Lo primero y más fácil que puedes hacer es darte cuenta de que tu programa se ejecuta en un instante, y si no lo haces, deberías pasar tiempo optimizando la mierda de eso primero. Una vez que se ejecuta en un tiempo suficientemente rápido, puede generar cada conjunto posible para D = 3 , R <= 5 en ningún momento. Luego puede usar los conjuntos en R = 5 como semillas para su algoritmo codicioso. Ahora, en lugar de una solución codiciosa, tiene unos pocos miles, y solo necesita realizar un seguimiento del valor más alto generado en cada nivel R y los valores que lo crean. Eso es bastante fácil de hacer, y esto hará que su puntaje sea superior a 80.

Pasé casi un mes optimizando la función que puede probar cualquier conjunto de entrada aleatoria, de modo que pude aumentar mi generador de semillas a R = 10 y ejecutarlo en aproximadamente 8 horas en un solo núcleo. Esto garantizaba tener la mejor solución posible para ''D = 3'', ''R <= 10'' y respuestas mucho mejores cuando R > 10 que con el resultado codicioso original. Esto hizo que mi puntaje estuviera bastante cerca de donde terminó después de que la R aumentara lo más alto posible para cada D tiempo pudiese ejecutar el programa en un solo día. Pude alcanzar R = 9 para D = 4 , R = 8 para D = 5 y R = 8 para D = 6 .

Una vez ejecutados, calculé que no podría aumentar R en 1 para ninguna D sobre los números que se acaban de enumerar y que complete su ejecución en el transcurso de mi vida. Obviamente, era hora de buscar una nueva técnica. Me di cuenta de que estaba haciendo un gran trabajo en la parte delantera al probar cada posible segmento inicial, así que, ¿por qué no cambiar algo de eso a la parte posterior mediante la prueba de conjuntos de resultados más profundos para cada uno de mis segmentos iniciales? En lugar de obtener el mejor resultado siguiente en el mismo nivel, realicé una vista anticipada de 2 niveles y tomé el mejor valor siguiente de dos niveles de profundidad. Por ejemplo, siempre comienza con un 1, luego enumera todos los valores para R = 2 (2, 3, 4) y luego para cada uno de ellos, evalúa todos los valores posibles para R = 3 . Entonces 2 (3, 4, 5, 6, 7), 3 (4, 5, 6, 7, 8), 4 (5, 6, 7) . Tome la más alta de todas esas evaluaciones y luego elija el valor en R = 2 que contiene el valor más alto para R = 3 . Esto requirió mucho más tiempo de procesamiento y me obligó a bajar el máximo R que podía usar para sembrarlo, pero produjo mejores resultados para las búsquedas más profundas.

En este punto, desistí de los enfoques codiciosos y utilicé esta competencia para ampliar mi conocimiento de AI. Intenté usar varias técnicas de Monte Carlo, así como un algoritmo genético básico. Aprendí mucho sobre Monte Carlo, y al buscar algunos de los mejores artistas en este concurso, encontré publicaciones sobre optimizaciones para los criterios de selección de Monte Carlo que estaba más allá de mi entendimiento. Desearía poder ayudarlo más, pero me siento confiado al argumentar que romper 90 puntos con un enfoque codicioso es muy poco probable en mi vida. Me interesaría ver cuánto mejor serían las respuestas si fueran multiproceso y se lanzara un montón de poder.

No tengo el trabajo que hice para este problema conmigo, pero recuerdo que mostrar que mirar hacia adelante y una mayor enumeración de semillas iniciales fueron las únicas dos posibles mejoras al algoritmo codicioso para este problema. Voy a por esas cosas esta noche y publicaré el proceso de pensamiento aquí si puedo encontrar las notas.

EDITAR: código originalmente publicado en el servidor que ha sido abandonado. Por favor, envíe un mensaje si desea que se vuelva a publicar.

Answer 2

El máximo del elemento inalcanzable más pequeño es bueno buscarlo solo en la última iteración. Mejor subobjetivo primario es el número de elementos alcanzables con un número dado de dardos. Una subobjetivo interesante podría ser

Nae * (Rt - Rc) / Rt + Msue, where

• Nae - número de elementos alcanzables (con un número dado de dardos)
• Rt - total de regiones disponibles
• Rc - regiones actualmente utilizadas (nivel actual de recursión)
• Msue - máximo de elemento inalcanzable más pequeño

¿Por qué es Nae más valioso que Msue en las primeras iteraciones? Los elementos más alcanzables que tenemos al principio, todos los elementos subsiguientes serían más empleables, producirían más combinaciones y alcanzarían elementos aún más alcanzables. Con la explosión de Nae, hay una alta probabilidad de que Msue también alcance un buen nivel. Sin embargo, en las últimas iteraciones, Msue se vuelve más importante y los nuevos elementos se usan más para "tapar los orificios", con la esperanza de que el último orificio para tapar esté lo más alejado posible.

La analogía física de este razonamiento sería el salto olímpico largo, donde el atleta al comienzo de la carrera primero acumula impulso, pero cuando se acerca a la línea de falta, sincroniza sus pasos para que el salto real sea más efectivo. El atleta no sincroniza sus pasos desde el inicio de la carrera, porque el impulso es más importante en esa etapa.

Answer 3

Gracias por una pregunta muy interesante! Pasé unos minutos entendiendo la pregunta.

No vi una formulación de notación del problema, así que, déjame intentarlo con una anotación aquí.

En primer lugar, una observación (como también lo hizo correctamente), una de las regiones debe ser 1, de lo contrario 1 no sería alcanzable.

En segundo lugar, dado que estamos tratando de MAXIMIZAR la puntuación inalcanzable, no tiene sentido repetir los valores de la región.

Entonces, eso da una solución degenerada (pero no óptima): 1, 2, 3, ... R

El valor de la función objetivo de esta solución degenerada es: D * R + 1

Por ejemplo, si tiene D = 4 dardos, y colorea su tablero de dardos con puntajes 1, 2. ..40, entonces es posible obtener todos los puntajes de los valores 1 a 160. 161 no es alcanzable.

Claramente, esta solución no es óptima, y ​​la solución óptima involucrará posiblemente algunos poderes de 2 y definitivamente algo de pensamiento.

Ahora para la notación:

Sea f (X, D, {Y_1..Y_R}) =

• 1 si se puede obtener una puntuación de X usando dardos D en una diana con rangos Y_1 ... Y_R
• 0 si es inalcanzable

Como ejemplo discutido anteriormente. f (160,4, {1..40}) = 1 y f (161,4, {1..40}) = 0

El valor de la función objetivo del rompecabezas se puede denotar como:

g (D, (Y_1..Y_R}) = Min X | f (X, D, {Y_1..Y_R}) = 0

Por la observación 1 anterior, podemos suponer que Y_1 = 1.

Además, una formulación recursiva de la función f puede ser la siguiente.

f (X, D, {1..Y_R} = 1 si:

• X = 0, o
• f (X-Y_j, D-1, {1..Y_R}) = 1 para algunos j

[Continuaré trabajando en esto y publicaremos más a medida que lo desarrolle.]

Answer 4

Una vez que haya aplicado fuerza bruta a algunos, es posible que vea algunos patrones para informar las búsquedas heurísticas. Por ejemplo, muchas de las soluciones principales tienen un patrón como este para D = 3, R = 40: una serie de pequeños incrementos, una serie de mayores incrementos, luego un salto de 2x seguido de una pequeña serie de incrementos pequeños.

Al menos, te dice que no vayas con la idea del subconjunto, donde los valores 3x30 son un subconjunto de 3x40, por ejemplo.