공백 유형으로 재귀 backtracking을 반환하는 방법

Question

이 질문을 일반화하기 위해 Zelenski CS 수업 자료를 빌려 왔습니다. 그리고 저는 몇 년 전에 다른 강사로부터 수업을 들었고 C++에 대한이 접근법을 배웠기 때문에 제 특정한 질문과 관련이 있습니다. 유인물은 here입니다. C++에 대한 나의 이해는 가끔씩 사용하기 때문에 낮습니다. 기본적으로 몇 번이나 수업 자료로 돌아가서 비슷한 것을 발견하고 거기서 시작한 프로그램을 작성해야했습니다.

이 예제 (4 페이지)에서 줄리는 문자열 함수에서 재귀 알고리즘을 사용하여 단어를 찾고 있습니다. 재귀 호출 수를 줄이기 위해 그녀는 결정 점 bool containsWord()을 추가했습니다.

string FindWord(string soFar, string rest, Lexicon &lex) 
{ 
    if (rest.empty()) { 
    return (lex.containsWord(soFar)? soFar : ""); 
    } else { 
    for (int i = 0; i < rest.length(); i++) { 
    string remain = rest.substr(0, i) + rest.substr(i+1); 
    string found = FindWord(soFar + rest[i], remain, lex); 
    if (!found.empty()) return found; 
    } 
    } 
return ""; // empty string indicates failure 
} 

이 알고리즘을 사용하는 방법에 유연성을 추가하려면 void 유형으로 구현할 수 있습니까?

void FindWord(string soFar, string rest, Lexicon &lex, Set::StructT &words) 
{ 
    if (rest.empty()) { 
    if (lex.containsWord(soFar)) //this is a bool 
     updateSet(soFar, words); //add soFar to referenced Set struct tree 
    } else { 
    for (int i = 0; i < rest.length(); i++) { 
    string remain = rest.substr(0, i) + rest.substr(i+1); 
    return FindWord(soFar + rest[i], remain, lex, words); //<-this is where I am confused conceptually 
    } 
    } 
return; // indicates failure 
} 

그리고, 방법에 대한 첫 번째 코드 조각이 soFar의 초기 값에 추가 rest의 모든 순열, 시도 할 것이다

void FindWord(string soFar, string rest, Lexicon &lex, Set::StructT &words) 
{ 
    if (rest.empty()) { 
    if (lex.containsWord(soFar)) 
     updateSet(soFar, words); //add soFar to Set memory tree 
    } else { 
    for (int i = 0; i < rest.length(); i++) { 
    string remain = rest.substr(0, i) + rest.substr(i+1); 
    FindWord(soFar + rest[i], remain, lex, words); //<-this is where I am confused conceptually 
    } 
    } 
} 

Answer 1

수익이없는 (아마도 빈 문자열을?). 발견 된 첫 번째 단어에서 멈추며 그 단어는 lex입니다. 해당 단어는 발견되면 즉시 반환되며 검색은 그 시점에서 짧게 절단됩니다. lex이 없으면 모든 for 루프가 끝까지 실행될 때 빈 문자열이 결국 반환됩니다.

두 번째 조각은 한 단어 만 시도합니다. 즉, soFar과 rest 문자열의 연결입니다. 해당 연결 문자열이 lex 인 경우 updateSet을 호출합니다. 그런 다음 실패를 나타내는 리턴합니다. for 루프 내부의 return이 무조건이기 때문에 추가 검색이 수행되지 않습니다.

그래서이 두 기능은 완전히 다릅니다. 두 번째 코드가 첫 번째 코드처럼 동작하도록하려면 성공을 나타 내기 위해 다른 것을 반환해야하며 FindWord 호출 반환 값이 성공을 나타낼 때 for 루프 내에서만 반환해야합니다. 분명히 void은 failure과 success을 알리는 데 사용할 수 없습니다. 최소한, bool 값을 반환해야합니다.

반환하지 않고 세 번째 코드는 철저한 검색을 수행합니다. 어휘집에서 찾으려면 초기 문자열 값 rest의 모든 가능한 순열을 시도합니다.

당신은 이런 식으로 무슨 일이 일어나고 있는지 시각화 할 수 있습니다 :

FindWord: soFar=""  rest=........... 
    for: i=... rest[i]=a 
     call findWord 

FindWord: soFar=a  rest=.......... 
    for: i=... rest[i]=b 
     call findWord 

FindWord: soFar=ab  rest=......... 
    for: i=... rest[i]=c 
     call findWord 
     if return, the loop will be cut short 
     if not, the loop continues and next i will be tried 

...... 

FindWord: soFar=abcdefgh...  rest=z 
    for: i=0  rest[0]=z 
     call findWord 

FindWord: soFar=abcdefgh...z  rest=""  // base case 
    // for: i=N/A rest[i]=N/A 
    if soFar is_in lex       // base case 
     then do_some and return soFar OR success 
     else    return ""  OR failure 

기본 케이스 (rest가 비어있는) 우리가 초기 rest 문자열에 n 편지의 스택에 n+1FindWord 전화 프레임을 가지고에 도달 할 때마다 .

우리가 아래를 칠 때마다, 우리는 rest에서 모든 편지를 골랐습니다. 검사는 그것이 lex에 있는지 확인하기 위해 수행되고 제어는 한 레벨 위로 되돌아갑니다.

따라서 반환 값이 없으면 각 for 루프가 끝까지 실행됩니다.반환 값이 무조건적인 경우, 단지 하나의 순열이 시도 될 것입니다 - 사소한 것이지요. 그러나 반환이 조건부 일 경우, 모든 것은 첫 번째 성공에서만 멈출 것입니다.