algorithm - simplificacion - Estrategias para simplificar expresiones matemáticas

simplificar fracciones algebraicas (6)

Tengo un árbol bien formado que representa una expresión matemática. Por ejemplo, dada la cadena: "1+2-3*4/5" , esto se analiza en:

subtract(add(1,2),divide(multiply(3,4),5))

Que se expresa como este árbol:

Lo que me gustaría poder hacer es tomar este árbol y reducirlo lo más posible. En el caso anterior, esto es bastante simple, porque todos los números son constantes. Sin embargo, las cosas empiezan a ser más complicadas una vez que permito las incógnitas (denotadas con un $ seguido de un identificador):

"3*$a/$a" convierte en divide(multiply(3,$a), $a)

Esto debería simplificarse a 3 , ya que los términos $a deben cancelarse mutuamente. La pregunta es, "¿cómo hago para reconocer esto de manera genérica?" ¿Cómo reconozco que min(3, sin($x)) siempre va a ser sin($x) ? ¿Cómo reconozco que sqrt(pow($a, 2)) es abs($a) ? ¿Cómo reconozco que nthroot(pow(42, $a), $a) (la raíz a de 42 a la potencia a ^th ) es 42 ?

Me doy cuenta de que esta pregunta es bastante amplia, pero hace tiempo que me estoy sacudiendo la cabeza por esto y no he encontrado nada lo suficientemente satisfactorio.

Creo que tienes que "usar la fuerza bruta" tales árboles.

Tendrá que formular un par de reglas que describan posibles simplificaciones. Luego debe caminar por el árbol y buscar las reglas aplicables. Dado que algunas simplificaciones pueden conducir a resultados más simples que otras, tendrá que hacer algo similar para encontrar la ruta más corta en un plan de metro: pruebe todas las posibilidades y clasifique los resultados según algunos criterios de calidad.

Dado que el número de tales escenarios es finito, es posible que pueda descubrir las reglas de simplificación probando todas las combinaciones de operadores y variables y nuevamente tener un algoritmo genético que verifique que la regla no se haya encontrado antes y que realmente simplifique la entrada .

Las multiplicaciones se pueden representar como adiciones, por lo que una regla podría ser que a - a se anula: 2a-a = a + aa

Otra regla sería multiplicar primero todas las divisiones porque son fracciones. Ejemplo:

1/2 + 3/4 Descubre todas las divisiones y luego multiplica cada fracción con el divisor en ambos lados de todas las otras fracciones

4/8 + 6/8 Entonces todos los elementos tienen el mismo divisor y también pueden unificarse a (4 + 6) / 8 = 10/8

Finalmente encuentras el divisor común más alto entre arriba y abajo 5/4

Aplicado a su árbol, la estrategia sería trabajar desde abajo hacia arriba, simplificando primero cada multiplicación convirtiéndola en adiciones. Luego simplificando cada adición como las fracciones

Todo el tiempo verificarías tus reglas de atajo para descubrir tales simplifcaciones. Para saber que una regla se aplica probablemente tengas que probar todas las permutaciones de un subárbol. Por ejemplo, la regla aa también se aplicaría a -a + a. Puede haber un a + ba.

Solo algunos pensamientos, espero que te dé algunas ideas ...

En general, no se puede hacer esto porque, aunque son lo mismo matemáticamente, puede no ser el mismo en la aritmética de la computadora. Por ejemplo, -MAX_INT no está definido, entonces -% a = / =% a. De manera similar para flotadores, debe lidiar con NaN e Inf de manera apropiada.

Esta tarea puede ser bastante complicada (además de la transformación más simple). Esencialmente esto es lo que el software de álgebra hace todo el tiempo.

Puede encontrar una introducción legible sobre cómo se hace esto (evaluación basada en reglas), por ejemplo, para Mathematica .

