¿Cómo abordar un algoritmo de juego de adivinanzas de números (con un giro)?

Solución:

Combinaremos teoría de grafos y probabilidad:

El primer día, cree un conjunto de todas las soluciones factibles. Denotemos las soluciones establecidas como A1 = {a1 (1), a1 (2), …, a1 (n)}.

El segundo día puede volver a construir el conjunto de soluciones A2.

Ahora, para cada elemento en A2, deberá verificar si se puede alcanzar desde cada elemento de A1 (dada la tolerancia x%). Si es así, conecte A2 (n) a A1 (m). Si no se puede acceder a él desde ningún nodo en A1 (m), puede eliminar este nodo.

Básicamente, estamos construyendo un gráfico acíclico dirigido conectado.

Todas las rutas del gráfico son igualmente probables. Puede encontrar una solución exacta solo cuando hay un solo borde de Am a Am + 1 (de un nodo en Am a un nodo en Am + 1).

Claro, algunos nodos aparecen en más rutas que otros nodos. La probabilidad de cada nodo se puede deducir directamente en función del número de rutas que contiene este nodo.

Al asignar un peso a cada nodo, que equivale al número de rutas que conducen a este nodo, no es necesario mantener todo el historial, solo el día anterior.

Además, eche un vistazo a las ecuaciones difantinas lineales de valores no negativos: una pregunta que hice hace un tiempo. La respuesta aceptada es una excelente manera de enumarte todos los combos en cada paso.

Descargo de responsabilidad: cambié mi respuesta drásticamente después de eliminar temporalmente mi respuesta y volver a leer la pregunta con atención, ya que leí mal algunas partes críticas de la pregunta. Aunque todavía hacía referencia a temas y algoritmos similares, la respuesta mejoró enormemente después de que intenté resolver algunos de los problemas en C # yo mismo.

Versión de Hollywood

• El problema es un problema de satisfacción de restricciones dinámicas (DCSP), una variación de los problemas de satisfacción de restricciones (CSP).
• Utilice Monte Carlo para encontrar posibles soluciones para un día determinado si los valores y los rangos de cantidad no son pequeños. De lo contrario, use la fuerza bruta para encontrar todas las posibles soluciones.
• Usar Grabación de restricciones (relacionado con DCSP), aplicado en cascada a días anteriores para restringir el conjunto de soluciones potenciales.
• Cruza los dedos, apunta y disparo (Adivinar), basado en la probabilidad.
• (Opcional) Bruce Willis gana.

Versión original

Primero, me gustaría indicar lo que veo aquí, dos problemas principales:

1. La gran cantidad de posibles soluciones. Conociendo solo el número de artículos y el valor total, digamos 3 y 143, por ejemplo, dará como resultado mucho de posibles soluciones. Además, no es fácil tener un algoritmo que elija una solución válida sin probar inevitablemente soluciones no válidas (el total no es igual a 143).

2. Cuando se encuentran posibles soluciones para un día determinado D_I, uno debe encontrar una manera de eliminar las posibles soluciones con la información adicional proporcionada por {D_{yo + 1} .. D_{yo + n} }.

Establezcamos algunas bases para los próximos ejemplos:

• Mantengamos los mismos valores de elementos, todo el juego. Puede ser aleatorio o elegido por el usuario.
• Los posibles valores de los elementos están vinculados al rango muy limitado de [1-10], donde dos elementos no pueden tener el mismo valor.
• Ningún artículo puede tener una cantidad superior a 100. Eso significa: [0-100].

Para solucionar esto más fácilmente Me tomé la libertad de cambiar una restricción, lo que hace que el algoritmo converja más rápido:

• Esta regla anula la regla de “cantidad total”: puede agregar o eliminar cualquier número de artículos dentro del [1-10] rango, total, en un día. Sin embargo, no puede agregar o eliminar la misma cantidad de elementos, en total, más del doble. Esto también le da al juego un ciclo de vida máximo de 20 días.

Esta regla nos permite descartar soluciones con mayor facilidad. Y, con rangos no pequeños, hace que los algoritmos de Backtracking sigan siendo inútiles, al igual que su problema y reglas originales.

En mi humilde opinión, esta regla no es la esencia del juego, pero sólo un facilitador, permitiendo que la computadora resuelva el problema.

Problema 1: encontrar posibles soluciones

Para principiantes, problema 1. se puede resolver utilizando un algoritmo de Monte Carlo para encontrar un conjunto de posibles soluciones. La técnica es simple: Genere números aleatorios para valores y cantidades de artículos (dentro de su respectivo rango aceptado). Repita el proceso para la cantidad requerida de artículos. Verifique si la solución es aceptable o no. Eso significa verificar si los elementos tienen valores distintos y el total es igual a nuestro total objetivo (digamos, 143).

Si bien esta técnica tiene la ventaja de ser fácil de implementar, tiene algunos inconvenientes:

