machine learning language español best java python algorithm machine-learning data-mining

language - machine learning java español



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

Estoy aprendiendo programación (Python y algoritmos) y estaba tratando de trabajar en un proyecto que me parece interesante. He creado algunos scripts de Python básicos, pero no estoy seguro de cómo acercarme a una solución de un juego que estoy tratando de construir.

Así es como funcionará el juego:

Los usuarios recibirán elementos con un valor. Por ejemplo,

Apple = 1 Pears = 2 Oranges = 3

Luego tendrán la oportunidad de elegir cualquier combo que quieran (es decir, 100 manzanas, 20 peras y una naranja). El único resultado que obtiene la computadora es el valor total (en este ejemplo, actualmente es de $ 143). La computadora intentará adivinar lo que tienen. Que obviamente no podrá obtener correctamente el primer turno.

Value quantity(day1) value(day1) Apple 1 100 100 Pears 2 20 40 Orange 3 1 3 Total 121 143

El siguiente turno el usuario puede modificar sus números pero no más del 5% de la cantidad total (o algún otro porcentaje que podamos elegir. Usaré un 5%, por ejemplo). Los precios de la fruta pueden cambiar (al azar) por lo que el valor total puede cambiar en función de eso también (por simplicidad, no estoy cambiando los precios de la fruta en este ejemplo). Usando el ejemplo anterior, en el día 2 del juego, el usuario devuelve un valor de $ 152 y $ 164 en el día 3. Aquí hay un ejemplo:

Quantity (day2) %change (day2) Value (day2) Quantity (day3) %change (day3) Value(day3) 104 104 106 106 21 42 23 46 2 6 4 12 127 4.96% 152 133 4.72% 164

* (Espero que las tablas se muestren bien, tuve que espaciarlas manualmente, así que espero que no solo lo haga en mi pantalla, si no funciona, hágamelo saber e intentaré cargar una captura de pantalla).

Estoy tratando de ver si puedo averiguar cuáles son las cantidades en el tiempo (suponiendo que el usuario tenga la paciencia para seguir ingresando números). Sé que en este momento mi única restricción es que el valor total no puede ser más del 5%, por lo que no puedo tener una precisión del 5% en este momento para que el usuario lo ingrese para siempre.

Lo que he hecho hasta ahora

