Как подойти к алгоритму угадывания номера (с помощью скручивания)?

Ответ 1

Объединим теорию графов и вероятность:

В первый день создайте набор всех возможных решений. Обозначим решения, заданные как A1 = {a1 (1), a1 (2),..., a1 (n)}.

Во второй день вы можете снова создать набор решений A2.

Теперь, для каждого элемента в A2, вам нужно будет проверить, может ли он быть достигнут из каждого элемента A1 (с учетом допуска x%). Если это так - соедините A2 (n) с A1 (m). Если его невозможно достичь из любого node в A1 (m) - вы можете удалить этот node.

В основном мы строим связанный направленный ациклический граф.

Все пути в графе одинаково вероятны. Точное решение можно найти только тогда, когда имеется один край от Am до Am + 1 (от node в Am до a node в Am + 1).

Конечно, некоторые узлы появляются в большем количестве путей, чем другие узлы. Вероятность для каждого node может быть непосредственно выведена на основе количества путей, содержащих этот node.

Назначая вес каждому node, который равен числу путей, которые приводят к этому node, нет необходимости хранить всю историю, но только в предыдущий день.

Кроме того, взгляните на линейные уравнения дифантинов с отрицательным значением - вопрос, который я задал некоторое время назад. Принятый ответ - отличный способ перечислить все комбо на каждом шагу.

Ответ 2

Эту проблему решить невозможно. Позволяет сказать, что вы точно знаете, какое количество элементов было увеличено, а не только то, что для этого максимальное соотношение.

Пользователь имеет N плодов, и у вас есть D дней угадывания.

В каждый день вы получаете N новых переменных, а затем вы имеете в сумме переменные D * N.

В течение каждого дня вы можете генерировать только 2 уравнения. Одно уравнение - это сумма цены n_item *, а другая - на основе отношения. В целом у вас есть не более 2 * D уравнений, если они все независимы.

2 * D < N * D для всех N > 2

Ответ 3

Отказ от ответственности: я сильно изменил свой ответ после временного удаления моего ответа и тщательного повторного чтения вопроса, поскольку я неправильно понял некоторые важные вопросы. В то время как все еще ссылаясь на похожие темы и алгоритмы, ответ был значительно улучшен после того, как я попытался решить часть проблемы на С# сам.

Голливудская версия

• Проблема заключается в проблема удовлетворения динамического ограничения (DCSP), вариант Проблемы ограничения ограничений (CSP.)
• Используйте "Монте-Карло" , чтобы найти потенциальные решения для данного дня, если значения и диапазоны значений не являются крошечными. В противном случае используйте грубую силу, чтобы найти все возможные решения.
• Используйте привязку Constraint Recording (относящуюся к DCSP), применяемую в каскаде до предыдущих дней, чтобы ограничить возможный набор решений.
• Перекрестите пальцы, прицелитесь и стреляйте (Guess), исходя из вероятности.
• (Необязательно) побеждает Брюс Уиллис.

Оригинальная версия

Во-первых, я хотел бы указать, что я вижу здесь две основные проблемы:

• Огромное количество возможных решений. Зная только количество предметов и общее значение, скажем, 3 и 143, например, даст много возможных решений. Кроме того, нелегко добиться того, чтобы алгоритм собирал правильное решение без неизбежного использования недействительных решений (общее число не равное 143.)

• Когда возможные решения найдены для данного дня D _i, нужно найти способ устранения потенциальных решений с добавленной информацией, заданной {D _{я + 1}.. D _{я + n}}.

Положим некоторые основы для следующих примеров:

• Позволяет сохранять одинаковые значения элементов, всю игру. Он может быть случайным или выбран пользователем.
• Возможные значения элементов привязаны к очень ограниченному диапазону [1-10], где ни одно из двух элементов не может иметь одинаковое значение.
• Ни один элемент не может иметь величину больше 100. Это означает: [0-100].

Чтобы решить эту задачу легче , я взял на себя смелость изменить одно ограничение, что ускоряет алгоритм:

• Правило "общее количество" переопределяется этим правилом: вы можете добавлять или удалять любое количество элементов в пределах диапазона [1-10], всего за один день. Однако вы не можете добавлять или удалять одинаковое количество элементов, всего более двух раз. Это также дает игре максимальный жизненный цикл продолжительностью 20 дней.

Это правило позволяет нам более легко исключать решения. И с небольшими диапазонами рендер делает алгоритмы обратной трассировки бесполезными, как и ваши исходные проблемы и правила.

По моему скромному мнению, это правило не суть игры, а только фасилитатор, позволяющий компьютеру решить проблему.