• No se garantiza que la solución del usuario aparezca en nuestros resultados.
• Hay muchas “fallas”. Por ejemplo, se necesitan más o menos 3.000.000 de intentos para encontrar 1.000 posibles soluciones dadas nuestras limitaciones.
• Lleva mucho tiempo: alrededor de 4 a 5 segundos en mi portátil perezoso.

¿Cómo solucionar estos inconvenientes? Bien…

• Limite el rango a valores más pequeños y
• Encuentre una cantidad adecuada de posibles soluciones para que exista una buena posibilidad de que la solución del usuario aparezca en su conjunto de soluciones.
• Utilice la heurística para encontrar soluciones más fácilmente (más sobre esto más adelante).

Tenga en cuenta que cuanto más restrinja los rangos, menos útil será el algoritmo de Monte Carlo, ya que habrá pocas soluciones válidas suficientes para iterar sobre todas ellas en un tiempo razonable. Para restricciones {3, [1-10], [0-100] } hay alrededor de 741.000.000 de soluciones válidas (no limitadas a un valor total objetivo). Monte Carlo se puede utilizar allí. Para 3, [1-5], [0-10] }, solo hay alrededor de 80.000. No es necesario utilizar Monte Carlo; fuerza bruta for los bucles funcionarán bien.

Creo que el problema 1 es lo que llamaría un problema de satisfacción de restricciones (o CSP).

Problema 2: restringir el conjunto de posibles soluciones

Dado el hecho de que problema 1 es un CSP, seguiría adelante y llamaría problema 2, y el problema en general, un CSP dinámico (o DCSP).

[DCSPs] son útiles cuando la formulación original de un problema se altera de alguna manera, generalmente porque el conjunto de restricciones a considerar evoluciona debido al entorno. Los DCSP se ven como una secuencia de CSP estáticos, cada uno de los cuales es una transformación del anterior en el que se pueden agregar (restricción) o eliminar (relajación) variables y restricciones.

Una técnica utilizada con CSP que podría ser útil para este problema se llama Grabación de restricciones:

• Con cada cambio en el entorno (el usuario ingresó valores para D_{yo + 1}), busque información sobre la nueva restricción: ¿Cuáles son las cantidades posiblemente “utilizadas” para la restricción de agregar-eliminar.
• Aplicar la restricción a todos los días anteriores en cascada. Los efectos ondulantes pueden reducir significativamente las posibles soluciones.

Para que esto funcione, necesita obtener un nuevo conjunto de posibles soluciones todos los días; Utilice la fuerza bruta o Monte Carlo. Luego, compare las soluciones de D_I a D_i-1 y mantenga solo las soluciones que puedan tener éxito con las soluciones de días anteriores sin violar las limitaciones.

Probablemente tendrá que llevar un historial de qué soluciones conducen a qué otras soluciones (probablemente en un gráfico dirigido). El registro de restricciones le permite recordar posibles cantidades de agregar-quitar y rechaza soluciones basadas en eso.

Hay muchos otros pasos que podrían tomarse para mejorar aún más su solución. Aquí tienes algunas ideas:

• Registre las restricciones para las combinaciones artículo-valor encontradas en soluciones de días anteriores. Rechace otras soluciones inmediatamente (ya que los valores de los elementos no deben cambiar). Incluso podría encontrar conjuntos de soluciones más pequeños para cada solución existente utilizando restricciones específicas de la solución para rechazar soluciones no válidas antes.
• Genere algunas soluciones “mutantes”, de historial completo, todos los días para “reparar” el caso en el que el D₁ El conjunto de soluciones no contiene la solución del usuario. Podría usar un algoritmo genético para encontrar una población mutante basada en un conjunto de soluciones existente).
• Use heurísticas para encontrar soluciones fácilmente (por ejemplo, cuando se encuentre una solución válida, intente encontrar variaciones de esta solución sustituyendo cantidades).
• Utilice heurísticas de comportamiento para predecir algunas acciones del usuario (por ejemplo, la misma cantidad para cada elemento, patrones extremos, etc.)
• Siga haciendo algunos cálculos mientras el usuario ingresa nuevas cantidades.

Dado todo esto, intente encontrar un sistema de clasificación basado en la ocurrencia de soluciones y heurísticas para determinar una solución candidata.

Este problema es imposible de resolver.

Supongamos que sabe exactamente para qué proporción se aumentó el número de elementos, no solo cuál es la proporción máxima para esto.

Un usuario tiene N frutas y usted tiene D días para adivinar.

En cada día obtienes N nuevas variables y luego tienes un total de D * N variables.

Para cada día, puede generar solo dos ecuaciones. Una ecuación es la suma de n_item * precio y otra se basa en una relación conocida. En total, tiene como máximo 2 * D ecuaciones si todas son independientes.

2 * D 2

---

---

Utiliza Nuestro Buscador