Nombre del problema de la cuenta atrás Números redondos - y soluciones algorítmicas?

10

Para los no británicos en la audiencia, hay un segmento de un programa de juegos diurno donde los concursantes tienen un conjunto de 6 números y un número objetivo generado aleatoriamente. Tienen que alcanzar el número objetivo usando cualquiera (pero no necesariamente todos) de los 6 números usando solo operadores aritméticos. Todos los cálculos deben dar como resultado enteros positivos.

Un ejemplo: Youtube: Countdown: ¿el juego de números más extraordinario?

Se proporciona una descripción detallada en Wikipedia: Countdown (Game Show)

Por ejemplo:

  • El contendiente selecciona 6 números: dos grandes (las posibilidades incluyen 25, 50, 75, 100) y cuatro pequeños (números 1 .. 10, cada uno incluido dos veces en el grupo).
  • Los números recogidos están 75, 50, 2, 3, 8, 7se dan con un número objetivo de 812.
  • Un intento es (75 + 50 - 8) * 7 - (3 * 2) = 813 (Esto obtiene 7 puntos para una solución dentro de 5 del objetivo)
  • Una respuesta exacta sería (50 + 8) * 7 * 2 = 812 (Esto habría obtenido 10 puntos que coinciden exactamente con el objetivo).

Obviamente, este problema existía antes del advenimiento de la televisión, pero el artículo de Wikipedia no le da nombre. También vi este juego en una escuela primaria a la que asistí, donde el juego se llamaba "Crypto" como una competencia entre clases, pero buscarlo ahora no revela nada.

Participé varias veces y mi padre escribió una hoja de cálculo de Excel que intentaba forzar el problema, no recuerdo cómo funcionó (solo que no funcionó, con el límite de filas de 65535 de Excel), pero seguramente debe haber una solución algorítmica para el problema. Tal vez haya una solución que funcione de la manera en que lo hace la cognición humana (por ejemplo, en paralelo para encontrar números 'lo suficientemente cerca', luego tomar candidatos y realizar operaciones 'más pequeñas').

Dai
fuente
1
He resuelto esto gráficamente - nodos utilizan para representar los resultados de los cálculos y los bordes para representar las operaciones que se pueden hacer en esos números, a continuación, utilizar un algoritmo de búsqueda gráfica para encontrar la ruta deseada
ell
1
A partir de una lectura de las reglas, parece que es posible no llegar a una solución perfecta, por ejemplo, si los números seleccionados son (1, 1, 2, 2, 3, 3) y el número objetivo es 999. Entonces realmente El objetivo de cualquier algoritmo sería encontrar la solución más cercana posible.
Rich Smith
1
@ell: ¿Su solución de búsqueda de gráficos es básicamente una búsqueda de fuerza bruta?
Martin
Simplemente utilicé una primera búsqueda en profundidad en mi implementación, pero no veo por qué algo como Dijkstra no se pudo utilizar.
ell
1
Tenemos algunos programas similares de los Estados: nos ceñimos aproximadamente 6 idiotas sub-leer y escribir en una casa durante varias semanas y la película que hablen de uno al otro y gritando a la otra. Eso es lo más cerca que nuestro televisor llega a algo tan intelectual en los programas populares.
RBarryYoung

Respuestas:

4

Descargo de responsabilidad: esta respuesta no responde la pregunta por completo. Pero es demasiado largo para un comentario.

NP-hard? Creo que este problema podría ser NP-duro .

Considere un caso especial del problema de la mochila :

Dado un conjunto de enteros positivos y un entero positivo b , ¿existe un subconjunto del conjunto tal que la suma de todos los enteros en ese subconjunto sea igual a b ?

Esto suena algo similar a nuestro problema de cuenta regresiva, y parece ser mucho más simple. Sin embargo, la mochila (y este caso especial de la mochila) es NP-hard (y NP-complete, por supuesto).

No logré usar esto como prueba de que Countdown es NP-hard. No pude deshacerme de la división. Considere que tenemos mil 2, y b = 7. Esto nunca será solucionable con Knapsack, pero siempre (?) Con Countdown, al menos en todas las formas en que intenté transferir el problema.

Ahora, si Countdown realmente fue NP-hard, podríamos deducir que con una probabilidad muy alta no hay algoritmo que sea significativamente más eficiente que la fuerza bruta que intenta todas las posibilidades. (Y si encontramos un algoritmo así, seremos muy famosos).

No, no creo que deba haber un algoritmo eficiente.

Heurística El video de Youtube vinculado en la pregunta tiene un buen ejemplo: el concursante encontró una respuesta exacta 952 = ((100 + 6) * 3 * 75 - 50) / 25. Eso está completamente en contra de mi intuición, nunca lo habría intentado que la primera vez: Produzca un número muy grande, luego divídalo y produzca el resultado.

Por otro lado, los humanos sentimos que no necesitamos intentar (ejemplo arbitrario) 50 * 75 * 100/2/3/7 para alcanzar un número de tres dígitos. Pero las computadoras no sienten nada, simplemente calculan.

Después de todo, si implementamos algunas heurísticas, y esta heurística no encuentra una solución exacta, aún tendremos que probar todas las demás soluciones para asegurarnos de que realmente no haya ninguna.

Lo que hace el concursante en el video de Youtube es, creo, verificar muy rápidamente una gran cantidad de posibilidades y descartar rápidamente aquellas que no darán (o probablemente no darán) una solución.

Conclusión. Al implementar un algoritmo, uno podría tener cuidado de eliminar cálculos iguales como a / b / c = a / (b * c), pero creo que esto es bastante difícil de hacer y no sé si esto mejora significativamente el tiempo de ejecución.

Las computadoras, por supuesto, son más rápidas que los humanos al verificar una gran cantidad de posibilidades. Y hoy en día, incluso los teléfonos inteligentes son tan rápidos que pueden resolver este problema, creo, en un segundo simplemente probando todas las posibilidades. (No probé esto.) Solo hay seis números, sería diferente si hubiera, por ejemplo, 60 de ellos.

Martín
fuente
La solución al ejemplo, aunque es extremadamente impresionante, no es tan complicada como parece. Es probable que su proceso de pensamiento, menos las cosas más obvias que haya intentado, haya sido "Puedo llegar a 954 usando (100 + 6) * 9, que puedo hacer a través de (100 + 6) * 3 * 75/25. Me quedan 50 y 50/25 son dos, así que puedo quitar los 50 (100 + 6) * 3 * 75 antes de dividirlos por 25 ".
Tim Down
1

Un algoritmo no es realmente muy difícil.

Dados dos números a y b, podemos producir los resultados a + b, abs (a - b) (no sé si se permiten números negativos, en cuyo caso podemos producir a - by a + b), a * b, y posiblemente a / b o b / a si el resultado es un entero. Entonces, los resultados posibles son un conjunto de hasta cinco números. Llame a este conjunto S (a, b).

Toma seis números a, b, c, d, e y f.

Para cada subconjunto de dos números, encuentre los números que pueden producir.

Luego, para cada subconjunto de tres números, encuentre los números que pueden producir: S (a, b, c) = S (S (a, b), c) unión S (S (a, c), b) unión S ( S (b, c), a).

Luego lo mismo para cada subconjunto de 4 o 5 números, luego para los 6 números.

gnasher729
fuente