Понимание возврата в C ++

12

У меня есть хорошее базовое понимание основ C ++, я также понимаю, как работает рекурсия. Я сталкивался с определенными проблемами, такими как классическая проблема восьми королев и решение судоку с возвратом.

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

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

И да, я знаю, что это было бы проще в функциональных языках, но я бы хотел понять реализацию и в императивных языках.

Нихилу
источник
Я думаю, что это хороший вопрос, но я думаю, что было бы лучше подчеркнуть просьбу о том, чтобы кто-то объяснил возвращение назад, прося учебники или другие ресурсы. Глубокий пояснительный ответ превосходит список ссылок в любой день.
Адам Лир
Было бы идеально, если бы кто-то мог дать подробное объяснение, но я бы тоже не прочел прочитать ссылки. Просто я не знаю с чего начать.
nikhil

Ответы:

9

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

При возврате вы не начинаете снова. Вместо этого вы перебираете все варианты в текущей ситуации.

Подумайте о поиске решения для лабиринта. В один момент, когда у вас есть два разных пути, вы сначала пробуете левый. Если левый не ведет вас к выходу, вы возвращаетесь к точке и пробуете другой путь. Вот как работает возврат. В 8 Q и других задачах, где можно использовать возвратный путь, запутанная часть находится в проблемной области - как детально детерминировать ваши варианты в данной ситуации.

РЕДАКТИРОВАТЬ : ниже приведен псевдокод, помогающий разобраться в возврате.

# depending on the problem, backtracking is not necessarily calling the
# method itself directly. for now, let's just stick with the simple case.

def backtracking(state)
  option_list = state.get_all_options
  option_list.each {|option|
    state.apply option
    return resolved if state.is_resolved
    return resolved if backtracking(state) == resolved
    state.undo option
  }
  return not_resolved
end

Для вопроса 8Q:

  • state.get_all_options вернет список возможных позиций для следующей ферзя
  • State.is_resolved будет проверять, все ли королевы на доске и хорошо ли они друг с другом.
  • state.apply и state.undo изменят доску, чтобы применить или отменить позиционирование.
Codism
источник
Первым рекурсивным кодом, который я написал (в 1984 году, используя Паскаль) для задания, был алгоритм решения лабиринта.
Джерри
Знайте какое-нибудь простое задание, где я могу написать код, чтобы получить представление об этом.
nikhil
@nikhil: ты спрашиваешь, есть ли какая-то простая проблема? Лучше написать псевдокод, чтобы продемонстрировать общую маршрутизацию возврата. Я попробую один позже в ответе.
Кодизм
Да, именно это будет очень полезно.
nikhil
Большое вам спасибо, я читал кое-что в последнее время. Медленно, но верно мое понимание улучшается.
Нихил
5

Вы видели программу для бинарного дерева, верно? Это выглядит так:

void walk(node* p){
  if (p == NULL) return;  // this is backtracking
  else if (WeWin(p)){
    // print We Win !!
    // do a Throw, or otherwise quit
  }
  else {
    walk(p->left);   // first try moving to the left
    walk(p->right);  // if we didn't win, try moving to the right
                     // if we still didn't win, just return (i.e. backtrack)
  }
}

Вот ваш ответ.

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

Майк Данлавей
источник
1
Вы не можете вернуть bool / int, чтобы проверить, найдено ли решение в поддереве? else{return walk(p->left)||walk(p->right));}не нужно бросать для ожидаемого результата
чокнутый урод
@ratchet: Абсолютно. Это также очень хороший способ сделать это. (Я просто пытался разобрать пример. Я бы сделал это по-своему.)
Майк Данлавей,
@MikeDunlavey резки является важным на практике, хотя.
августа