Задача 1: Поиск потенциальных решений

Для начала проблема 1. может быть решена с помощью алгоритма Монте-Карло, чтобы найти набор потенциальных решений. Метод прост: генерируйте случайные числа для значений и величин позиций (в пределах их соответствующего диапазона). Повторите процесс для необходимого количества элементов. Проверьте, приемлемо ли решение. Это означает, что если элементы имеют разные значения, а общая сумма равна нашей общей цели (скажем, 143.)

Хотя этот метод имеет то преимущество, что его легко реализовать, он имеет некоторые недостатки:

• Пользовательское решение не гарантируется в наших результатах.
• Существует много "промахов". Например, требуется принять более или менее 3 000 000 попыток найти 1000 потенциальных решений с учетом наших ограничений.
• Это займет много времени: от 4 до 5 секунд на ленивом ноутбуке.

Как обойти эти недостатки? Ну...

• Ограничьте диапазон до меньших значений и
• Найдите достаточное количество потенциальных решений, поэтому есть хороший шанс, что пользовательское решение появится в вашем наборе решений.
• Используйте эвристику, чтобы легче находить решения (подробнее об этом позже).

Обратите внимание, что чем больше вы ограничиваете диапазоны, тем менее полезно использовать алгоритм Монте-Карло, так как будет достаточно достаточно правильных решений для повторения на них всех в разумные сроки. Для ограничений {3, [1-10], [0-100]} существует около 741 000 000 действительных решений (не ограниченных целевым общим значением.) Монте-Карло можно использовать там. Для {3, [1-5], [0-10]} всего около 80 000. Не нужно использовать Монте-Карло; грубая сила for будет делать все отлично.

Я считаю, что проблема 1 заключается в том, что вы бы назвали проблемой ограничения ограничений (или CSP.)

Задача 2: Ограничить набор потенциальных решений

Учитывая тот факт, что проблема 1 является CSP, я бы пошел и вызовет проблему 2, а проблема вообще, Dynamic CSP (или DCSP.)

[DCSP] полезны, когда исходная формулировка проблема каким-то образом изменяется, как правило, потому что набор ограничения, которые необходимо учитывать, развиваются из-за окружающей среды. DCSPs рассматриваются как последовательность статических CSP, каждая из которых представляет собой преобразование предыдущий, в котором могут быть добавлены переменные и ограничения (ограничение) или удаление (релаксация).

Один метод, используемый с CSP, который может быть полезен для этой проблемы, называется Constraint Recording:

• При каждом изменении среды (пользователь вводит значения для D _{я + 1}), найдите информацию о новом ограничении: какие возможные значения используются для ограничения добавления-удаления.
• Применять ограничение на каждый предыдущий день в каскаде. Эффекты сотрясения могут значительно уменьшить возможные решения.

Для этого вам нужно каждый день получать новый набор возможных решений; Используйте либо грубую силу, либо Монте-Карло. Затем сравните решения D _i с D _i-1 и сохраните только решения, которые могут преуспеть в решениях предыдущих дней, не нарушая ограничений.

Вероятно, вам придется вести историю того, какие решения приводят к каким-либо другим решениям (возможно, в ориентированном графике). Запись ограничений позволяет вам помнить возможные значения добавления-удаления и отклонять решения на основе этого.

Есть много других шагов, которые можно предпринять для дальнейшего улучшения вашего решения. Вот несколько идей:

• Ограничения записи для комбинаций элементов и значений, найденных в предыдущих версиях решений. Немедленно отклонить другие решения (поскольку значения элементов не должны меняться.) Вы даже можете найти меньшие наборы решений для каждого существующего решения, используя ограничения, специфичные для решения, для отклонения ранее недействительных решений.
• Сгенерировать некоторые "мутантные", полномасштабные решения каждый день, чтобы "восстановить" случай, когда набор решений D ₁ не содержит пользовательского решения. Вы можете использовать генетический алгоритм для поиска популяции мутантов на основе существующего набора решений.)
• Используйте эвристику, чтобы легко находить решения (например, когда найдено действительное решение, попробуйте найти варианты этого решения, заменив величины вокруг.)
• Используйте поведенческие эвристики, чтобы предсказать некоторые действия пользователя (например, такое же количество для каждого элемента, экстремальные шаблоны и т.д.).
• Продолжайте делать некоторые вычисления, пока пользователь вводит новые количества.

Учитывая все это, попытайтесь выяснить систему ранжирования, основанную на появлении решений и эвристик, чтобы определить решение кандидата.

