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.
Odpowiedzi:
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.
W przypadku pytania 8Q:
źródło
Widziałeś program do chodzenia po drzewie binarnym, prawda? To wygląda tak:
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.
źródło
else{return walk(p->left)||walk(p->right));}
nie trzeba rzucać dla oczekiwanego rezultatu