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




machine learning library weka (4)

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

Вот как игра будет работать:

Пользователям будут предоставлены предметы со значением. Например,

Apple = 1
Pears = 2
Oranges  = 3

Затем они получат возможность выбрать любую комбинацию из них (например, 100 яблок, 20 груш и один апельсин). Единственный результат, который получает компьютер, - это общее значение (в этом примере это сейчас $ 143). Компьютер попытается угадать, что у них есть. Который, очевидно, не сможет правильно разобраться в первом повороте.

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

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

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

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

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

То, что я сделал до сих пор

Вот мое решение до сих пор (не так много). В принципе, я беру все значения и выясняю все возможные комбинации из них (я делаю эту часть). Затем я беру все возможные комбо и помещаю их в базу данных в виде словаря (например, для $ 143, может быть запись в словаре {apple: 143, Pears: 0, Orange: 0}) до самого {apple : 0, Pears: 1, Апельсины: 47} Я делаю это каждый раз, когда получаю новый номер, поэтому у меня есть список всех возможностей.

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

Вопросов:

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

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

ОБНОВЛЕНИЕ: получение отзывов, которые трудно решить. Поэтому я думал, что добавлю еще одно условие в игру, которое не будет мешать тому, что делает игрок (игра остается для них одинаковой), но каждый день ценность фруктов меняет цену (случайным образом). Помогло бы это решить? Потому что в пределах 5% движения и некоторых изменений стоимости фруктов, только несколько комбинаций вероятны с течением времени.

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

UPDATE2: После прочтения и опроса, я считаю, что это скрытая проблема Маркова / Витерби, которая отслеживает изменения цен на фрукты, а также общую сумму (взвешивая последние данные, самые тяжелые). Я не уверен, как применять отношения. Я думаю, что это так и может быть неправильным, но, по крайней мере, я начинаю подозревать, что это проблема машинного обучения.

Обновление 3: Я создал тестовый пример (с меньшими числами) и генератор, чтобы помочь автоматизировать созданные пользователем данные, и я пытаюсь создать граф из него, чтобы узнать, что более вероятно.

Вот код, а также общие значения и комментарии о том, что на самом деле представляют собой количество фруктов.

#!/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

https://code.i-harness.com


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

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

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

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

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

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

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

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

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


Эту проблему решить невозможно.

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 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 , а проблема вообще - динамический CSP (или DCSP).

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

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

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

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

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

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

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

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


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







data-mining