рекурсия C++ с массивами

Question

У меня есть этот проект, над которым я работаю для класса, и я не ищу ответа, но, возможно, всего несколько советов, так как я не чувствую, что использую истинную рекурсию , Проблема заключается в решении игры Hi Q или «peg solitaire», в которой вы хотите, чтобы конечный результат оставался на одном конце (он играл с треугольной доской, и одно место открыто с самого начала.)

Я представлял плата с простым массивом, причем каждый индекс является пятном и имеет значение 1, если он имеет привязку, а 0, если нет, а также набор действительных ходов с 2-мерным массивом, который равен 36, 3 (каждый набор перемещений содержит 3 числа, привязку, которую вы перемещаете, привязка переполнения и индекс назначения.)

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

Это то, что у меня есть до сих пор; массив «a» представляет плату, массив «b» представляет перемещение, а массив «c» - это моя идея напоминания о том, какие шаги я использовал уже. Используемые функции - вспомогательные функции, которые в основном просто проходят через массивы, чтобы найти пустое пространство и соответствующий ход. :

void solveGame(int a[15], int b[36][3], int c[15][3]){ 

    int empSpace; 
    int moveIndex; 
    int count = 0; 

    if(pegCount(a) < 2){ 

     return; 

    } 
    else{ 

     empSpace = findEmpty(a); 
     moveIndex = chooseMove(a, b, empSpace); 

     a[b[moveIndex][0]] = 0; 
     a[b[moveIndex][1]] = 0; 
     a[b[moveIndex][2]] = 1; 

     c[count][0] = b[moveIndex][0]; 
     c[count][1] = b[moveIndex][1]; 
     c[count][2] = b[moveIndex][2]; 

      solveGame(a,b,c); 

    } 

} 

Answer 1

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

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

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

Теперь, когда вы на самом деле запускаете поиск в пространстве, скорее всего, вы действительно не потрудитесь проверить все эти ходы - если вам вообще повезет, вы увидите «правильное» движение до этого. Поэтому вы возвращаете что-то из функции, говоря: «У меня это есть, все выше меня выходят», и все ваши родительские звонящие разбивают свои петли.

Этот шаблон является так называемым поиск по глубине. Я проиллюстрирую, создав гипотетическую более простую игру. Представьте, что вам приходилось выбирать «A», «B» или «C» на каждом ходу, и игра длится три хода. Сначала вы исследуете A, затем AA, затем AAA, тогда, если это нехорошо, вы смотрите AAB, затем AAC, затем AB, затем ABA, затем ABB, затем ABC, затем AC, затем ACA, ACB, ACC, B, БАД и т. Д.

Вот почему это глубина: вы идете до самого низа, а затем возвращаетесь назад как можно меньше. Нелегко рекурсивно реализовать поиск по ширине, в котором будут исследоваться A, затем B, затем C, затем AA, затем AB, затем BA, затем BB и так далее, пока он, наконец, не попадет в «полную игру», состояний с тремя ходами. Для этого требуется использование очереди вместо неявного стека, получаемого из рекурсии.

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

Есть целые главы учебников по поисковым алгоритмам («восхождение по холму», «эвристика», «поиск по звездам» и т. П.). Некоторые из алгоритмов очень интересны.

Что касается вашего первого вопроса, на тему «Использование большого количества итераций» - это не столько итерация, сколько у вас такая умная :-). То есть, если вы не знаете, что у вас проблема с производительностью, вам, вероятно, не нужно оптимизировать, и даже тогда интуиция о том, что требует времени, может быть плохим. Получите что-то, где вы можете сказать «это работает, но ...», прежде чем беспокоиться о том, чтобы получить то, чем вы гордитесь, чтобы надеть свою метафорическую трофейную стену. Вернитесь сюда, если вам нужна помощь по таким темам, как , обрезка или создание лучшей эвристики для поиска по звездам.

Удачи вам в вашей игровой программе!

Answer 2

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

Окончательное «решение» будет одним из возможных путей через древовидную структуру N-арки ... вы ищете его так же, как и поиск значения в двоичном дереве поиска, только вы должны проверить более двух детей, чтобы увидеть, какое поддерево для перемещения вниз. Если вы обнаружите, что ни один из детей не соответствует вашему решению, вы переходите к родительскому узлу и продолжаете тестировать больше детей родителя на текущий узел (т. Е. Это ваш «обратный путь»).

поиске N-арной дерево будет выглядеть примерно так:

template<typename T> 
bool search_nary_tree(const node_t<T>* node, std::stack<const node_t<T>*>& steps) 
{ 
    if (node->current_board == ONE_PEG) 
    { 
     steps.push(node); 
     return true; 
    } 

    for (int i=0; i < node->choices.size(); i++) 
    { 
     if (search_nary_tree(node->choices[i])) 
     { 
      steps.push(node); 
      return true; 
     } 
    } 

    return false; 
} 

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

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

Answer 3

Я не понимаю, как вы могли бы затем вернуться назад с помощью рекурсии

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

Для того, чтобы возвращаться назад с помощью рекурсии, вам потребуется несколько вещей:

1. Держите свое состояние в локальных переменных или параметров (так стек вызовов неявным сохраняет свои промежуточные состояния)
2. RECURSE в середине вашей функции, возможно, в цикле, который пытается выполнить все начальные шаги.
3. Используйте код возврата, чтобы указать, было ли найдено решение. Если бы это было так, то функция просто вернется снова (вызывая длинную последовательность возвратов); иначе вы вернетесь в свое предыдущее состояние, готовое попробовать другой ход.

Что касается шага 2, каждый рекурсивный вызов может «думать», он просто пытается все первые ходы, но плата, переданная в качестве аргумента, уже изменена предыдущими вызовами.

Когда функция возвращается, вызывающий может выбрать «принять» решение (т. Е. Вернуться снова) или попробовать что-то еще, сделав еще одну рекурсию с измененными параметрами. [← Я только что объяснил шаг 3, используя другие слова]