Ответ 4

Я написал программу для игры. Конечно, мне пришлось автоматизировать человеческую сторону, но я считаю, что я сделал все это таким образом, чтобы я не нарушал свой подход, когда играл против настоящего человека.

Я подошел к этому с точки зрения машинного обучения и рассмотрел проблему как скрытую марковскую модель, где общая цена была наблюдением. Мое решение - использовать фильтр частиц. Это решение написано на Python 2.7 с помощью NumPy и SciPy.

Я изложил любые предположения, сделанные явным образом в комментариях или неявно в коде. Я также установил некоторые дополнительные ограничения для того, чтобы запустить код в автоматическом режиме. Это не особенно оптимизировалось, поскольку я пытался ошибаться на стороне понимания, а не скорости.

Каждая итерация выводит текущие истинные величины и гадание. Я просто передаю вывод в файл, чтобы я мог легко его просмотреть. Интересным продолжением будет построение вывода на графике либо 2D (для 2 фруктов), либо 3D (для 3-х фруктов). Затем вы сможете увидеть, как фильтр частиц оттачивается в решении.

Update:

Отредактировал код для включения обновленных параметров после настройки. Включены вызовы с использованием matplotlib (через pylab). Планирование работает на Linux-Gnome, ваш пробег может отличаться. По умолчанию NUM_FRUITS - 2 для построения поддержки. Просто закомментируйте все вызовы pylab, чтобы удалить график и сможете изменить NUM_FRUITS на что-либо.

Хорошо ли оценивает текущую fxn, представленную UnknownQuantities X Prices = TotalPrice. В 2D (2 Fruits) это линия, в 3D (3 Fruits) это был бы самолет. Кажется, слишком мало данных для фильтра частиц, чтобы надежно оттачивать правильные количества. Нужно немного больше смайликов поверх фильтра частиц, чтобы действительно собрать историческую информацию. Вы можете попробовать преобразовать фильтр частиц в 2-й или 3-й порядок.

Обновление 2:

Я много играл с моим кодом. Я попробовал кучу вещей и теперь представляю последнюю программу, которую я буду делать (начиная с этой идеи).

Изменения:

Теперь частицы используют плавающие точки, а не целые. Не уверен, что это имело какой-либо значимый эффект, но это более общее решение. Округление до целых чисел выполняется только при угадывании.

На графике показаны истинные величины как зеленый квадрат, а текущая догадка - как красный квадрат. В настоящее время считается, что частицы показаны как синие точки (размер которых зависит от того, насколько мы им верим). Это позволяет легко понять, насколько хорошо работает алгоритм. (Plotting также тестировался и работал на 64-разрядной версии Win 7).

Добавлены параметры отключения/изменения количества и изменения цены. Конечно, обе "офф" не интересны.

Это хорошо работает, но, как уже отмечалось, это очень сложная проблема, поэтому получить точный ответ сложно. Отключение CHANGE_QUANTITIES создает простейший случай. Вы можете получить оценку сложности проблемы, выполнив работу с 2 фруктами с выключенным CHANGE_QUANTITIES. Посмотрите, как быстро он набирает правильный ответ, а затем посмотрите, насколько сложнее, чем увеличивать количество фруктов.

Вы также можете взглянуть на трудность, сохранив CHANGE_QUANTITIES, но настроив MAX_QUANTITY_CHANGE с очень малых значений (.001) на "большие" значения (.05).

Одна из ситуаций, когда он борется, - это если размерность (одно количество фруктов) приближается к нулю. Поскольку он использует среднее количество частиц, чтобы угадать, он всегда будет перескакивать с жесткой границы, равной нулю.

В общем, это делает учебник с большим количеством частиц.

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

Ответ 5

Для ваших начальных правил: Из моих школьных лет я бы сказал, что если мы сделаем абстракцию изменений в 5%, у нас есть ежедневное уравнение с тремя неизвестными значениями (извините, что я не знаю словарь математики по-английски), которые имеют те же значения, что и предыдущий день, На 3-й день у вас есть 3 уравнения, 3 неизвестных значения, решение должно быть прямым.

Я думаю, что 5% -ное изменение каждый день может быть забыто, если значения трех элементов достаточно различны, потому что, как вы сказали, мы будем использовать аппроксимации и округлять числа.

Для ваших адаптированных правил: Слишком много неизвестных и изменяющихся значений в этом случае, поэтому нет прямого решения, о котором я знаю. Я бы поверила Лиору в этом, его подход выглядит прекрасно! (если у вас ограниченный диапазон цен и количества)