我需要遞歸算法

Question

期間停止執行我有一個問題，在選擇實現我的目標正確的方法。 我對算法教學系統的工作，我使用C＃。我需要將我的算法分成幾步，每一步都會包含一個遞歸。 我必須停止在每個步驟之後執行，用戶可以在我的GUI用一個按鈕然後移動到下一個步驟（下一遞歸）。

搜索，線程後是正確的選擇，但我發現了幾個方法：

• （的Thread.sleep /中斷）：沒有工作，我的GUI凍結！

• （掛起/恢復）：我讀過這是一個壞主意，使用。

• （Waithandles）：仍然閱讀有關它們。

• （顯示器等待/恢復）。

我沒有太多的時間去嘗試和讀取所有以前的方法，請幫我在選擇適合我的system.Any建議是極值歡迎的最佳方法。

Answer 1

從根本上說，這個問題是不是真正的遞歸或支持多線程，它很簡單：

如何在一個GUI應用程序的後臺執行一個長期運行的操作，這樣該應用住宿響應？

實現自己的線程模型是不去這裏的路，特別是如果你是剛開始學習多線程/異步操作。 .NET框架已經有你想要做的一個組件：BackgroundWorker，它可以在Winforms和WPF（以及幾乎任何其他體系結構）中工作。

使用BackgroundWorker來完成您想要的任務非常非常容易。我將假設Winforms爲這個例子，但是這是just as easy in WPF。

// Don't actually write this line; it will be in the .designer.cs file when you 
// drop a BackgroundWorker onto the form/control. This is for reference only. 
private BackgroundWorker bwRecursive; 

private void bwRecursive_DoWork(object sender, DoWorkEventArgs e) 
{ 
    MyTreeNode root = (MyTreeNode)e.Argument; 
    ExecuteRecursiveOperation(root); 
} 

private void bwRecursive_RunWorkerCompleted(object sender, 
    RunWorkerCompletedEventArgs e) 
{ 
    // Optionally update the GUI with the results here 
} 

private void ExecuteRecursiveOperation(MyTreeNode node) 
{ 
    if (bwRecursive.CancellationPending) 
     return; 

    foreach (MyTreeNode childNode in node.ChildNodes) 
    { 
     if (bwRecursive.CancellationPending) 
      break; 

     ExecuteRecursiveOperation(childNode); 
    } 
} 

顯然，你也必須要連接的DoWork和RunWorkerCompleted事件，並確保設置WorkerSupportsCancellation到true在BackgroundWorker。在此之後，運行與操作：

bwRecursive.RunWorkerAsync(someTreeNode); 

並與取消：

bwRecursive.CancelAsync(); 

---

這裏唯一的皺紋是，你說你希望每個之後暫停（不停止）執行「步」。我可能會使用AutoResetEvent來做到這一點，這是一種事件類型，每次等待成功時都會重置其信號（「就緒」）狀態。再次，這是隻有幾行代碼整合：

public class MyForm : Form 
{ 
    private AutoResetEvent continueEvent = new AutoResetEvent(false); 

    // Previous BackgroundWorker code would go here 

    private void ExecuteRecursiveOperation(MyTreeNode node) 
    { 
     if (bwRecursive.CancellationPending) 
      return; 

     foreach (MyTreeNode childNode in node.ChildNodes) 
     { 
      continueEvent.WaitOne(); // <--- This is the new code 

      if (bwRecursive.CancellationPending) 
       break; 

      ExecuteRecursiveOperation(childNode); 
     } 
    } 

    private void btnContinue_Click(object sender, EventArgs e) 
    { 
     continueEvent.Set(); 
    } 

    private void btnCancel_Click(object sender, EventArgs e) 
    { 
     bwRecursive.CancelAsync(); 
     continueEvent.Set(); 
    } 

    private void btnStart_Click(object sender, EventArgs e) 
    { 
     continueEvent.Set(); 
     bwRecursive.RunWorkerAsync(...); 
    } 
} 

有一件事可能在這裏需要額外的解釋，那就是取消方法，它先取消，然後設置continueEvent。有必要這樣做，因爲如果工作人員仍在等待事件發生，實際上將不會取消到取消階段，因此當您取消時，您需要允許該工作人員繼續。如果您希望執行第一步而不要求用戶點擊「繼續」，則您還需要設置continueEvent當開始工作人員。「

Answer 2

你只需要，如果你想「在後臺」，而你的用戶界面仍然是互動的，或者如果你想達到分裂緩慢的任務，以便它可以在多個處理器內核來執行辦工作中使用線程。

你描述聽起來像你只需要編寫一個單獨的線程：

• 記住當用戶要由順序排列。
• 每次點擊您的按鈕，執行下一步

如果你想使用線程，那麼你可以使用的AutoResetEvent，讓你的線程遍歷的步驟，對WaitOne的每個迭代。只要用戶點擊按鈕開始下一步，用戶界面就會發出該事件的信號。 （您還需要在一步完成，因此用戶只能運行在序列中的步驟通知UI - 以爲你可以只設立button.Enabled =假，當他們開始了一步，而線程可以使用button.Invoke設置當完成步驟時，Enabled = true）。但是，線程聲音過於複雜，你似乎在描述。

Answer 3

一切你上市將阻止執行，如果你的代碼是在主線程中執行將凍結UI。

如果您只需要暫停操作，然後恢復或取消操作，那麼您必須將計算移至單獨的線程，以便凍結它不會影響用戶界面。

