주어진 : 그리드 m × n
하나 이상의 교차로가 있고 역 추적과 재귀를 사용하여 오른쪽 상단에서 끝나는 모든 경로를 열거해야합니다! 어떤 제안.?
Self-Avoiding Walk역 추적 재귀를 사용하여 자체 회피 보행
-1
A
답변
3
비 재귀 방법은 이전의 위치와 그 위치에서 의사 결정을 필요로하는 정보의 스택을 유지하는 것입니다. 결정이 내려 질 때마다 저장해야하는 정보를 스택 맨 위에 밀어 넣으십시오.
그런 다음 검색에서 문제가 발견되면 스택을 팝하고 가장 최근의 결정 포인트로 돌아가서 다른 결정을 내립니다. 결국 당신은 성공하거나 모든 가능한 경로를 불가능한 것으로 제거합니다.
재귀 적 솔루션의 경우 정보를 스택에 푸시하는 대신 재귀 호출에서 결정한 후에 새 위치를 전달합니다. 재귀 호출이 실패를 반환하면 현재 위치에서 다음 가능한 결정을 시도합니다. 현재 위치에서 선택 사항을 모두 사용하지 못하면 위의 레벨로 실패를 리턴하십시오. 재귀 호출이 성공을 반환하는 경우에만이 수준에서 성공을 반환합니다.
마지막으로 성공은 전체 호출 체인에서 반환되거나 가능한 모든 경로는 제거됩니다.
숙제이기 때문에 한 수준에서 다른 수준으로 전달해야하는 정보와 최종 성공 경로를 응용 프로그램에 반환하는 방법을 직접 결정해야합니다.
필요한 모든 새로운 아이디어는 위의 단락에 나와 있습니다. 구현은 당신에게 달려 있습니다.
- 제시
+0
+1 숙제에 대한 좋은 답변입니다. –
관련 문제
- 1. 역 추적
- 2. 재귀 - 메모리 할당을 사용하여 C의 격자에서 자체 회피 임의 회선
- 3. ?? OpenMP를 역 추적
- 4. 자바 디버그에서 역 추적
- 5. 역 추적 재귀 질문
- 6. GDB - 역 추적
- 7. LISP 역 추적
- 8. NHibernate와 자체 추적 엔티티
- 9. IsLoaded 자체 추적 엔티티
- 10. 역 추적 라인 검색 R
- 11. 자식 프로세스의 GDB 역 추적
- 12. gdb 역 추적 및 pthread_cond_wait()
- 13. 자체 추적 엔터티 - 탐색 속성의 탐색 속성로드
- 14. 자체 추적 엔티티 및 지연로드
- 15. Entity Framework - 자체 추적 엔터티
- 16. 재귀를 사용하여 다항식 추가하기
- 17. 하스켈 재귀를 사용하여 누산기
- 18. 재귀를 사용하여 문자열 반전
- 19. 재귀를 사용하여 가능한 범주화
- 20. 재귀를 사용하여 removeLastElement를 만들려고합니다.
- 21. 재귀를 사용하여 계열을 계산하십시오.
- 22. 재귀를 사용하여 함수
- 23. 재귀를 사용하여 정렬
- 24. 재귀를 사용하여 오버플로 스택
- 25. 재귀를 사용하여 최소값 찾기
- 26. 재귀를 사용하여 Palindrome을 확인하십시오.
- 27. 재귀를 사용하여 다항식을 더하기
- 28. 자바에서 재귀를 사용하여 명확화
- 29. 재귀를 사용하여 문자열 결합
- 30. 보행 가능한 스프라이트 도움말
지금까지 무엇을 했습니까? –
나는 어떻게 시작 해야할지 모르겠다! – Rawhi
명백한 출발점은 홍수 채우기 스타일 알고리즘입니다. 시작 스퀘어 (지정되지 않은 경우)를 선택하여 사용 된 것으로 표시 한 다음 사용 된 것으로 표시되지 않은 모든 이웃을 재귀 적으로 시도하십시오. –