Maximizando una expresión algebraica usando corchetes

Question

Es una especie de acertijo: dada una lista de números $\alpha_1 \dots \alpha_n$ y operadores $o_1 \dots o_{n-1}$ que solo pueden ser $\times\, \mbox{o}\, + $ si lo anterior es una expresión algebraica específica en la forma $\alpha_1 o_1 \alpha_2 \dots \alpha_{n-1} o_{n-1} \alpha_n$ ¿qué configuración de paréntesis maximizaría el valor de la expresión dado que $\forall i \,\alpha_i \geq 1 \in \mathbb{N}$?

¿Es suficiente colocar paréntesis solo sobre la serie de $+$ en la expresión? He comprobado esta regla con $a_1 + a_2 \cdot a_3$ y $a_1 + a_2 \cdot a_3 +a_4$ pero no pude encontrar un contraejemplo.

Answer 1

Suponiendo que estos son enteros positivos, podemos usar una técnica de programación dinámica para resolver este problema.

Se nos da un problema similar al problema de multiplicación de matrices (n matrices), donde se debe determinar el orden óptimo de paréntesis para maximizar la expresión total; este problema es similar en estructura.

1. Subproblemas

Supongamos que se nos da la expresión: A[1] o A[2] o A[3] o ... o A[n]. Para maximizar la expresión usando programación dinámica, nuestra conjetura para la solución tendría que ser una que maximice la última operación (multiplicación/adición) - es decir, necesitamos recorrer todas las combinaciones de paréntesis para encontrar el mayor valor. En particular, estamos interesados en todas las combinaciones de k, de manera que:

(A[1] o ... o A[k]) o (A[k+1] o ... o A[n]) se maximice, lo que significa que podemos elegir k' de modo que
   /           \
  /             \
 /               \
/                 \
(A[1] o ... o A[k']) o (A[k'+1] o ... oA[k]), y así sucesivamente.

Nos interesa encontrar el valor óptimo de la expresión A[:k] y A[k+1:], y luego combinarlos basándose en el operador que separa la expresión prefija y sufijo. Como podemos ver en nuestro resultado anterior, también estamos interesados en la prefija y sufija de la "cadena" A. Por lo tanto, nuestro subproblema se reduce a encontrar la mejor colocación de paréntesis de una "subcadena" de valores A(i->j), de manera que

(A[i] o A[i+1] o ... o A[k]) o (A[k+1] o ... o A[j]) se maximice, donde k toma valores de i->j => k = O(n) (en el peor caso, recorremos toda la lista)

Hay n^2 subproblemas de este tipo (esto se desprende del hecho de que hay Theta(n^2) subcadenas en una cadena de tamaño n).

2. Definición recursiva del valor óptimo

Nuestra definición general de recursión describe encontrar el valor óptimo para la expresión al variar 'k' sobre la subcadena dada:

optVal(i,j) = max{optVal(i,k) o optVal(k+1,j) para k:i->j}, donde 'o' es el operador '+' o '*'

3. Tiempo por subproblema

Como podemos ver arriba, cada subproblema encuentra el valor máximo de la expresión al variar k sobre i->j, o a lo sumo n valores.

Por lo tanto, la complejidad temporal del subproblema es O(n).

4. Pseudocódigo

Tenemos que considerar dos casos en la recursión :

 1. op = '+'
 2. op = '*'

Entonces, la recursión para el valor óptimo se ve algo así :

optVal(inp){ 

si(|inp| == 1) 
  devolver inp[1] // caso base 
sino
  opt_val = 0;
  para(k=2; k

``

5. Análisis del tiempo de ejecución

El tiempo de ejecución de esta solución se puede definir de la siguiente manera

T(n) = # de subproblemas * tiempo/subproblema

usando nuestros resultados de las secciones 1 y 2 anteriores, tenemos

T(n) = n^2 * O(n) = O(n^3)

6. Argumento de corrección

En el problema anterior, podemos ver que no importa cómo pongamos paréntesis a una subexpresión, tiene que haber alguna operación final que se realice. Mencionamos anteriormente que la colocación final de paréntesis de A[i] o A[j] debe ser de la forma (A[i]...A[k] ) o (A[k+1]..A[j]), para k:i->j - observamos aquí que no importa la elección de k, también las expresiones (A[i]...A[k]) y (A[k+1]...A[j]) también deben evaluarse de manera óptima. Si no es así, entonces existiría otra solución óptima que podría resolver cualquiera de estos subproblemas dados de manera óptima - pero esto no puede suceder, porque podríamos maximizar la expresión reemplazando la solución actual del subproblema con una solución óptima en su lugar. Por lo tanto, hemos construido la solución a este problema de optimización para el caso general (i,j) en términos de subproblemas más pequeños (pero aún óptimos). Entonces, la solución final se puede derivar maximizando el valor sobre todas las soluciones óptimas en la subexpresión A(i,j) dejando que k vaya de i->j.

``

Answer 2

Su intuición es correcta y lo demostraré. $\def\nn{\mathbb{N}}$

Solución

Observa que cada expresión corresponde a un árbol binario completo (cada número es un nodo hoja y cada operación es un nodo interno con exactamente dos nodos hijos). Por lo tanto, podemos definir la profundidad de una operación como la distancia desde el nodo raíz.

Comienza desde cualquier expresión de la forma permitida.

Cuando $E$ tiene alguna subexpresión de la forma "$( a \times b ) + c$":

  Sustituye esa subexpresión en $E$ con "$a \times ( b + c )".

  Entonces el valor de $E$ no disminuye porque:

    $+,\times$ en $\nn^+$ son positivos y aumentan en cada uno de sus entradas.

    Así que $ac \ge c$ porque $a \ge 1$, y por lo tanto la expresión sustituida tiene un valor mayor.

  Además, la profundidad total de las operaciones de multiplicación ha disminuido.

Hacemos lo mismo cada vez que $E$ tiene alguna subexpresión de la forma "$a + ( b \times c )$", y repetimos estas dos modificaciones en la nueva expresión siempre que se puedan realizar.

Eventualmente debemos detenernos porque la profundidad total de las operaciones de multiplicación es un número entero. En ese punto, $E$ no puede tener ninguna multiplicación que sea un nodo hijo de una suma, y por lo tanto no puede tener ninguna multiplicación antes de la suma en absoluto.

Por lo tanto, cada expresión tiene un valor menor que alguna expresión que hace todas las sumas antes de todas las multiplicaciones. Es fácil verificar que todas esas expresiones tienen el mismo valor, y así hemos encontrado la solución óptima.

Notas

Observa que la sustitución no funcionará si se permiten que los números sean cero. La solución óptima todavía se puede describir, pero no tan simplemente. Básicamente primero ponemos paréntesis alrededor de los bloques que contienen solo multiplicaciones y al menos un cero que no está en ningún extremo (es decir, de la forma "$a \times \cdots \times b \times 0 \times c \times \cdots \times d$"). Luego realizamos todas las sumas antes de todas las multiplicaciones. La prueba sería similar a la anterior.