Comment aborder un jeu de devinette de nombre (avec une torsion) algorithme?

Ce problème est impossible à résoudre.

disons que vous savez exactement pour quel ratio le nombre d'articles a été augmenté, pas seulement ce qui est le ratio maximum pour cela.

un utilisateur A N fruits et vous avez D jours de deviner.

dans chaque jour vous obtenez N nouvelles variables et puis vous avez dans Total D*N variables.

Pour chaque jour, vous pouvez générer que deux équations. Une équation est la somme de n_item*le prix et les autres est basé sur un taux. Au total, vous avez au maximum 2 * d équations si elles sont toutes indépendantes.

2*D < N*D pour tous N >2

avertissement: j'ai changé ma réponse de façon dramatique après avoir temporairement supprimé ma réponse et relu la question attentivement car j'ai mal lu certaines parties critiques de la question. Tout en faisant référence à des sujets et des algorithmes similaires, la réponse a été grandement améliorée après que j'ai essayé de résoudre certains du problème dans C# moi-même.

Hollywood version

• le problème est une contrainte dynamique problème de satisfaction (DCSP), une variation de problèmes de satisfaction contrainte (CSP.)
• utiliser Monte Carlo pour trouver des solutions possibles pour un jour donné si les valeurs et les plages de quantité ne sont pas infimes. Sinon, utilisez la force brute pour trouver toutes les solutions possibles.
• Utiliser Contrainte d'Enregistrement (liées à la DCSP), appliqué en cascade aux jours précédents pour restreindre l' ensemble de solutions possibles.
• croiser les doigts, le but et les tirer (Devinez), fondée sur des probabilités.
• (optionnel) Bruce Willis gagne.

version originale

tout d'abord, je voudrais dire ce que je vois deux problèmes principaux ici:

1. le simple nombre de solutions possibles. Sachant seulement le nombre de les éléments et la valeur totale, disons 3 et 143 par exemple, donnera beaucoup des solutions possibles. De plus, il n'est pas facile d'avoir un algorithme qui choisit une solution valide sans nécessairement essayer des solutions invalides (total non égal à 143.)

2. lorsque des solutions possibles sont trouvées pour un jour donné D _i , il faut trouver un moyen d'éliminer les solutions potentielles avec les informations supplémentaires fournies par { D _i+1 .. D _i+n }.

posons quelques bases pour les exemples à venir:

• permet de garder les mêmes valeurs d'article, l'ensemble du jeu. Il peut soit être aléatoire ou choisi par l'utilisateur.
• les valeurs possibles des articles sont liées à la gamme très limitée de [1-10], où deux articles ne peuvent pas avoir la même valeur.
• aucun article ne peut avoir une quantité supérieure à 100. Cela signifie que: [0-100].

afin de résoudre ce plus facilement j'ai pris la liberté de changer une contrainte , ce qui rend l'algorithme converge plus rapide:

• la règle de la "quantité totale" est annulée par cette règle: vous pouvez ajouter ou supprimer n'importe quel nombre d'articles dans l'intervalle [1-10], total, en une journée. Cependant, vous ne pouvez pas ajouter ou supprimer le même nombre d'éléments, au total, plus de à deux reprises. Cela donne aussi au jeu un cycle de vie maximum de 20 jours.

cette règle nous permet d'écarter des solutions plus facilement. Et, avec des plages non-minuscules, rend " backtracking algorithms toujours inutile, tout comme votre problème original et les règles.

À mon humble avis, cette règle n'est pas la essence du jeu, mais seulement un facilitateur, permettant à l'ordinateur de résoudre le problème.

Problème 1: trouver des solutions potentielles

pour commencer, problème 1. peut être résolu en utilisant un algorithme de Monte Carlo pour trouver un ensemble de solutions potentielles. La technique est simple: générer des nombres aléatoires pour des valeurs et des quantités d'items (dans leur plage respective acceptée). Répétez le processus pour le nombre requis de points. Vérifier si la solution est acceptable. Cela signifie que vérifier si les éléments ont des valeurs distinctes et le total est égal à notre total cible (disons, 143.)

bien que cette technique ait l'avantage d'être facile à mettre en œuvre, elle présente certains inconvénients:

• la solution de l'utilisateur n'est pas garantie d'apparaître dans nos résultats.
• Il y a beaucoup de "manque". Par exemple, il faut plus ou moins 3.000.000 tente de trouver 1.000 solutions potentielles compte tenu de nos contraintes.
• cela prend beaucoup de temps: environ 4 à 5 secondes sur mon ordinateur portable paresseux.

