Переполнение стека рекурсии мемоизации
Я реализовывал рекурсивную функцию с запоминанием для ускорения. Суть программы заключается в следующем:
Я тасую колоду карт (с равным количеством красного и черного
карты) и начать раздавать их лицом вверх.
После любой карты вы можете сказать «стоп», после чего я заплачу вам 1 доллар за
каждая красная карточка сдается, и вы платите мне 1 доллар за каждую сданную черную карту.
Какова ваша оптимальная стратегия, и сколько вы заплатите, чтобы играть
эта игра?
Моя рекурсивная функция выглядит следующим образом:
double Game::Value_of_game(double number_of_red_cards, double number_of_black_cards)
{
double value, key;if(number_of_red_cards == 0)
{
Card_values.insert(Card_values.begin(), pair<double, double> (Key_hash_table(number_of_red_cards, number_of_black_cards), number_of_black_cards));
return number_of_black_cards;
}
else if(number_of_black_cards == 0)
{
Card_values.insert(Card_values.begin(), pair<double, double> (Key_hash_table(number_of_red_cards, number_of_black_cards), 0));
return 0;
}
card_iter = Card_values.find(Key_hash_table(number_of_red_cards, number_of_black_cards));
if(card_iter != Card_values.end())
{
cout << endl << "Debug: [" << number_of_red_cards << ", " << number_of_black_cards << "] and value = " << card_iter->second << endl;
return card_iter->second;
}
else
{
number_of_total_cards = number_of_red_cards + number_of_black_cards;
prob_red_card = number_of_red_cards/number_of_total_cards;
prob_black_card = number_of_black_cards/number_of_total_cards;
value = max(((prob_red_card*Value_of_game(number_of_red_cards - 1, number_of_black_cards)) +
(prob_black_card*Value_of_game(number_of_red_cards, number_of_black_cards - 1))),
(number_of_black_cards - number_of_red_cards));
cout << "Check: value = " << value << endl;
Card_values.insert(Card_values.begin(), pair<double, double> (Key_hash_table(number_of_red_cards, number_of_black_cards), value));
card_iter = Card_values.find(Key_hash_table(number_of_red_cards , number_of_black_cards ));
if(card_iter != Card_values.end());
return card_iter->second;
}
}
double Game::Key_hash_table(double number_of_red_cards, double number_of_black_cards)
{
double key = number_of_red_cards + (number_of_black_cards*91);
return key;
}
Третий оператор if является частью кода «памятки», в нем хранятся все необходимые значения. Значения, которые хранятся на карте, можно рассматривать как матрицу, эти значения будут соответствовать определенным #red карточкам и # черным карточкам. Что действительно странно, так это то, что когда я выполняю код для 8 карт (4 черных и 4 красных), я получаю неправильный ответ. Но когда я выполняю код для 10 карт, мой ответ неверен, но теперь мой ответ для 4 черных и 4 красных правил верен (8 карт)! То же самое можно сказать и для 12 карт, где я получаю неправильный ответ для 12 карт, но правильный ответ для 10 карт, и так далее, и так далее. В коде есть какая-то ошибка, однако я не могу ее понять.
Решение
На самом деле никто не ответил на этот вопрос ответом. Так что я попробую, хотя nneonneo на самом деле положить его или ее пальцем на вероятный источник вашей проблемы.
Первая проблема, которая, вероятно, на самом деле не является проблемой в этом случае, но торчит как больной палец … вы используете double держать значение, которое вы в основном рассматриваете как целое число. В этом случае на большинстве систем это, вероятно, нормально. Но, как правило, это очень плохо. В частности, потому что вы проверяете, если double в точности равно 0. Вероятно, в большинстве систем с большинством компиляторов double может содержать целочисленные значения вплоть до довольно большого размера с идеальной точностью, если вы ограничиваете себя сложением, вычитанием и умножением на другие целые числа. или удваивает маскировку под целые числа, чтобы получить новое значение.
Но, скорее всего, это не источник ошибки, которую вы видите, это просто срабатывает сигнал тревоги каждого хорошего программиста за вонючий код. Это должно быть исправлено. Единственный раз, когда вам действительно нужно, чтобы они были двойными, это когда вы вычисляете относительную вероятность красного или черного.
И это подводит меня к тому, что, вероятно, является вашей проблемой. У вас есть эти два утверждения в вашем коде:
number_of_total_cards = number_of_red_cards + number_of_black_cards;
prob_red_card = number_of_red_cards/number_of_total_cards;
prob_black_card = number_of_black_cards/number_of_total_cards;
что, конечно, следует читать:
number_of_total_cards = number_of_red_cards + number_of_black_cards;
prob_red_card = number_of_red_cards/double(number_of_total_cards);
prob_black_card = number_of_black_cards/double(number_of_total_cards);
потому что вы были хорошим программистом и объявили эти переменные как целые числа.
предположительно prob_red_card а также prob_black_card переменные типа double, Но они нигде не объявлены в коде, который вы нам показываете. Это означает, что независимо от того, где они объявлены или каковы их типы, они должны эффективно использоваться всеми под-вызовами в дереве рекурсивных вызовов для Game::Value_of_game,
Это почти наверняка не то, что вы хотите. Это делает чрезвычайно трудным рассуждать о том, какие значения имеют эти переменные и что эти значения представляют во время любого данного вызова в дереве рекурсивного вызова для вашей функции. Они действительно должны быть локальными переменными, чтобы алгоритм можно было анализировать. К счастью, они, кажется, используются только в else пункт о конкретном if заявление. Таким образом, они могут быть объявлены, когда им изначально присвоены значения. Вот, вероятно, то, что этот код должен прочитать:
unsigned const int number_of_total_cards = number_of_red_cards + number_of_black_cards;
const double prob_red_card = number_of_red_cards/double(number_of_total_cards);
const double prob_black_card = number_of_black_cards/double(number_of_total_cards);
Обратите внимание, что я также объявляю их const, Хорошей практикой является объявление любой переменной, значение которой вы не ожидаете изменить в течение жизни переменной, как const, Это поможет вам написать более правильный код, попросив компилятор сообщить вам, когда вы случайно пишете неправильный код. Это также может помочь компилятору генерировать лучший код, хотя в этом случае даже тривиальный анализ кода показывает, что они не модифицируются в течение срока их службы и могут рассматриваться как const, поэтому большинство достойных оптимизаторов по существу помещают const для вас в целях оптимизации кода, хотя это все равно не даст вам преимущества того, что компилятор сообщит вам, если вы случайно используете их неконстантным способом.
Другие решения
Других решений пока нет …