método de recursión en C#

Question

Este es mi código:

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; 
      } 
     } 
    } 
} 

Mi código toma un conjunto de cartas y representa su puntuación máxima posible cuando se juega contra un oponente determinista. Después de cada jugada de tu oponente tienes 2 opciones hasta que todas las cartas sean elegidas. ¿Hay alguna manera de almacenar de alguna manera mis resultados de las iteraciones para poder mejorar mi algoritmo? Entonces, ¿la recursión no hace iteraciones innecesarias? Porque después de 40 o 50 cartas, se vuelve muy lento.

Answer 1

Solo tiene acceso al primer o al último elemento de la lista D. En lugar de pasar la lista exacta, puede pasar la lista completa de tarjetas (o incluso mejor: como una matriz int) junto con el índice de la primera y la última posición.

Es mucho más rápido calcular la puntuación del oponente después de completar el cálculo: myScore y opponentScore suman la suma de los valores de las cartas, por lo que puede hacerlo en el tiempo O (n). De esta forma, puede eliminar todo el código que actualiza opponentScore.

No necesita pasar myScore tampoco. Si deja que cardGameValue devuelva la mejor puntuación obtenida de solo las cartas restantes.

Finalmente, si trabaja con el primer y último índice, puede almacenar el puntaje en una matriz 2D, indexada por first y last.Si todas las cartas tienen valores positivos, entonces la puntuación debe ser positiva si quedan al menos dos cartas.

Por lo tanto, al comienzo de la llamada, verifica si la puntuación en la memoria caché es positiva. Si es así, puede devolverlo de inmediato. De lo contrario, debe calcularlo y luego almacenarlo en la matriz de caché.

Esto es lo que usted termina con:

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; 
} 

Incluso para 300 tarjetas, esto se ejecuta en menos de 1 milisegundo en mi máquina.

Answer 2

Puede probar la programación dinámica, simplemente almacene los resultados intermedios en una estructura de datos adecuada, y cuando necesite invocar una llamada recursiva, ¡simplemente use el valor almacenado!

Puede usar una matriz 2-D de int s para almacenar los resultados. El elemento en [i][j] almacenará el resultado del juego con el mazo D[i] hasta D[j]. Comience con la fila 0, luego usando los resultados llene la fila 1, y así sucesivamente. Esto calculará el resultado en O (n^2) tiempo.

Answer 3

Estas líneas asignan nuevos objetos List, sin mencionar que el método GetRange crea un nuevo objeto List, por lo que hay un total de 4 nuevos objetos List creados por estas 2 líneas de código cada vez que se ejecutan. Esto podría ser relativamente costoso si tiene una gran cantidad de artículos en la lista.

 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); 

Es posible que pueda modificar su método de firma para tomar parámetros startIndex y longitud de manera que cada llamada a cardGameValue puede volver a utilizar la misma instancia de lista.

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

tal vez hacer las llamadas recursivas como este:

 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); 

es decir, código que se refiere al índice de 0 como D[0] y D.RemoveAt(0) tendría que ser modificado para utilizar startIndex, como D[startIndex] y D.RemoveAt(startIndex). El código que hace referencia a D.Count debería repararse con startIndex + length. Corrección: El código que hace referencia a D.Count - 1 debería reemplazarse con length - 1 o startIndex + length - 1 (según el contexto), pero el código que solo hace referencia a D.Count simplemente se reemplazará por length.