재귀 적 검색을 수행하는 방법은 무엇입니까?

Question

나는 같은 종류의 내가 재귀 검색 LINQ (아마도) 가장 빠른 시작 날짜가 작업을 찾을를 수행하는 방법을

public class Task 
{ 
    public DateTime Start { get; set;} 
    public DateTime Finish { get; set;} 
    public List<Task> Tasks {get; set;} 
    public DateTime FindTaskStartDate(Task task) 
    {} 
} 

의 하위 작업을 할 수있는 작업 클래스가?

초기 접근법은 너무 많은 루프를 필요로하고 결국 약간의 엉망이되어 제어 불능 상태가되었습니다. 두 번째 시도는 다음과 같습니다.

public DateTime FindTaskStartDate(Task task) 
{ 
    DateTime startDate = task.Start; 

    if(task.HasSubTasks()) 
    { 
     foreach (var t in task.Tasks) 
     { 
      if (t.Start < startDate) 
      { 
       startDate = t.Start; 

       if (t.HasSubTasks()) 
       { 
        //What next? 
        //FindTaskStartDate(t); 
       } 
      } 
     } 
    } 

    return startDate; 
} 

더 좋은 솔루션으로이 문제를 해결할 수 있습니까?

감사

Answer 1

당신은 맞다는 재귀 여기에 올바른 접근 방식이다. 이런 식으로 뭔가 작업을해야합니다 : 나는 task.HasSubTasks()에 대한 체크를 제거

public DateTime FindTaskStartDate(Task task) 
{ 
    DateTime startDate = task.Start; 

    foreach (var t in task.Tasks) 
    { 
     var subTaskDate = FindTaskStartDate(t); 
     if (subTaskDate < startDate) 
      startDate = subTaskDate; 
    } 

    return startDate; 
} 

, 그것은 단지 어떤 추가 혜택없이 코드를 더 복잡하게하기 때문이다.

자주 트리에서 모든 작업을 수행해야하는 코드를 발견하면이 코드를 좀 더 일반적인 코드로 만들 수 있습니다. 예를 들어 트리의 모든 작업을 반환하는 IEnumerable<Task>을 반환하는 메서드를 사용할 수 있습니다.

IterateSubTasks(task).Min(t => t.Start) 

Answer 2

당신이 모든 항목에서 수행 할 다른 작업이있는 경우 도움이 될 수 있습니다 검색에서 나무를 통해 반복을 분리 :로 작은 시작 날짜를 찾는 것은 다음과 같은 쉬운 것입니다. 나는. 트리 항목 위에 IEnumerable을 구현하면 LINQ 쿼리를 사용하여 원하는 모든 것을 검색하거나 트리의 모든 작업에 대해 다른 작업을 수행 할 수 있습니다. 이렇게하려면 Implementing IEnumerable on a tree structure을 확인하십시오.

Answer 3

스빅의 해결책은 괜찮지 만, 좀 더 일반적인 조언을 덧붙이겠다고 생각했습니다. 당신이 재귀 적 방법을 쓰는 것에 익숙하지 않은 것처럼 보였고 거기에서 조금 어려움을 겪고있었습니다. 재귀 메서드를 작성하는 가장 쉬운 방법은 엄격하게 패턴을 따르는 것입니다 :

Result M(Problem prob) 
{ 
    if (<problem can be solved easily>) 
     return <easy solution>; 
    // The problem cannot be solved easily. 
    Problem smaller1 = <reduce problem to smaller problem> 
    Result result1 = M(smaller1); 
    Problem smaller2 = <reduce problem to smaller problem> 
    Result result2 = M(smaller2); 
    ... 
    Result finalResult = <combine all results of smaller problem to solve large problem> 
    return finalResult; 
} 

그래서

문제를 해결하려는 생각을 "내 이진 트리의 최대 깊이 무엇인가?"

• 문제는 당신이 재귀 작은 때마다 얻을 수 있습니다

  int Depth(Tree tree) 
  { 
      // Start with the trivial case. Is the tree empty? 
      if (tree.IsEmpty) return 0; 
      // The tree is not empty. 
      // Reduce the problem to two smaller problems and solve them: 
      int depthLeft = Depth(tree.Left); 
      int depthRight = Depth(tree.Right); 
      // Now combine the two solutions to solve the larger problem. 
      return Math.Max(depthLeft, depthRight) + 1; 
  } 
  

  당신은 재귀 일을 할 세 가지가 필요합니다.

• 결국 문제는 너무 작아서 재귀없이 해결할 수 있습니다.
• 문제는 일련의 더 작은 문제로 분해하여 각각을 해결하고 결과를 결합하여 해결할 수 있어야합니다.

세 가지를 보장 할 수없는 경우 은 재귀 솔루션을 사용하지 마십시오.