comment contourner cet inconvénient? Bien...

• Limiter la plage pour les plus petits, les valeurs et les 1519130920"
• trouver un nombre adéquat de solutions potentielles de sorte qu'il ya une bonne chance de la solution de l'utilisateur apparaît dans votre ensemble de solutions.
• utilisez l'heuristique pour trouver des solutions plus facilement (plus sur cela plus tard.)

notez que plus vous limitez les plages, moins l'algorithme de Monte Carlo sera utile, car il y aura peu de solutions valides pour les itérer toutes dans un délai raisonnable. Pour les contraintes { 3, [1-10], [0-100] } il y a environ 741.000.000 de solutions valables (non limitées à une valeur cible totale.) Monte Carlo y est utilisable. Pour { 3, [1-5], [0-10] }, il n'y en a qu'environ 80 000. Pas besoin D'utiliser Monte Carlo; brute force for boucles fera juste fin.

je crois que le "151920920 problème de" 1 est ce que l'on pourrait appeler un Constraint satisfaction problem (ou CSP.)

problème 2: restreindre l'ensemble des solutions possibles

étant donné que problème 1 est un CSP, je vais de l'avant et appeler problème 2 , et le problème en général, un CSP dynamique (ou DCSP.)

[DCSPs] sont utiles lorsque la formulation originale d'un problème est modifié d'une certaine façon, généralement parce que l'ensemble de les contraintes à considérer évoluent en raison de l'environnement. DCSPs sont considérés comme une séquence d'EFPC statiques, chacun une transformation de la précédente dans laquelle des variables et des contraintes peuvent être ajoutées (restriction) ou enlevé (relaxation).

une technique utilisée avec CSPs qui pourrait être utile à ce problème est appelé enregistrement de contrainte :

• à chaque changement d'environnement (valeurs saisies par l'utilisateur pour D _i+1 ), trouver des informations sur la nouvelle contrainte: quelles sont les quantités éventuellement" utilisées " pour la contrainte add-remove.
• appliquer la contrainte à chaque jour précédent en cascade. Les effets d'ondulation pourraient réduire considérablement les solutions possibles.

pour que cela fonctionne, vous devez obtenir un nouvel ensemble de solutions possibles chaque jour; utilisez soit la force brute ou Monte Carlo. Ensuite, comparez les solutions de D _i à d _i-1 et conservez seulement les solutions qui peuvent réussir aux solutions des jours précédents sans violer les contraintes.

vous aurez probablement à garder une histoire de ce que les solutions conduisent à ce que d'autres solutions (probablement dans un graphique dirigé.) Contrainte l'enregistrement vous permet de se rappeler possible Ajouter-Supprimer des quantités et rejette des solutions basées sur cela.

Il y a beaucoup d'autres mesures qui pourraient être prises pour améliorer davantage votre solution. Voici quelques idées:

• Enregistrement de contraintes pour le point-combinaisons de valeurs trouvées dans les jours précédents solutions. Rejeter d'autres solutions immédiatement (comme les valeurs de l'article ne doit pas changer.) Vous pourriez même trouver une solution plus petite ensembles pour chaque solution existante utilisant des contraintes spécifiques à la solution pour rejeter plus tôt les solutions invalides.
• générez des solutions "mutantes", historique complet, chaque jour afin de "réparer" le cas où le d ₁ ensemble de solution ne contient pas la solution de l'utilisateur. Vous pouvez utiliser un algorithme génétique pour trouver une population mutante basée sur une solution existante.)
• utiliser l'heuristique pour trouver facilement des solutions (par exemple quand un solution est trouvée, essayer de trouver des variations de cette solution en remplaçant les quantités autour.)
• utiliser des heuristiques comportementales afin de prédire certaines actions de l'utilisateur (par exemple, la même quantité pour chaque élément, les modèles extrêmes, etc.)
• continuez à faire quelques calculs pendant que l'utilisateur entre de nouvelles quantités.

compte tenu de tout cela, essayer de comprendre un système de classement basé sur l'occurrence de solutions et heuristiques à déterminer une solution possible.

j'ai écrit un programme pour jouer au jeu. Bien sûr, j'ai dû automatiser le côté humain, mais je crois que j'ai fait tout cela de telle manière que je ne devrais pas invalider mon approche lorsque joué contre un vrai humain.

j'ai abordé cela d'une perspective d'apprentissage machine et traité le problème comme un modèle de markov caché où le prix total était l'observation. Ma solution est d'utiliser un filtre à particules. Cette solution est écrite en Python 2.7 en utilisant NumPy et SciPy.