Mi enfoque ingenuo sería tener algún tipo de estructura de datos con inversas de cada función (es decir, divide y multiply ). Obviamente, necesitaría una lógica adicional para asegurarse de que son realmente inversas, ya que multiplicar por 3 y luego dividir por 4 no es en realidad un inverso.

Aunque esto es primitivo, creo que es un primer paso decente para el problema y que resolvería muchos de los casos que anotó en su pregunta.

Espero ver tu solución completa y mirar con asombro a es brillo matemático :)

Probablemente desee implementar un sistema de reescritura de términos . En cuanto a las matemáticas subyacentes, eche un vistazo a WikiPedia .

Estructura de un módulo de reescritura de términos

Desde que implementé una solución recientemente ...

Primero, prepare una clase CExpression, que modela la estructura de su expresión.
Implementar CRule , que contiene un patrón y un reemplazo. Use símbolos especiales como variables de patrón, que deben vincularse durante la coincidencia de patrones y reemplazarse en la expresión de reemplazo.
Luego, implementa una clase CRule . Es el método principal applyRule(CExpression, CRule) intenta hacer coincidir la regla con cualquier subexpresión de expresión aplicable. En caso de que coincida, devuelve el resultado.
Finalmente, implemente una clase CRuleSet , que es simplemente un conjunto de objetos CRule. El método principal reduce(CExpression) aplica el conjunto de reglas siempre que no se puedan aplicar más reglas y luego devuelve la expresión reducida.
Además, necesita una clase CBindingEnvironment , que asigna símbolos ya coincidentes a los valores coincidentes.

Intenta volver a escribir la expresión en una forma normal

No olvide que este enfoque funciona hasta cierto punto, pero es probable que no sea completo. Esto se debe al hecho de que todas las siguientes reglas realizan reescrituras de términos locales.

Para hacer más fuerte esta lógica de reescritura local, uno debe tratar de transformar las expresiones en algo que llamaría una forma normal. Este es mi enfoque:

Si un término contiene valores literales, intente mover el término lo más hacia la derecha como sea posible.
Finalmente, este valor literal puede aparecer más a la derecha y se puede evaluar como parte de una expresión totalmente literal.

Cuándo evaluar la expresión completamente literal

Una pregunta interesante es cuándo evaluar la expresión completamente literal. Supongamos que tienes una expresión

x * ( 1 / 3 )

que se reduciría a

x * 0.333333333333333333

Ahora supongamos que x es reemplazado por 3. Esto daría algo así como

0.999999999999999999999999

Por lo tanto, la evaluación entusiasta arroja un valor ligeramente incorrecto.

En el otro lado, si mantienes (1/3) y primero reemplazas x por 3

3 * ( 1 / 3 )

una regla de reescritura daría

1

Por lo tanto, podría ser útil evaluar tarde la expresión totalmente literal.

Ejemplos de reglas de reescritura

Así es como aparecen mis reglas dentro de la aplicación: Los símbolos _1, _2, ... coinciden con cualquier subexpresión:

