用修剪搜索迴避回溯

我有一個遞歸函數，它用每個節點中的所有字符來分析trie字符串數據庫。在遞歸調用時，編輯計數會遞增，然後測試新字符串1）是否已解析所有節點，以及2）字符串是否等於批准字符串列表中的字符串。所以，結果應該是測試字符串和數據庫中所有可能的字符串之間的編輯距離。用修剪搜索迴避回溯

void suggestCorrections(nodeT *w, Set<CorrectionT> &suggest, int index, string test, string final, double edits) 
{ 
    if (word == "") { 
     if (containsCode(final)) //compare with list of approved strings 
      updateSet(w, suggest, final, edits); 

    } else { //continue to search path 
     if(w->alpha.size() > index) { 
      if (test[0] == w->alpha[index].char) 
       suggestCorrections(w->alpha[index].next, suggest, 0, test.substr(1), final+test[0], edits); //follow matching char 
      suggestCorrections(w, suggest, ++index, test, final, edits);//check next path 
      suggestCorrections(w->alpha[index].next, suggest, 0, test.substr(1), final+w->alpha[index].char, ++edits);//follow path 
     } 
    } 
} 


struct CorrectionT { 
    double editDistance; //stackItems 
    string suggestedWord; //stackItems 
    string suggestDescription; 
    string gates; 
};

問題是，當所述W-> alpha.size（）等於索引 - 的路徑是否正確結束，但隨後被輸入的最後一個路徑suggestCorrections(w->alpha[index].next, suggest, 0, test.substr(1), final+w->alpha[index].char, ++edits);，當索引遞增過去W-的端> α。爲什麼會發生？它是如何修復的？

我認爲當路徑結束時，通過函數回溯。我不想讓它回溯。我檢查了調用堆棧並設置了休息，但這似乎是一個概念問題，而不是一個錯誤。另外，我閱讀了關於遞歸和維基百科頁面的教科書一章 - 我理解回溯的概念，但不瞭解在這種特定情況下的實現（或缺乏）。我用backtracking來建立特里數據庫，它在那裏工作，但是從這裏不同，我不知道這一點。

來源

2012-08-02 forest.peterson

我添加了返回到每個遞歸調用 - >'返回suggestCorrections（w-> alpha [index] .next，...）;'，現在它不回溯 - 我真的很想了解我我在這裏做。解決這個問題的方法似乎有點粗略。 – 2012-08-03 00:11:55

在倒數第二次調用suggestCorrections時，您傳遞的是++索引。這是遞增索引的值，然後在上次調用建議修正時傳入。我沒有真正理解你的代碼，但看起來你可能只想在倒數第二次調用中傳遞索引+1，而不是++索引。

一般來說，在函數調用參數中隱藏增量操作並不是好的編程習慣（至少在我看來）。這使得讀取和調試代碼變得困難。

來源

2012-08-02 23:56:28 happydave

我在早期版本中使用了'index + 1'，'++ index'看起來更酷，所以我改變了它。你能解釋爲什麼在編譯器中這在功能上是不同的？ – 2012-08-03 00:10:30

從'++ index'到'index + 1'的changine沒有做太多 – 2012-08-03 00:25:04

++ index修改索引的值，所以任何時候在同一個函數中稍後引用索引時，它都會使用遞增的值。因此，如果索引==大小進入if語句，它將等於大小+ 1當你在最後一次調用時使用它來建議修正 – happydave 2012-08-03 01:26:51

用修剪搜索迴避回溯

回答

相關問題