停止回溯

C/C++有沒有什麼辦法可以在不退出程序的情況下找到第一個解決方案後停止回溯算法。停止回溯

我想讓我的函數立即退出函數，而不是退出每一個級別的循環，逐一說明返回。

來源

2010-04-25 John Retallack

C和C++有很大的不同語言。你在用哪個？ – 2010-04-25 14:27:24

我使用C++，但我對C和C++都感興趣 – 2010-04-25 14:29:21

通常回溯算法處理某些樹的高度，遞歸不是很深*。微型優化可能不會讓你的程序更高效。 – 2010-04-25 15:08:38

你可以使用C和C++的原油，但繞過需要的有效途徑的setjmp（）/ longjmp的（）傳遞一個標誌一路回來。

來源

2010-04-25 14:42:22

我認爲'setjmp'和'longjmp'應該永遠不會用在C++中 – 2010-04-25 14:44:25

它應該非常小心地使用，longjmp繞過析構函數調用。雖然不能擊敗速度。 – 2010-04-25 14:49:18

他們可能永遠不會被使用（因此粗糙但有效的評論），但他們在那裏，可以在C和C++中使用（小心！）。 – 2010-04-25 14:52:05

它實際上取決於你的實現，但你可以設置一些特殊的參數，並將其用作「我們是否得到解決方案？如果是，然後放棄你當前的例程並獲得輸出解決方案」的標誌。

來源

2010-04-25 14:26:21

如何中止例程，如果你聲明'返回'它只會退出當前的遞歸級別 – 2010-04-25 14:28:27

如果標誌被設置爲退出，像'if（flag == exit_flag）return'會遞歸地從每個recusion級別退出旗。只需找到你的算法實現方法。 – 2010-04-25 14:31:37

是的，但是會一次退出一個級別，直到我達到第一級。我有興趣在找到解決方案不會退出每個級別之前立即退出遞歸，直到我成爲第一級。 – 2010-04-25 14:36:50

一個快速和骯髒的方法是拋出一個異常並將其捕獲到基級（現在很多人會尖叫到只使用異常來處理錯誤，我認爲創建解決方案是一個例外事件，因爲不是找到一個是常態）

來源

2010-04-25 14:30:16

如果你有一個標誌，當你完成設置，然後檢查你的功能，你可以解決這個問題。例如

void foo(..) 
{ 
    if (g_done) return; 
... 
}

來源

2010-04-25 14:34:50

不知道你需要什麼，我會考慮實現你自己的堆棧，並完全避免遞歸。這樣，退出回溯樹（單個「返回」）變得很簡單，並且還可以通過再次調用函數來恢復搜索以找到下一個解決方案，假定用戶定義的堆棧的狀態被保留（在靜態變量中）。當然，將一個簡單的遞歸程序轉換成一個循環會有一些編程開銷，但這很簡單。

來源

2010-04-25 14:48:59 Nathan

管理你自己的堆棧很容易出錯，除非你需要壓縮性能的最後一點，將自然遞歸算法混淆成迭代算法幾乎沒有什麼好處。 – 2010-04-25 14:58:18

假設沒有必要重用堆棧，我不認爲分配/取消分配堆棧會更有效的遞歸和*返回*。 – 2010-04-25 15:18:03

使用你自己的堆棧，你可以預先分配最大深度，避免陷入堆棧溢出，避免存儲返回地址，避免存儲在遞歸調用中不需要保存的本地人，避免方法序言/結尾，使它更容易優化器可以存儲快照並在稍後繼續，並且 - 如上所述 - 可以隨時停止，可以在任何深度停止。 ----它通常是更多的代碼，但更容易分析讀者不理解遞歸，允許更好的調試+診斷，這是一個通常的代碼轉換，有時是必要的。 – peterchen 2010-04-25 15:59:19

爲什麼要讓函數立即退出？不通過堆棧回溯是危險的，因爲您可能需要銷燬其上的對象。拋出一個異常可能是由於你的技巧，它會清理堆棧。提供更多關於您想要做什麼的信息，並且我們可能會提供其他方法。

來源

2010-04-25 14:54:12

如果您的回溯算法實際上遞歸得足夠深以至於不重要，您不應該使用遞歸，因爲您將有可能吹動堆棧。你不應該犯一些涉及longjmp的暴行，你應該考慮用你自己的堆分配棧來重寫你的算法，以迭代方式存儲代表狀態的POD對象。當你找到你的解決方案時，可以在一個有效的步驟中銷燬狀態容器，並且可以返回答案。

見Way to go from recursion to iteration

來源

2010-04-25 15:48:33 Alan

首先，請注意，你不能對任何遞歸函數做到這一點。考慮下面的代碼：

int SumNum(int nMax) 
{ 
    if (0 == nMax) 
     return 0; 
    else 
     return nMax + SumNum(nMax-1); 
}

回溯時的實際值被計算。

但是，您可以通過以下方式重寫代碼：

int SumNum(int nMax, int nSum) 
{ 
    if (0 == nMax) 
     return nSum; 
    else 
     return SumNum(nMax-1, nSum+nMax); 
}

現在，你可以做下面的技巧：

int SumNum(int nMax, int nSum) 
    { 
     if (0 == nMax) 
      throw nSum; 
     else 
      return SumNum(nMax-1, nSum+nMax); 
    } 


f() 
{ 
     int nSum; 

     try 
     { 
      SumNum(100, 0); 
     } 
     catch (int _nSum) 
     { 
      nSum= _nSum; 
     } 
}

來源

2010-04-25 18:16:13

回答

相關問題