Aquí está mi solución hasta ahora (no mucho). Básicamente, tomo todos los valores y descubro todas las posibles combinaciones de ellos (ya terminé esta parte). Luego tomo todos los posibles combos y los coloco en una base de datos como un diccionario (por ejemplo, por $ 143, podría haber una entrada en el diccionario {manzana: 143, Pears: 0, Naranjas: 0} ... hasta {manzana : 0, Pears: 1, Oranges: 47}. Hago esto cada vez que obtengo un nuevo número, así que tengo una lista de todas las posibilidades.

Aquí es donde estoy atascado. Al usar las reglas anteriores, ¿cómo puedo encontrar la mejor solución posible? Creo que necesitaré una función de acondicionamiento físico que compare automáticamente los datos de dos días y elimine cualquier posibilidad que tenga más del 5% de varianza de los datos de días anteriores.

Preguntas:

Entonces mi pregunta con el usuario cambiando el total y yo teniendo una lista de todas las probabilidades, ¿cómo debería abordar esto? ¿Qué necesito aprender? ¿Hay algún algoritmo o teorías que pueda usar que sean aplicables? O, para ayudarme a entender mi error, ¿puede sugerir qué reglas puedo agregar para hacer que este objetivo sea factible (si no está en su estado actual, estaba pensando en agregar más frutas y decir que deben elegir al menos 3, etc.)? ? Además, solo tengo una vaga comprensión de los algoritmos genéticos, pero pensé que podría usarlos aquí, ¿hay algo que pueda usar?

Estoy muy ansioso por aprender, así que cualquier consejo o consejo sería muy apreciado (solo por favor no me digas que este juego es imposible).

ACTUALIZACIÓN: Obtener comentarios de que esto es difícil de resolver. Así que pensé en agregar otra condición para el juego que no interfiera con lo que el jugador está haciendo (el juego sigue siendo el mismo para ellos) pero todos los días el valor de las frutas cambia el precio (al azar). ¿Eso lo haría más fácil de resolver? Porque dentro de un 5% de movimiento y ciertos cambios en el valor de la fruta, solo unas pocas combinaciones son probables a lo largo del tiempo.

Día 1, todo es posible y obtener un rango lo suficientemente cercano es casi imposible, pero como los precios de las frutas cambian y el usuario solo puede elegir un cambio del 5%, entonces no debería (con el tiempo) el rango ser estrecho y estrecho. En el ejemplo anterior, si los precios son lo suficientemente volátiles, creo que podría forzar una solución que me diera un rango para adivinar, pero estoy tratando de descubrir si hay una solución más elegante u otras soluciones para seguir estrechando este rango. hora.

ACTUALIZACIÓN2: Después de leer y preguntar, creo que este es un problema oculto de Markov / Viterbi que rastrea los cambios en los precios de la fruta, así como la suma total (ponderando el último punto de datos, el más pesado). Aunque no estoy seguro de cómo aplicar la relación. Creo que este es el caso y podría estar equivocado, pero al menos estoy empezando a sospechar que se trata de algún tipo de problema de aprendizaje automático.

Actualización 3: me crearon un caso de prueba (con números más pequeños) y un generador para ayudar a automatizar los datos generados por el usuario y estoy tratando de crear un gráfico a partir de él para ver qué es más probable.

Aquí está el código, junto con los valores totales y los comentarios sobre lo que los usuarios realmente son las cantidades de fruta.

#!/usr/bin/env python import itertools # Fruit price data fruitPriceDay1 = {''Apple'':1, ''Pears'':2, ''Oranges'':3} fruitPriceDay2 = {''Apple'':2, ''Pears'':3, ''Oranges'':4} fruitPriceDay3 = {''Apple'':2, ''Pears'':4, ''Oranges'':5} # Generate possibilities for testing (warning...will not scale with large numbers) def possibilityGenerator(target_sum, apple, pears, oranges): allDayPossible = {} counter = 1 apple_range = range(0, target_sum + 1, apple) pears_range = range(0, target_sum + 1, pears) oranges_range = range(0, target_sum + 1, oranges) for i, j, k in itertools.product(apple_range, pears_range, oranges_range): if i + j + k == target_sum: currentPossible = {} #print counter #print ''Apple'', '':'', i/apple, '','', ''Pears'', '':'', j/pears, '','', ''Oranges'', '':'', k/oranges currentPossible[''apple''] = i/apple currentPossible[''pears''] = j/pears currentPossible[''oranges''] = k/oranges #print currentPossible allDayPossible[counter] = currentPossible counter = counter +1 return allDayPossible # Total sum being returned by user for value of fruits totalSumDay1=26 # Computer does not know this but users quantities are apple: 20, pears 3, oranges 0 at the current prices of the day totalSumDay2=51 # Computer does not know this but users quantities are apple: 21, pears 3, oranges 0 at the current prices of the day totalSumDay3=61 # Computer does not know this but users quantities are apple: 20, pears 4, oranges 1 at the current prices of the day graph = {} graph[''day1''] = possibilityGenerator(totalSumDay1, fruitPriceDay1[''Apple''], fruitPriceDay1[''Pears''], fruitPriceDay1[''Oranges''] ) graph[''day2''] = possibilityGenerator(totalSumDay2, fruitPriceDay2[''Apple''], fruitPriceDay2[''Pears''], fruitPriceDay2[''Oranges''] ) graph[''day3''] = possibilityGenerator(totalSumDay3, fruitPriceDay3[''Apple''], fruitPriceDay3[''Pears''], fruitPriceDay3[''Oranges''] ) # Sample of dict = 1 : {''oranges'': 0, ''apple'': 0, ''pears'': 0}..70 : {''oranges'': 8, ''apple'': 26, ''pears'': 13} print graph

Combinaremos la teoría de gráficos y la probabilidad:

El primer día, construya un conjunto de todas las soluciones posibles. Permite denotar las soluciones establecidas como A1 = {a1 (1), a1 (2), ..., a1 (n)}.

El segundo día puede volver a crear las soluciones establecidas A2.

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

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

Todos los caminos en el gráfico son igualmente probables. Puede encontrar una solución exacta solo cuando hay un único borde desde Am a Am + 1 (desde 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 es igual al número de rutas que conduce a este nodo, no hay necesidad de mantener todo el historial, sino solo el día anterior.

Además, eche un vistazo a las ecuaciones lineales de difenatina 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.

Escribí un programa para jugar el juego. Por supuesto, tuve que automatizar el lado humano, pero creo que lo hice todo de tal manera que no debería invalidar mi enfoque cuando se juega contra un humano real.

Abordé esto desde una perspectiva de aprendizaje automático y traté el problema como un modelo oculto de Markov donde el precio total era la observación. Mi solución es usar un filtro de partículas. Esta solución está escrita en Python 2.7 usando NumPy y SciPy.

Indiqué cualquier suposición que hice explícitamente en los comentarios o implícitamente en el código. También establecí algunas restricciones adicionales para que el código se ejecute de manera automatizada. No está particularmente optimizado ya que traté de equivocarme en la comprensión lateral en lugar de la velocidad.

Cada iteración genera las cantidades verdaderas actuales y la conjetura. Simplemente canalizo la salida a un archivo para poder revisarlo fácilmente. Una extensión interesante sería trazar el resultado en un gráfico ya sea 2D (para 2 frutas) o 3D (para 3 frutas). Entonces, usted podría ver el filtro de partículas enfocarse en la solución.

Actualizar:

Editado el código para incluir parámetros actualizados después de ajustar. Llamadas de trazado incluidas usando matplotlib (vía pylab). El trazado funciona en Linux-Gnome, su kilometraje puede variar. NUM_FRUITS predeterminado a 2 para trazar el soporte. Solo comente todas las llamadas de pylab para eliminar el trazado y poder cambiar NUM_FRUITS a cualquier cosa.

Hace un buen trabajo al estimar el fxn actual representado por UnknownQuantities X Prices = TotalPrice. En 2D (2 frutas) esta es una línea, en 3D (3 frutas) sería un avión. Parece que hay muy pocos datos para que el filtro de partículas se centre de manera confiable en las cantidades correctas. Necesita un poco más de inteligencia en la parte superior del filtro de partículas para realmente reunir la información histórica. Podría intentar convertir el filtro de partículas en 2º o 3er orden.

Actualización 2:

He estado jugando con mi código, mucho. Probé un montón de cosas y ahora presento el programa final que voy a hacer (comenzando a quemarme con esta idea).

Cambios:

Las partículas ahora usan puntos flotantes en lugar de números enteros. No estoy seguro si esto tuvo algún efecto significativo, pero es una solución más general. Redondear a enteros solo se hace al hacer una suposición.

El trazado muestra las cantidades verdaderas como el cuadrado verde y la conjetura actual como el cuadrado rojo. Las partículas actualmente creídas se muestran como puntos azules (de acuerdo con la medida en que los creemos). Esto hace que sea realmente fácil ver qué tan bien está funcionando el algoritmo. (Trazado también probado y trabajando en Win 7 de 64 bits).

Se agregaron parámetros para activar / desactivar el cambio de cantidad y el cambio de precio. Por supuesto, tanto ''apagado'' no es interesante.

Hace un buen trabajo, pero, como se ha señalado, es un problema realmente difícil, por lo que obtener la respuesta exacta es difícil. Desactivar CHANGE_QUANTITIES produce el caso más simple. Puede obtener una apreciación de la dificultad del problema si ejecuta 2 frutas con CHANGE_QUANTITIES desactivado. Vea cuán rápido se enfoca en la respuesta correcta y luego vea qué tan difícil es a medida que aumenta la cantidad de fruta.

También puede obtener una perspectiva de la dificultad manteniendo activado CHANGE_QUANTITIES, pero ajustando MAX_QUANTITY_CHANGE desde valores muy pequeños (.001) a valores "grandes" (.05).

Una situación en la que se lucha es si la dimensión (una cantidad de fruta) se acerca a cero. Porque está utilizando un promedio de partículas para adivinar que siempre se desviará de un límite duro como cero.

En general, esto hace un gran tutorial de filtro de partículas.

from __future__ import division import random import numpy import scipy.stats import pylab # Assume Guesser knows prices and total # Guesser must determine the quantities # All of pylab is just for graphing, comment out if undesired # Graphing only graphs first 2 FRUITS (first 2 dimensions) NUM_FRUITS = 3 MAX_QUANTITY_CHANGE = .01 # Maximum percentage change that total quantity of fruit can change per iteration MAX_QUANTITY = 100 # Bound for the sake of instantiating variables MIN_QUANTITY_TOTAL = 10 # Prevent degenerate conditions where quantities all hit 0 MAX_FRUIT_PRICE = 1000 # Bound for the sake of instantiating variables NUM_PARTICLES = 5000 NEW_PARTICLES = 500 # Num new particles to introduce each iteration after guessing NUM_ITERATIONS = 20 # Max iterations to run CHANGE_QUANTITIES = True CHANGE_PRICES = True '''''' Change individual fruit quantities for a random amount of time Never exceed changing fruit quantity by more than MAX_QUANTITY_CHANGE '''''' def updateQuantities(quantities): old_total = max(sum(quantities), MIN_QUANTITY_TOTAL) new_total = old_total max_change = int(old_total * MAX_QUANTITY_CHANGE) while random.random() > .005: # Stop Randomly change_index = random.randint(0, len(quantities)-1) change_val = random.randint(-1*max_change,max_change) if quantities[change_index] + change_val >= 0: # Prevent negative quantities quantities[change_index] += change_val new_total += change_val if abs((new_total / old_total) - 1) > MAX_QUANTITY_CHANGE: quantities[change_index] -= change_val # Reverse the change def totalPrice(prices, quantities): return sum(prices*quantities) def sampleParticleSet(particles, fruit_prices, current_total, num_to_sample): # Assign weight to each particle using observation (observation is current_total) # Weight is the probability of that particle (guess) given the current observation # Determined by looking up the distance from the hyperplane (line, plane, hyperplane) in a # probability density fxn for a normal distribution centered at 0 variance = 2 distances_to_current_hyperplane = [abs(numpy.dot(particle, fruit_prices)-current_total)/numpy.linalg.norm(fruit_prices) for particle in particles] weights = numpy.array([scipy.stats.norm.pdf(distances_to_current_hyperplane[p], 0, variance) for p in range(0,NUM_PARTICLES)]) weight_sum = sum(weights) # No need to normalize, as relative weights are fine, so just sample un-normalized # Create new particle set weighted by weights belief_particles = [] belief_weights = [] for p in range(0, num_to_sample): sample = random.uniform(0, weight_sum) # sum across weights until we exceed our sample, the weight we just summed is the index of the particle we''ll use p_sum = 0 p_i = -1 while p_sum < sample: p_i += 1 p_sum += weights[p_i] belief_particles.append(particles[p_i]) belief_weights.append(weights[p_i]) return belief_particles, numpy.array(belief_weights) '''''' Generates new particles around the equation of the current prices and total (better particle generation than uniformly random) '''''' def generateNewParticles(current_total, fruit_prices, num_to_generate): new_particles = [] max_values = [int(current_total/fruit_prices[n]) for n in range(0,NUM_FRUITS)] for p in range(0, num_to_generate): new_particle = numpy.array([random.uniform(1,max_values[n]) for n in range(0,NUM_FRUITS)]) new_particle[-1] = (current_total - sum([new_particle[i]*fruit_prices[i] for i in range(0, NUM_FRUITS-1)])) / fruit_prices[-1] new_particles.append(new_particle) return new_particles # Initialize our data structures: # Represents users first round of quantity selection fruit_prices = numpy.array([random.randint(1,MAX_FRUIT_PRICE) for n in range(0,NUM_FRUITS)]) fruit_quantities = numpy.array([random.randint(1,MAX_QUANTITY) for n in range(0,NUM_FRUITS)]) current_total = totalPrice(fruit_prices, fruit_quantities) success = False particles = generateNewParticles(current_total, fruit_prices, NUM_PARTICLES) #[numpy.array([random.randint(1,MAX_QUANTITY) for n in range(0,NUM_FRUITS)]) for p in range(0,NUM_PARTICLES)] guess = numpy.average(particles, axis=0) guess = numpy.array([int(round(guess[n])) for n in range(0,NUM_FRUITS)]) print "Truth:", str(fruit_quantities) print "Guess:", str(guess) pylab.ion() pylab.draw() pylab.scatter([p[0] for p in particles], [p[1] for p in particles]) pylab.scatter([fruit_quantities[0]], [fruit_quantities[1]], s=150, c=''g'', marker=''s'') pylab.scatter([guess[0]], [guess[1]], s=150, c=''r'', marker=''s'') pylab.xlim(0, MAX_QUANTITY) pylab.ylim(0, MAX_QUANTITY) pylab.draw() if not (guess == fruit_quantities).all(): for i in range(0,NUM_ITERATIONS): print "------------------------", i if CHANGE_PRICES: fruit_prices = numpy.array([random.randint(1,MAX_FRUIT_PRICE) for n in range(0,NUM_FRUITS)]) if CHANGE_QUANTITIES: updateQuantities(fruit_quantities) map(updateQuantities, particles) # Particle Filter Prediction print "Truth:", str(fruit_quantities) current_total = totalPrice(fruit_prices, fruit_quantities) # Guesser''s Turn - Particle Filter: # Prediction done above if CHANGE_QUANTITIES is True # Update belief_particles, belief_weights = sampleParticleSet(particles, fruit_prices, current_total, NUM_PARTICLES-NEW_PARTICLES) new_particles = generateNewParticles(current_total, fruit_prices, NEW_PARTICLES) # Make a guess: guess = numpy.average(belief_particles, axis=0, weights=belief_weights) # Could optimize here by removing outliers or try using median guess = numpy.array([int(round(guess[n])) for n in range(0,NUM_FRUITS)]) # convert to integers print "Guess:", str(guess) pylab.cla() #pylab.scatter([p[0] for p in new_particles], [p[1] for p in new_particles], c=''y'') # Plot new particles pylab.scatter([p[0] for p in belief_particles], [p[1] for p in belief_particles], s=belief_weights*50) # Plot current particles pylab.scatter([fruit_quantities[0]], [fruit_quantities[1]], s=150, c=''g'', marker=''s'') # Plot truth pylab.scatter([guess[0]], [guess[1]], s=150, c=''r'', marker=''s'') # Plot current guess pylab.xlim(0, MAX_QUANTITY) pylab.ylim(0, MAX_QUANTITY) pylab.draw() if (guess == fruit_quantities).all(): success = True break # Attach new particles to existing particles for next run: belief_particles.extend(new_particles) particles = belief_particles else: success = True if success: print "Correct Quantities guessed" else: print "Unable to get correct answer within", NUM_ITERATIONS, "iterations" pylab.ioff() pylab.show()

Este problema es imposible de resolver.

Digamos que usted sabe exactamente para qué proporción se aumentó la cantidad de elementos, no solo cuál es la proporción máxima para esto.

Un usuario tiene N frutas y tienes D días de conjeturas.

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

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

2 * D <N * D para todo N> 2

Descargo de responsabilidad: cambié mi respuesta dramáticamente después de eliminar temporalmente mi respuesta y volver a leer la pregunta con cuidado ya que he leído mal algunas partes críticas de la pregunta. Mientras seguía haciendo referencia a temas y algoritmos similares, la respuesta mejoró mucho después de que intenté resolver parte del problema en C #.

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 restricción (CSP).
  • Use Monte Carlo para buscar soluciones potenciales para un día determinado si los valores y los rangos de cantidad no son mínimos. De lo contrario, use la fuerza bruta para encontrar todas las posibles soluciones.
  • Utilice la grabación de restricción (relacionada con DCSP), aplicada en cascada a los días anteriores para restringir el conjunto de soluciones potenciales.
  • Cruza los dedos, apunta y dispara (Adivina), según la probabilidad.
  • (Opcional) Bruce Willis gana.

Versión original

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

  1. El gran número de soluciones posibles. Saber solo el número de elementos y el valor total, digamos 3 y 143, por ejemplo, arrojará muchas soluciones posibles. Además, no es fácil tener un algoritmo que elija una solución válida sin intentar soluciones inválidas (total no igual a 143.)

  2. Cuando se encuentran posibles soluciones para un día dado D i , se debe encontrar la manera de eliminar soluciones potenciales con la información agregada dada por {D i + 1 .. D i + n }.

Establezcamos algunas bases para los próximos ejemplos:

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

Para resolver 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:

  • La regla de "cantidad total" queda anulada por esta regla: puede agregar o eliminar cualquier cantidad de elementos dentro del rango [1-10], total, en un día. Sin embargo, no puede agregar o eliminar la misma cantidad de elementos, en total, más de dos veces. Esto también le da al juego un ciclo de vida máximo de 20 días.

Esta regla nos permite descartar soluciones más fácilmente. Y, con rangos no minúsculos, hace que los algoritmos de Retroceso sigan siendo inútiles, al igual que el problema y las reglas originales.

En mi humilde opinión, esta regla no es la esencia del juego, sino solo un facilitador, que permite que la computadora resuelva el problema.

Problema 1: Encontrar soluciones potenciales

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

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

  • La solución del usuario no está garantizada para aparecer en nuestros resultados.
  • Hay muchos "errores". Por ejemplo, lleva más o menos 3,000,000 intentos para encontrar 1,000 soluciones potenciales dadas nuestras limitaciones.
  • Lleva mucho tiempo: alrededor de 4 a 5 segundos en mi laptop perezosa.

¿Cómo evitar estos inconvenientes? Bien...

  • Limite el rango a valores más pequeños y
  • Encuentre una cantidad adecuada de posibles soluciones, por lo que es muy probable que la solución del usuario aparezca en su conjunto de soluciones.
  • Use 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 para repetirlos en un tiempo razonable. Para las 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 es utilizable allí. Para {3, [1-5], [0-10]}, solo hay alrededor de 80,000. No es necesario usar Monte Carlo; la fuerza bruta for bucles hará bien.

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

Problema 2: Restringir el conjunto de soluciones potenciales

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

[DCSP] 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 medio ambiente. Los DCSP se ven como una secuencia de CSP estáticos, cada uno una transformación del anterior en el que las variables y restricciones se pueden agregar (restricción) o eliminar (relajación).

Una técnica utilizada con CSP que podría ser útil para este problema se denomina grabación de restricción :

  • Con cada cambio en el entorno (valores ingresados ​​por el usuario para D i + 1 ), encuentre información acerca de la nueva restricción: ¿Cuáles son las cantidades posiblemente "utilizadas" para la restricción add-remove?
  • Aplica la restricción a cada día anterior en cascada. Los efectos de ondulación pueden reducir significativamente las posibles soluciones.

Para que esto funcione, necesita obtener un nuevo conjunto de soluciones posibles todos los días; Usa la fuerza bruta o Monte Carlo. Luego, compare las soluciones de D i a D i-1 y conserve solo las soluciones que pueden tener éxito con las soluciones de días anteriores sin violar las restricciones.

Probablemente tendrá que mantener un historial de qué soluciones conducen a qué otras soluciones (probablemente en un gráfico dirigido). El registro de restricción le permite recordar posibles cantidades de eliminación y eliminación y rechaza soluciones basadas en eso.

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

  • Restricciones de registro para combinaciones de valores de elementos encontrados en soluciones de días anteriores. Rechace otras soluciones de inmediato (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 las soluciones no válidas anteriormente.
  • Genere soluciones "mutantes" de historia completa todos los días para "reparar" el caso en el que el conjunto de soluciones D 1 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 la heurística para encontrar soluciones fácilmente (por ejemplo, cuando se encuentre una solución válida, intente y encuentre variaciones de esta solución sustituyendo cantidades).
  • Use heurísticas conductuales 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.

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

For your initial rules:

From my school years, I would say that if we make an abstraction of the 5% changes, we have everyday an equation with three unknown values (sorry I don''t know the maths vocabulary in English), which are the same values as previous day. At day 3, you have three equations, three unknown values, and the solution should be direct.

I guess the 5% change each day may be forgotten if the values of the three elements are different enough, because, as you said, we will use approximations and round the numbers.

For your adapted rules:

Too many unknowns - and changing - values in this case, so there is no direct solution I know of. I would trust Lior on this; his approach looks fine! (If you have a limited range for prices and quantities.)