Cải thiện phương pháp đệ quy trong C#

Question

Đây là mã của tôi:

static int cardGameValue(List<int> D, int myScore, int opponentScore) 
    { 
     if (D.Count == 0) return myScore; 
     else if (D.Count == 1) 
     { 
      opponentScore += D[0]; 
      return myScore; 
     } 
     else 
     { 
      if (D[0] <= D[D.Count - 1]) 
      { 
       opponentScore += D[D.Count - 1]; 
       D.RemoveAt(D.Count - 1); 
      } 
      else 
      { 
       opponentScore += D[0]; 
       D.RemoveAt(0); 
      } 

      int left = cardGameValue(new List<int>(D.GetRange(1, D.Count - 1)), myScore + D[0], opponentScore); 

      int right = cardGameValue(new List<int>(D.GetRange(0, D.Count - 1)), myScore + D[D.Count - 1], opponentScore); 

      if (left >= right) 
      { 
       return left; 
      } 
      else 
      { 
       return right; 
      } 
     } 
    } 
} 

Mã của tôi phải mất một tập hợp các thẻ và đại diện cho số điểm tối đa có thể của bạn khi thi đấu với một đối thủ xác định. Sau mỗi lượt chơi của đối thủ, bạn có 2 lựa chọn cho đến khi tất cả các lá bài được chọn. Có cách nào để lưu trữ kết quả của tôi về các lần lặp lại để tôi có thể cải thiện thuật toán của mình không? Vì vậy, đệ quy không làm lặp đi lặp lại không cần thiết? Bởi vì sau 40 hoặc 50 thẻ nó trở nên rất chậm.

Answer 1

Bạn chỉ truy cập phần tử đầu tiên hoặc phần tử cuối cùng trong danh sách D. Thay vì vượt qua danh sách chính xác, bạn có thể chuyển danh sách thẻ đầy đủ (hoặc thậm chí tốt hơn: dưới dạng mảng int) cùng với chỉ mục của vị trí đầu tiên và vị trí cuối cùng.

Nhanh hơn để tính toán điểm số của đối phương sau khi tính toán hoàn thành: myScore và opponentScore cộng lại tổng giá trị của thẻ, để bạn có thể thực hiện điều này trong thời gian O (n). Bằng cách này, bạn có thể loại bỏ tất cả mã cập nhật opponentScore.

Bạn không cần phải vượt qua myScore một trong hai. Nếu bạn để cardGameValue trả lại điểm số tốt nhất thu được từ các thẻ còn lại.

Cuối cùng, nếu bạn làm việc với chỉ mục đầu tiên và cuối cùng, bạn có thể lưu trữ điểm số trong một mảng 2D, được lập chỉ mục bởi first và last.Nếu tất cả các thẻ có giá trị dương, thì điểm số phải dương nếu có ít nhất hai thẻ còn lại.

Vì vậy, khi bắt đầu cuộc gọi, bạn kiểm tra xem điểm lưu trong bộ nhớ cache có dương không. Nếu có, bạn có thể trả lại ngay lập tức. Nếu không, bạn phải tính toán nó, và sau đó lưu trữ nó trong mảng bộ nhớ cache.

Đây là những gì bạn kết thúc với:

static int cardGameValue(int[] D, int first, int last) { 
    scores = new int[last + 1, last + 1]; 
    return cardGameValue(D, first, last, scores); 
} 

static int cardGameValue(int[] D, int first, int last, int[,] scores) { 
    // If we have at most 1 card, our score is 0: 
    if (first >= last) 
     return 0; 

    // Otherwise, get the score from the cache array. 
    // If it is positive, return the value. 
    int score = scores[first, last]; 
    if (score > 0) 
     return score; 

    // Keep the original first and last 
    // for filling in the computed value later. 
    int firstOriginal = first; 
    int lastOriginal = last; 

    // Let the opponent pick a card: 
    if (D[first] <= D[last]) 
     last--; 
    else 
     first++; 

    // Choose our best card: 
    int left = D[first] + cardGameValue(D, first + 1, last, scores); 
    int right = D[last] + cardGameValue(D, first, last - 1, scores); 
    score = Math.Max(left, right); 

    // and enter the score into the cache array: 
    scores[firstOriginal, lastOriginal] = score; 

    // Finally, return the computed score. 
    return score; 
} 

Ngay cả đối với 300 thẻ, điều này chạy trong vòng chưa đầy 1 millisecond trên máy tính của tôi.

Answer 2

Bạn có thể thử lập trình động, chỉ lưu trữ kết quả trung gian trong một số cấu trúc dữ liệu phù hợp và khi bạn cần gọi một cuộc gọi đệ quy, chỉ cần sử dụng giá trị đã lưu!

Bạn có thể sử dụng mảng 2-D là int giây để lưu trữ kết quả. Phần tử tại [i][j] sẽ lưu trữ kết quả của trò chơi với boong tàu D[i] đến D[j]. Bắt đầu với hàng 0, sau đó sử dụng kết quả lấp đầy hàng 1, v.v. Điều này sẽ tính toán kết quả trong thời gian O (n^2).

Answer 3

Những dòng này phân bổ đối tượng Danh sách mới, chưa kể phương thức GetRange tạo đối tượng Danh sách mới, vì vậy có tổng cộng 4 đối tượng Danh sách mới được tạo bởi 2 dòng mã này mỗi lần thực thi. Điều này có thể tương đối đắt nếu bạn có một số lượng lớn các mục trong danh sách.

 int left = cardGameValue(new List<int>(D.GetRange(1, D.Count - 1)), myScore + D[0], opponentScore); 

     int right = cardGameValue(new List<int>(D.GetRange(0, D.Count - 1)), myScore + D[D.Count - 1], opponentScore); 

Bạn có thể sửa đổi chữ ký phương thức của mình để có tham số startIndex và chiều dài để mọi cuộc gọi tới thẻGameValue đều có thể sử dụng lại cùng một thể hiện Danh sách.

static int cardGameValue(List<int> D, int startIndex, int length, int myScore, int opponentScore) 

lẽ làm cho các cuộc gọi đệ quy như thế này:

 int left = cardGameValue(D, startIndex + 1, length - 1, myScore + D[startIndex], opponentScore); 

     int right = cardGameValue(D, startIndex, length - 1, myScore + D[startIndex + length - 1], opponentScore); 

ví dụ: Mã đề cập đến chỉ số 0 như D[0] và D.RemoveAt(0) sẽ cần phải được sửa đổi để sử dụng startIndex, chẳng hạn như D[startIndex] và D.RemoveAt(startIndex). Mã đề cập đến D.Count cần phải được thay thế bằng startIndex + length. Chỉnh sửa: Mã đề cập đến D.Count - 1 cần phải được thay thế bằng length - 1 hoặc startIndex + length - 1 (tùy thuộc vào ngữ cảnh), nhưng mã chỉ đề cập đến D.Count sẽ chỉ được thay thế bằng length.