Вычисление вероятности и алгоритм для подпоследовательностей - PullRequest
Новая
       21

Вычисление вероятности и алгоритм для подпоследовательностей

9 голосов
/ 22 сентября 2011

Это игра, в которой карты 1-50 раздаются двум игрокам, каждый из которых имеет 10 карт в случайном порядке. Цель состоит в том, чтобы отсортировать все карты, и тот, кто сделает это первым, становится победителем. Каждый раз, когда человек может забрать карту из колоды, он должен заменить существующую карту. Игрок не может обменять свои карты. Т.е. только он может заменить свою карту картой из колоды. Сброшенная карта вернется в колоду в случайном порядке. Теперь мне нужно написать программу, которая делает это эффективно.

Я подумал о следующем решении 1) найти все подпоследовательности, которые находятся в порядке возрастания в данном наборе карт 2) для каждой подпоследовательности вычисляют вес, основанный на вероятности отсутствия путей, которые могут решить проблему. Например: если у меня есть подпоследовательность 48,49,50 с индексом 2,3,4, вероятность завершения задачи с этой подпоследовательностью равна 0. Таким образом, вес умножается на 0. Точно так же, если у меня есть последовательность 18, 20, 30 с индексом 3, 4, 5, то ни один из возможных способов завершения игры - это 20 возможных карт для выбора на 6-10 и 17 возможных карт для выбора на первые 2 позиции, 3) для каждой карты из колоды я отсканирую список и пересчитаю вес последующих, чтобы найти лучшее соответствие.

Ну, у этого решения может быть много недостатков, но я хотел знать, 1) Учитывая подпоследовательность, как найти вероятность возможных путей завершения игры? 2) Каков наилучший алгоритм для поиска всех подпоследовательностей?

1 Ответ

2 голосов
/ 20 октября 2011

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

N=50
I=10
while hand is not ordered:
   get a card from the deck
   v = value of the card
   put card in position round(v/N*I)
...