Представление этого с точки зрения вопросов по-прежнему играбельно.Я буду нумеровать вопросы от 0 до 4 вместо 1 до 5, так как это более удобно при программировании.
01234
-----
player A x x - player A has just 2 playable questions
player B xx x - player B has 3 playable questions
player C x x x - player C has 3 playable questions
Сначала я опишу то, что может показаться очень наивным алгоритмом, но вВ конце я покажу, как его можно значительно улучшить.
Для каждого из 5 вопросов вам нужно решить, оставить его или отказаться от него.Для этого потребуются рекурсивные функции с глубиной 5.
vector<bool> keep_or_discard(5); // an array to store the five decisions
void decide_one_question(int question_id) {
// first, pretend we keep the question
keep_or_discard[question_id] = true;
decide_one_question(question_id + 1); // recursively consider the next question
// then, pretend we discard this question
keep_or_discard[question_id] = false;
decide_one_question(question_id + 1); // recursively consider the next question
}
decide_one_question(0); // this call starts the whole recursive search
. Эта первая попытка приведет к бесконечному рекурсивному спуску и пройдет за конец массива.Очевидное первое, что нам нужно сделать, это немедленно вернуться, когда question_id == 5 (то есть, когда все вопросы с 0 по 4 были решены. Мы добавляем этот код в начало решить____для:
void decide_one_question(int question_id) {
{
if(question_id == 5) {
// no more decisions needed.
return;
}
}
// ....
Далее,мы знаем, сколько вопросов нам разрешено хранить. Назовите это allowed_to_keep. В данном случае это 5-3, что означает, что мы должны оставить ровно два вопроса. Вы можете установить это как глобальную переменную где-нибудь.
int allowed_to_keep; // set this to 2
Теперь мы должны добавить дополнительные проверки в начало define_one_question и добавить еще один параметр:
void decide_one_question(int question_id, int questions_kept_so_far) {
{
if(question_id == 5) {
// no more decisions needed.
return;
}
if(questions_kept_so_far > allowed_to_keep) {
// not allowed to keep this many, just return immediately
return;
}
int questions_left_to_consider = 5 - question_id; // how many not yet considered
if(questions_kept_so_far + questions_left_to_consider < allowed_to_keep) {
// even if we keep all the rest, we'll fall short
// may as well return. (This is an optional extra)
return;
}
}
keep_or_discard[question_id] = true;
decide_one_question(question_id + 1, questions_kept_so_far + 1);
keep_or_discard[question_id] = false;
decide_one_question(question_id + 1, questions_kept_so_far );
}
decide_one_question(0,0);
(Обратите внимание на общую закономерность: мы разрешаем вызову рекурсивной функции переходить на один уровень тоже)Я считаю, что легче проверять «недопустимые» состояния в начале функции, чем пытаться вообще избежать недопустимых вызовов функций.)
Пока что это выглядит довольно наивно.Это проверка каждой комбинации. Терпите меня!
Мы должны начать отслеживать счет, чтобы запомнить лучшее (и впарация для дальнейшей оптимизации).Первым делом нужно написать функцию calculate_score.И иметь глобальный под названием best_score_so_far.Наша цель - максимизировать его, поэтому в начале алгоритма это должно быть инициализировано до -1.
int best_score_so_far; // initialize to -1 at the start
void decide_one_question(int question_id, int questions_kept_so_far) {
{
if(question_id == 5) {
int score = calculate_score();
if(score > best_score_so_far) {
// Great!
best_score_so_far = score;
store_this_good_set_of_answers();
}
return;
}
// ...
Далее, было бы лучше отслеживать, как меняется счет, когда мы повторяемчерез уровни.Давайте начнем с оптимизма;давайте представим, что мы можем сохранить каждый вопрос, рассчитать оценку и назвать ее upper_bound_on_the_score.Копия этого будет передаваться в функцию каждый раз, когда она вызывает себя рекурсивно, и будет обновляться локально каждый раз, когда будет принято решение отказаться от вопроса .
void decide_one_question(int question_id
, int questions_kept_so_far
, int upper_bound_on_the_score) {
... the checks we've already detailed above
keep_or_discard[question_id] = true;
decide_one_question(question_id + 1
, questions_kept_so_far + 1
, upper_bound_on_the_score
);
keep_or_discard[question_id] = false;
decide_one_question(question_id + 1
, questions_kept_so_far
, calculate_the_new_upper_bound()
);
См.ближе к концу этого последнего фрагмента кода была вычислена новая (меньшая) верхняя граница на основе решения об отклонении вопроса 'question_id'.
На каждом уровне в рекурсии эта верхняя граница получаламеньше.Каждый рекурсивный вызов либо сохраняет вопрос (не внося изменений в эту оптимистическую границу), либо решает отбросить один вопрос (приводя к меньшей границе в этой части рекурсивного поиска).
Оптимизация
Теперь, когда мы знаем верхнюю границу, мы можем выполнить следующую проверку в самом начале функции, независимо от того, сколько вопросов было решено на данный момент :
void decide_one_question(int question_id
, int questions_kept_so_far
, upper_bound_on_the_score) {
if(upper_bound_on_the_score < best_score_so_far) {
// the upper bound is already too low,
// therefore, this is a dead end.
return;
}
if(question_id == 5) // .. continue with the rest of the function.
Эта проверка гарантирует, что как только будет найдено «разумное» решение, алгоритм быстро откажется от всех «тупиковых» поисков.Затем (надеюсь) он быстро найдет лучшие и лучшие решения, а затем может быть еще более агрессивным в деле обрезки мертвых веток.Я обнаружил, что этот подход довольно хорошо работает на практике.
Если он не работает, есть много возможностей для дальнейшей оптимизации.Я не буду пытаться перечислить их все, и вы, безусловно, можете попробовать совершенно другие подходы.Но я обнаружил, что это работает в тех редких случаях, когда мне приходится искать что-то вроде этого.