addRule( new TARuleFromString( ''0+_1'', // left hand side :: pattern ''_1'' // right hand side :: replacement ) );

o un poco más complicado

addRule( new TARuleFromString( ''_1+_2*_1'', ''(1+_2)*_1'' ) );

Ciertos símbolos especiales solo coinciden con subexpresiones especiales. Eg _Literal1, _Literal2, ... coinciden solo con valores literales:

addRule( new TARuleFromString( ''exp(_Literal1) * exp(_Literal2 )'', ''exp( _Literal1 + _Literal2 )'' ) );

Esta regla mueve la expresión no literal a la izquierda:

addRule( new TARuleFromString( ''_Literal*_NonLiteral'', ''_NonLiteral*_Literal'' ) );

Cualquier nombre, que comienza con ''_'', es una variable de patrón. Mientras que el sistema coincide con una regla, mantiene una pila de asignaciones de símbolos ya coincidentes.

Finalmente, no olvide que las reglas pueden producir secuencias de reemplazo no terminadas. Por lo tanto, al reducir la expresión, haga que el proceso recuerde, qué expresiones intermedias ya se han alcanzado antes.

En mi implementación, no guardo expresiones intermedias directamente. Mantengo una matriz de hashes MD5 () de expresión intermedia.

Un conjunto de reglas como punto de partida

Aquí hay un conjunto de reglas para comenzar:

addRule( new TARuleFromString( ''0+_1'', ''_1'' ) ); addRule( new TARuleFromString( ''_Literal2=0-_1'', ''_1=0-_Literal2'' ) ); addRule( new TARuleFromString( ''_1+0'', ''_1'' ) ); addRule( new TARuleFromString( ''1*_1'', ''_1'' ) ); addRule( new TARuleFromString( ''_1*1'', ''_1'' ) ); addRule( new TARuleFromString( ''_1+_1'', ''2*_1'' ) ); addRule( new TARuleFromString( ''_1-_1'', ''0'' ) ); addRule( new TARuleFromString( ''_1/_1'', ''1'' ) ); // Rate = (pow((EndValue / BeginValue), (1 / (EndYear - BeginYear)))-1) * 100 addRule( new TARuleFromString( ''exp(_Literal1) * exp(_Literal2 )'', ''exp( _Literal1 + _Literal2 )'' ) ); addRule( new TARuleFromString( ''exp( 0 )'', ''1'' ) ); addRule( new TARuleFromString( ''pow(_Literal1,_1) * pow(_Literal2,_1)'', ''pow(_Literal1 * _Literal2,_1)'' ) ); addRule( new TARuleFromString( ''pow( _1, 0 )'', ''1'' ) ); addRule( new TARuleFromString( ''pow( _1, 1 )'', ''_1'' ) ); addRule( new TARuleFromString( ''pow( _1, -1 )'', ''1/_1'' ) ); addRule( new TARuleFromString( ''pow( pow( _1, _Literal1 ), _Literal2 )'', ''pow( _1, _Literal1 * _Literal2 )'' ) ); // addRule( new TARuleFromString( ''pow( _Literal1, _1 )'', ''ln(_1) / ln(_Literal1)'' ) ); addRule( new TARuleFromString( ''_literal1 = pow( _Literal2, _1 )'', ''_1 = ln(_literal1) / ln(_Literal2)'' ) ); addRule( new TARuleFromString( ''pow( _Literal2, _1 ) = _literal1 '', ''_1 = ln(_literal1) / ln(_Literal2)'' ) ); addRule( new TARuleFromString( ''pow( _1, _Literal2 ) = _literal1 '', ''pow( _literal1, 1 / _Literal2 ) = _1'' ) ); addRule( new TARuleFromString( ''pow( 1, _1 )'', ''1'' ) ); addRule( new TARuleFromString( ''_1 * _1 = _literal'', ''_1 = sqrt( _literal )'' ) ); addRule( new TARuleFromString( ''sqrt( _literal * _1 )'', ''sqrt( _literal ) * sqrt( _1 )'' ) ); addRule( new TARuleFromString( ''ln( _Literal1 * _2 )'', ''ln( _Literal1 ) + ln( _2 )'' ) ); addRule( new TARuleFromString( ''ln( _1 * _Literal2 )'', ''ln( _Literal2 ) + ln( _1 )'' ) ); addRule( new TARuleFromString( ''log2( _Literal1 * _2 )'', ''log2( _Literal1 ) + log2( _2 )'' ) ); addRule( new TARuleFromString( ''log2( _1 * _Literal2 )'', ''log2( _Literal2 ) + log2( _1 )'' ) ); addRule( new TARuleFromString( ''log10( _Literal1 * _2 )'', ''log10( _Literal1 ) + log10( _2 )'' ) ); addRule( new TARuleFromString( ''log10( _1 * _Literal2 )'', ''log10( _Literal2 ) + log10( _1 )'' ) ); addRule( new TARuleFromString( ''ln( _Literal1 / _2 )'', ''ln( _Literal1 ) - ln( _2 )'' ) ); addRule( new TARuleFromString( ''ln( _1 / _Literal2 )'', ''ln( _Literal2 ) - ln( _1 )'' ) ); addRule( new TARuleFromString( ''log2( _Literal1 / _2 )'', ''log2( _Literal1 ) - log2( _2 )'' ) ); addRule( new TARuleFromString( ''log2( _1 / _Literal2 )'', ''log2( _Literal2 ) - log2( _1 )'' ) ); addRule( new TARuleFromString( ''log10( _Literal1 / _2 )'', ''log10( _Literal1 ) - log10( _2 )'' ) ); addRule( new TARuleFromString( ''log10( _1 / _Literal2 )'', ''log10( _Literal2 ) - log10( _1 )'' ) ); addRule( new TARuleFromString( ''_Literal1 = _NonLiteral + _Literal2'', ''_Literal1 - _Literal2 = _NonLiteral'' ) ); addRule( new TARuleFromString( ''_Literal1 = _NonLiteral * _Literal2'', ''_Literal1 / _Literal2 = _NonLiteral'' ) ); addRule( new TARuleFromString( ''_Literal1 = _NonLiteral / _Literal2'', ''_Literal1 * _Literal2 = _NonLiteral'' ) ); addRule( new TARuleFromString( ''_Literal1 =_NonLiteral - _Literal2'', ''_Literal1 + _Literal2 = _NonLiteral'' ) ); addRule( new TARuleFromString( ''_NonLiteral + _Literal2 = _Literal1 '', ''_Literal1 - _Literal2 = _NonLiteral'' ) ); addRule( new TARuleFromString( ''_NonLiteral * _Literal2 = _Literal1 '', ''_Literal1 / _Literal2 = _NonLiteral'' ) ); addRule( new TARuleFromString( ''_NonLiteral / _Literal2 = _Literal1 '', ''_Literal1 * _Literal2 = _NonLiteral'' ) ); addRule( new TARuleFromString( ''_NonLiteral - _Literal2 = _Literal1'', ''_Literal1 + _Literal2 = _NonLiteral'' ) ); addRule( new TARuleFromString( ''_NonLiteral - _Literal2 = _Literal1 '', ''_Literal1 + _Literal2 = _NonLiteral'' ) ); addRule( new TARuleFromString( ''_Literal2 - _NonLiteral = _Literal1 '', ''_Literal2 - _Literal1 = _NonLiteral'' ) ); addRule( new TARuleFromString( ''_Literal1 = sin( _NonLiteral )'', ''asin( _Literal1 ) = _NonLiteral'' ) ); addRule( new TARuleFromString( ''_Literal1 = cos( _NonLiteral )'', ''acos( _Literal1 ) = _NonLiteral'' ) ); addRule( new TARuleFromString( ''_Literal1 = tan( _NonLiteral )'', ''atan( _Literal1 ) = _NonLiteral'' ) ); addRule( new TARuleFromString( ''_Literal1 = ln( _1 )'', ''exp( _Literal1 ) = _1'' ) ); addRule( new TARuleFromString( ''ln( _1 ) = _Literal1'', ''exp( _Literal1 ) = _1'' ) ); addRule( new TARuleFromString( ''_Literal1 = _NonLiteral'', ''_NonLiteral = _Literal1'' ) ); addRule( new TARuleFromString( ''( _Literal1 / _2 ) = _Literal2'', ''_Literal1 / _Literal2 = _2 '' ) ); addRule( new TARuleFromString( ''_Literal*_NonLiteral'', ''_NonLiteral*_Literal'' ) ); addRule( new TARuleFromString( ''_Literal+_NonLiteral'', ''_NonLiteral+_Literal'' ) ); addRule( new TARuleFromString( ''_Literal1+(_Literal2+_NonLiteral)'', ''_NonLiteral+(_Literal1+_Literal2)'' ) ); addRule( new TARuleFromString( ''_Literal1+(_Literal2+_1)'', ''_1+(_Literal1+_Literal2)'' ) ); addRule( new TARuleFromString( ''(_1*_2)+(_3*_2)'', ''(_1+_3)*_2'' ) ); addRule( new TARuleFromString( ''(_2*_1)+(_2*_3)'', ''(_1+_3)*_2'' ) ); addRule( new TARuleFromString( ''(_2*_1)+(_3*_2)'', ''(_1+_3)*_2'' ) ); addRule( new TARuleFromString( ''(_1*_2)+(_2*_3)'', ''(_1+_3)*_2'' ) ); addRule( new TARuleFromString( ''(_Literal * _1 ) / _Literal'', ''_1'' ) ); addRule( new TARuleFromString( ''(_Literal1 * _1 ) / _Literal2'', ''(_Literal1 * _Literal2 ) / _1'' ) ); addRule( new TARuleFromString( ''(_1+_2)+_3'', ''_1+(_2+_3)'' ) ); addRule( new TARuleFromString( ''(_1*_2)*_3'', ''_1*(_2*_3)'' ) ); addRule( new TARuleFromString( ''_1+(_1+_2)'', ''(2*_1)+_2'' ) ); addRule( new TARuleFromString( ''_1+_2*_1'', ''(1+_2)*_1'' ) ); addRule( new TARuleFromString( ''_literal1 * _NonLiteral = _literal2'', ''_literal2 / _literal1 = _NonLiteral'' ) ); addRule( new TARuleFromString( ''_literal1 + _NonLiteral = _literal2'', ''_literal2 - _literal1 = _NonLiteral'' ) ); addRule( new TARuleFromString( ''_literal1 - _NonLiteral = _literal2'', ''_literal1 - _literal2 = _NonLiteral'' ) ); addRule( new TARuleFromString( ''_literal1 / _NonLiteral = _literal2'', ''_literal1 * _literal2 = _NonLiteral'' ) );

Hacer reglas de primera clase expresiones

Un punto interesante: dado que las reglas anteriores son expresiones especiales, que se evalúan correctamente mediante el analizador de expresiones, los usuarios pueden incluso agregar nuevas reglas y así mejorar las capacidades de reescritura de la aplicación.

Expresiones de análisis (o más generales: idiomas)

Para aplicaciones Cocoa / OBjC , DDMathParser de Dave DeLong es un candidato perfecto para analizar sintácticamente expresiones matemáticas.

Para otros idiomas, nuestros viejos amigos Lex & Yacc o el nuevo GNU Bison podrían ser de ayuda.

Mucho más joven y con un enorme conjunto de archivos de sintaxis listos para usar , ANTLR es un moderno generador de analizadores basado en Java. Además del uso puramente de línea de comandos, ANTLRWorks proporciona una interfaz gráfica para construir y depurar analizadores basados en ANTLR. ANTLR genera gramáticas para varios lenguajes de host , como JAVA, C, Python, PHP o C # . El tiempo de ejecución de ActionScript actualmente está broken .

En caso de que quiera aprender a analizar expresiones (o idiomas en general) de abajo hacia arriba, propongo el texto de este libro gratuito de Niklaus Wirth (o la edición de libros alemana ), el famoso inventor de Pascal y Modula. -2.

Quiere construir un CAS (sistema de cálculo de álgebra) y el tema es tan amplio que hay un campo de estudio completo dedicado a él. Lo que significa que hay algunos books que probablemente responderán a su pregunta mejor que SO.

Sé que algunos sistemas crean árboles que reducen las constantes primero y luego colocan el árbol en una forma normalizada y luego usan una gran base de datos de fórmulas probadas / conocidas para transformar el problema en alguna otra forma.