Zrozumienie cofania w C ++

Dobrze rozumiem podstawy języka C ++, rozumiem także, jak działa rekurencja. Natknąłem się na pewne problemy, takie jak klasyczny problem ośmiu królowych i rozwiązywanie Sudoku z Cofaniem.

Zdaję sobie sprawę, że jestem całkiem zagubiony, jeśli chodzi o to, nie wydaje mi się, żebym był w stanie skupić się na koncepcji powrotu do stosu rekurencji i rozpoczęcia od nowa w celu rozwiązania problemu. Pióro i papier wydają się łatwe, ale jeśli chodzi o pisanie kodu do tego, jestem zdezorientowany, jak zacząć atakować te problemy.

Byłoby pomocne, gdyby istniał samouczek skierowany do początkujących do cofania się lub gdyby istniała dobra książka, w której to omówiono. Gdybym mógł rzucić nieco światła na ten temat lub podać linki do porządnych referencji, byłbym bardzo wdzięczny.

I tak, wiem, że byłoby łatwiej w językach funkcjonalnych, ale chciałbym również zrozumieć implementację w językach imperatywnych.

... Wydaje mi się, że nie jestem w stanie omówić koncepcji powrotu do stosu rekurencji i rozpoczęcia od nowa w celu rozwiązania problemu.

W przypadku cofania nie zaczynasz od nowa. Zamiast tego powtarzasz wszystkie opcje w obecnej sytuacji.

Pomyśl o znalezieniu rozwiązania dla labiryntu. W jednym punkcie, w którym masz dwie różne ścieżki, najpierw wypróbuj lewą. Jeśli lewy nie prowadzi do wyjścia, wróć do punktu i wypróbuj inną ścieżkę. Tak działa backtracking. W 8 Q i innych problemach, w których można zastosować powrót, myląca część znajduje się w domenie problemu - jak iterować po opcjach w danej sytuacji w sposób deterministyczny.

EDYCJA : poniżej znajduje się pseudo kod pomagający zrozumieć powrót do przeszłości.

# 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

W przypadku pytania 8Q:

• state.get_all_options zwróci listę możliwych pozycji dla następnej królowej
• state.is_resolved sprawdzi, czy wszystkie królowe są na planszy i czy są ze sobą dobre.
• state.apply i state.undo zmodyfikują tablicę, aby zastosować lub cofnąć pozycjonowanie.

Widziałeś program do chodzenia po drzewie binarnym, prawda? To wygląda tak:

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)
  }
}

Tu jest twój powrót.

W rzeczywistości nie potrzebujesz fizycznego drzewa. Wszystko czego potrzebujesz to sposób, aby wykonać ruch, a następnie cofnąć go lub powiedzieć, czy wygrałeś, lub powiedzieć, czy nie możesz iść dalej.