восстановление порядка от образцов

Question

У меня есть пул из шариков из 30 разных цветовых узоров (сплошной зеленый, зеленый и красный полосатый и т. Д.), И у меня также есть 6 ящиков, заказанных от 1 до 6. Теперь случайным образом я выбираю 6 шаров из пул и поместите каждый шар в одну коробку, чтобы каждый ящик содержал ровно один шар. И среди 6 мячей цветовой узор каждого шара может отличаться от того же цвета, что и цветовой паттерн других шариков в других коробках. Теперь я хочу, чтобы вы угадали цветовой паттерн мяча в каждой коробке, выполнив следующие действия:

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

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

Answer 1

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

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

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

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

Или вы могли бы немного больше узнать о статистике и узнать, что это недостающая проблема с данными, где скрытые данные - это знание того, из какого поля был выбран каждый из выбранных мячей. Статистики часто решают проблемы с скрытыми данными с помощью ЭМ-алгоритма. Существует введение для математиков в http://www.inf.ed.ac.uk/teaching/courses/pmr/docs/EM.pdf. Ваша проблема может рассматриваться как простой случай скрытой модели Маркова, при этом скрытое состояние является полем, в котором создается конкретный шар.