j'ai énoncé toute hypothèse que j'ai faite soit explicitement dans les commentaires ou implicitement dans le code. J'ai aussi établi des contraintes supplémentaires pour obtenir du code à exécuter de façon automatisée. Il n'est pas particulièrement optimisé car j'ai essayé d'errer sur la compréhensibilité côté plutôt que la vitesse.

chaque itération produit les quantités réelles courantes et les conjectures. Je ne fais que transférer la sortie dans un fichier pour pouvoir l'examiner facilement. Une intéressante extension serait de tracer la sortie sur un graphique soit 2D (pour 2 fruits) ou 3D (pour 3 fruits). Ensuite, vous pourrez voir le filtre à particules dans la solution.

mise à jour:

a modifié le code pour y inclure des paramètres mis à jour après modification. Inclus les appels de pointage à l'aide de matplotlib (via pylab). Traquer fonctionne sur Linux-Gnome, votre kilométrage peut varier. NUM_FRUITS par défaut à 2 pour le support de pointage. Il suffit de commenter tous les appels de pylab à supprimer le pointage et être en mesure de changer NUM_FRUITS à n'importe quoi.

fait un bon travail en estimant le fxn actuel représenté par les quantités inconnues X Prix = Prix Total. En 2D (2 Fruits) c'est une ligne, en 3D (3 Fruits) ce serait un plan. Semble être trop peu de données pour le filtre à particules de manière fiable focaliser sur les quantités correctes. Besoin d'un peu plus de smarts sur le dessus du filtre à particules pour vraiment rassembler les informations historiques. Vous pouvez essayer de convertir le filtre à particules de 2e ou 3e ordre.

Maj 2:

j'ai beaucoup joué avec mon code. J'ai essayé un tas de choses et maintenant présenter le programme final que je vais faire (en commençant à brûler sur cette idée).

changements:

les particules utilisent maintenant des points flottants plutôt que des entiers. Vous ne savez pas si cela a eu un effet significatif, mais c'est une solution générale. L'arrondissement aux entiers est fait seulement quand on fait une supposition.

Le graphique

montre les quantités réelles comme carré vert et le courant deviner comme carré rouge. Actuellement estimé particules montré que les points bleus (de la taille de combien nous les croire). Cela le rend vraiment facile de voir comment l'algorithme fonctionne. (Traçage également testé et travaillant sur Win 7 64-bit).

ajout de paramètres pour désactiver/modifier la quantité et changer le prix. Bien sûr, les deux " off " n'est pas intéressant.

il fait un bon travail assez dang, mais, comme il a été noté, c'est un problème vraiment difficile, donc obtenir la réponse exacte est difficile. Désactiver CHANGE_QUANTITIES produit le cas le plus simple. Vous pouvez obtenir une appréciation de la difficulté du problème en exécutant avec 2 fruits avec CHANGE_QUANTITIES off. Voir la rapidité avec laquelle il s'adapte à la bonne réponse, puis voir comment il est plus difficile que vous augmentez le nombre de fruits.

vous pouvez également obtenir une perspective sur le difficulté à maintenir CHANGE_QUANTITIES sur, mais en ajustant le MAX_QUANTITY_CHANGE à partir de très petites valeurs (.001) à des valeurs "grandes" (.05).

une situation où il lutte est si sur la dimension (une quantité de fruit) se rapproche de zéro. Parce qu'il utilise une moyenne de particules pour deviner qu'il s'éloignera toujours d'une frontière dure comme zéro.

en général, cela fait un grand tutoriel sur le filtre à particules.

---

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()

pour vos règles initiales:

de mes années scolaires, je dirais que si nous faisons une abstraction des 5% de changements, nous avons tous les jours une équation avec trois valeurs inconnues (désolé Je ne sais pas le vocabulaire mathématiques en anglais), qui sont les mêmes valeurs que la veille. Au jour 3, vous avez trois équations, trois valeurs inconnues, et la solution devrait être directe.

je suppose que le changement de 5% chaque jour peut être oublié si les valeurs des trois éléments sont suffisamment différentes, parce que, comme vous l'avez dit, Nous allons utiliser des approximations et arrondir les nombres.

pour vos règles adaptées:

trop de valeurs inconnues - et changeantes dans ce cas, il n'y a donc pas de solution directe que je connaisse. Je ferais confiance à Lior sur ce point; son approche semble très bien! (Si vous avez une gamme limitée de prix et de quantités.)