您也可以從不同的角度來處理你的問題。你可以重新設計你的算法，使他們可以從任何位置重新開始 - 讓你的遞歸堆棧外，它作爲一個參數傳遞

Answer 4

線程是很好的，只要你使用它的正確方法。我要說開始與以下步驟：

1. 創建，還有一種形式，兩個按鈕和兩個ProgressBar S（B1，B2，P1，P2 ...例如）。
2. 當按鈕b1被點擊時，在BackgroundWorker中啓動遞歸算法1，並顯示進度條p1中的進度。如果重要的是讓用戶不要按其他按鈕，則可以禁用按鈕，直到p1完成。
3. 當用戶點擊p2中的按鈕b1，update the progress bar時。

This example可能會有幫助。

Answer 5

你正朝着正確的方向等待處理。

嘗試使用AutoResetEvent。我認爲這是讓你想去的地方。

Answer 6

如果您對遞歸教學感興趣，同時允許算法在每次迭代時暫停，您可能需要考慮創建一個狀態管理器類來包裝算法並公開一個顯式堆棧。遞歸算法實際上是一個。的基於堆棧的算法形式，所以不必跑單次迭代，看到堆棧中的內容將幫助演示如何遞歸實際運行的能力，我可以想像這樣的：

public struct AlgorithmParameters 
{ 
    public readonly int Parameter1; 
    public readonly int Parameter2; 

    public AlgorithmParameters(int parameter1, int parameter2) 
    { 
     Parameter1 = parameter1; 
     Parameter2 = parameter2; 
    } 
} 

public class RecursiveAlgorithm 
{ 
    private Stack<AlgorithmParameters> _parameterStack = new Stack<AlgorithmParameters>(); 

    public IEnumerable<AlgorithmParameters> ParameterStack 
    { 
     get { return _parameterStack; } 
    } 

    public IEnumerable<RecursiveAlgorithm> RunAlgorithm(int parameter1, int parameter2) 
    { 
     return RunAlgorithm(new AlgorithmParameters(parameter1, parameter2)); 
    } 

    public IEnumerable<RecursiveAlgorithm> RunAlgorithm(AlgorithmParameters parameters) 
    { 
     //Push parameters onto the stack 
     _parameterStack.Push(parameters); 

     //Return the current state of the algorithm before we start running 
     yield return this; 

     //Now execute the algorithm and return subsequent states 
     foreach (var state in Execute()) 
      yield return state; 
    } 

    private IEnumerable<RecursiveAlgorithm> Execute() 
    { 
     //Get the parameters for this recursive call 
     var parameters = _parameterStack.Pop(); 

     //Some algorithm implementation here... 

     //If the algorithm calls itself, do this: 
     int newParameter1 = 2; //Parameters determined above... 
     int newParameter2 = 5; 
     foreach (var state in RunAlgorithm(newParameter1, newParameter2)) 
      yield return state; 

     //More implementation here... 

     //We've finished one recursive call, so return the current state 
     yield return this; 
    } 
} 

我沒有測試過這個代碼，但希望這給你的想法。「yield return」結構本質上將它變成一個實現遞歸算法的狀態機，其中stack re在每次迭代中呈現參數。爲了迭代運行算法，獲得一個IEnumerator並以任何你喜歡的速度迭代。每次迭代後，您可以檢查堆棧並顯示它以提供有關算法如何進展的有用信息。

Answer 7

你不需要爲此多線程。遞歸或迭代算法已經適用於步進。

class MainWnd : Form{ 
    /* 
    * A typical recursive factorial function would be 
    * implemented something like this: 
    */ 
    double Factorial(int n){ 
     return (double)n * Factorial(n - 1); 
    } 

    /* 
    * Alternatively, factorial can be implemented iteratively: 
    */ 
    double Factorial(int n){ 
     double product = n; 
     while(--n > 1) 
      product *= n; 
     return product; 
    } 

    /* 
    * Let's break the logic up into steps, so that it 
    * saves its state between steps and resumes where 
    * it left off for the next step. 
    */ 

    int factorialN; 
    double factorialProduct; 

    void BeginSteppedFactorial(int n){ 
     factorialProduct = n; 
     factorialN  = n - 1; 
    } 
    bool StepFactorial(){ 
     if(factorialN <= 1) 
      return true; // we're done, the result is ready 

     factorialProduct *= factorialN--; 
     return false; // we're not yet done, call the next step 
    } 
    double GetSteppedFactorialResult(){return factorialProduct;} 


    static void Main(){Application.Run(new MainWnd());} 
    MainWnd(){ 
     BeginSteppedFactorial(32); 

     Label lbl = new Label(){ 
      AutoSize = true, 
      Location = new Point(10, 10), 
      Text  = GetSteppedFactorialResult().ToString(), 
      Parent = this 
     }; 
     Button btn = new Button(){ 
      Location = new Point(10, 30), 
      Text  = "Next Step", 
      Parent = this 
     }; 
     btn.Click += (s, e)=>{ 
      if(StepFactorial()){ 
       btn.Text = "Finished"; 
       btn.Enabled = false; 
      } 
      lbl.Text = GetSteppedFactorialResult().ToString(); 
     }; 
    } 
} 

這是一個工作的例子，儘管階乘是一個很簡單的功能，骨骼是在這裏更復雜的程序。

Answer 8

的AutoResetEvent + BackgroundWorker的是一個完美的選擇:)