Zrozumienie cofania w C ++

12

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.

nikhil
źródło
Myślę, że to dobre pytanie, ale myślę, że lepiej byłoby podkreślić prośbę o wyjaśnienie cofania się niż proszenie o samouczki lub inne zasoby. Dogłębne wyjaśnienie odpowiedzi bije listę referencji każdego dnia.
Adam Lear
Byłoby idealnie, gdyby ktoś mógł podać szczegółowe wyjaśnienie, ale nie miałbym też nic przeciwko czytaniu referencji. Po prostu nie wiem od czego zacząć.
nikhil

Odpowiedzi:

9

... 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.
Codism
źródło
Pierwszym kodem rekurencyjnym, który napisałem (w 1984 r. Przy użyciu Pascala) dla zadania, był algorytm rozwiązywania labiryntu.
Gerry
Wiedz o prostym zadaniu, w którym mogę napisać kod, aby uzyskać rzeczywiste wyczucie tego typu rzeczy.
nikhil
@nikhil: pytasz, czy jest jakiś prosty problem? Lepiej jest napisać pseudo-kod, aby zademonstrować ogólne kierowanie cofania. Spróbuję później w odpowiedzi.
Codism
Tak, to będzie najbardziej pomocne.
nikhil
Dziękuję bardzo, ostatnio czytałem kilka rzeczy. Powoli, ale konsekwentnie moje rozumienie się poprawia.
nikhil
5

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.

Mike Dunlavey
źródło
1
nie możesz zwrócić bool / int, aby sprawdzić, czy rozwiązanie znajduje się w poddrzewie? else{return walk(p->left)||walk(p->right));}nie trzeba rzucać dla oczekiwanego rezultatu
maniak zapadkowy
@ratchet: Absolutnie. To także doskonale dobry sposób na zrobienie tego. (Próbowałem po prostu zaśmiecać przykład. Zrobiłbym to po swojemu.)
Mike Dunlavey,
Jednak cięcie @MikeDunlavey jest dość ważne w praktyce.
jupp0r