Как упростить математическую формулу, максимально уменьшив ее
Я буду стремиться быть объективным в этом вопросе.
У меня есть база данных с миллионами математических формул, созданных приложением, это формулы, которые уважают логику:
1) Используются только 5 математических операций: сложение, вычитание, умножение, деление и степень (+ — * / ^)
2) Каждая операция ограничена / сгруппирована в круглых скобках.
«Параметры» могут быть простыми, такими как константа или переменная.
Пример: (х + 15)
В сложном случае я могу иметь:
(х * (х + 15))
Важно помнить, что правильный порядок операций гарантирован с использованием скобок.
Пример:
((х * (х + 15)) / 15)
Моя задача состоит в том, чтобы уменьшить эти формулы.
Они бесполезны или многократно повторяются, когда операции одинаковы и не зависят от порядка факторов.
Пример:
((((х + 4) + 8) — х) / 12)
Это равно 1, это не формула, это константа, и я должен игнорировать это.
А дубликаты типа ((x + 4) + 8) и ((8 + x) + 4) должны быть устранены.
Вот почему мне нужно уменьшить.
Просто чтобы знать, все формулы стандартизированы с круглыми скобками и пробелами между операциями.
Я создал подпрограмму в PHP с использованием регулярных выражений для подстановок, мне удалось добиться огромного прогресса, сократив конкретную формулу с 8 тысяч возможностей до менее трехсот.
Однако по мере увеличения размера (а не сложности, поскольку они не являются сложными) формул моя процедура больше не может быть эффективной.
Мне нужен алгоритм, а не рутина, чтобы применить математическое сокращение, которое мы изучали в школе.
Я думаю, что это возможно, поскольку формулы стандартизированы и ограничены 5 основными математическими операциями.
Я использую класс EvalMath, полученный в GitHub, чтобы помочь в сокращении и выполнении формул.
Чтобы дать вам лучшее представление, формулы являются абстрактными, и каждый «@» заменяется в реальном времени константами и переменными.
(@ + @)
(@ / @)
(@ ** @)
((@ + @) + @)
((@ + @) ** @)
((@ - @) + @)
((@ - @) / @)
((@ - @) ** @)
((@ * @) + @)
((@ * @) / @)
((@ * @) ** @)
((@ / @) / @)
Вот фрагмент кода PHP, который является частью моей процедуры сокращения.
В рамках WHILE (TRUE) я сгруппировал правила, которые повторяются до тех пор, пока не будут сделаны замены.
В конце концов, у меня есть массив с множеством дубликатов, полученных с некоторым сокращением и переупорядочением элементов формулы, что решает array_unique ().
Мне действительно нужна помощь, мой мозг взрывается с этой проблемой.
Спасибо.
<?php
$Math_Formulas = array(
'(((x + 7) ** 9) - 9)',
'(((x ^ 3) - 9) - 5)',
'(((2 + x) + x) * x)',
'(((x + 3) / 6) / 8)',
'(((x - 5) + 6) ** 2)',
'(1024 ^ (x / 5))',
'((3 - (x + 6)) + 3)',
'(((x ^ 3) + 9) * 6)',
);
while (TRUE)
{
$changed = FALSE;
// Rule 1: (x - x) = 0
for ($i = 0; $i < count($Math_Formulas); $i++)
{
$Formula = trim(preg_replace_callback('/([^-]?)([a-z]+?) [-] ([a-z]+?)/', function($matches) {
$Expression = $matches[0];
if ($matches[2] == $matches[3])
{
$Expression = $matches[1] . '0';
}
return($Expression);
}, $Math_Formulas[$i]));
if ($Formula != $Math_Formulas[$i])
{
$changed = TRUE;
$Math_Formulas[$i] = $Formula;
}
}
// Rule 2: ...
if (!$changed)
{
break;
}
}
$Math_Formulas = array_values(array_unique($Math_Formulas));
?>
ОБНОВЛЕНИЕ 1:
Я думаю, что если бы при создании формул использовалась «обратная польская запись», все было бы намного проще, но с имеющимися у меня формулами мне нужно переставить параметры (в алфавитном порядке по возрастанию или по убыванию), чтобы иметь возможность Сравните их.
В РПН:
(х + 4) + 5) становится «х 4 5 +»
(Х + 5) + 4) становится «х 5 4 +»
Как сравнить оба? А как насчет больших функций?
Я думаю, что сделал ошибку, не детализировав технику, использованную в 14 «регулярных выражениях», которые я применяю, чтобы максимально упростить эти формулы. В этом процессе есть нечто большее, чем регулярное выражение:
Исходная формула: (((4 — 5) + х) + 8)
Шаг 1: сложение (или вычитание или умножение) двух-двух констант и сокращение выражения без скобок.
Формула: ((-1 + х) + 8)
Шаг 2: Удалить скобки для ((n + — n) + — n) или (n + — (n + — n)).
Формула: (-1 + х + 8)
Шаг 3: Изменить порядок параметров в алфавитном порядке по убыванию.
Формула: (х + 8 — 1)
Шаг 4: В цикле Шаг 1 выполняется снова.
Окончательная формула: (х + 7)
Есть больше преобразований, например (x + x + x) становится (3 * x), (-x + x) становится 0.
Все это было прекрасно, но когда я натолкнулся на такие функции, как ((x * 9) * (x * 5)) / 9), эта логика потеряла эффективность. Мне нужно было бы создать еще как минимум 14 других вложенных правил.
Решение
Разрешить только четыре операции (+ - * /), все эти выражения представляют собой так называемые рациональные дроби, то есть отношение двух полиномов.
Действительно, применяются следующие правила:
p/q + p'/q' = (pq' + p'q)/pq
p/p.p'/'q = (pp')/(qq')
(p/p')/(q/q') = (pq')/(p'q)
так что комбинация двух рациональных дробей также является рациональной дробью.
Вы можете реализовать систему, в которой каждое выражение описывается как пара полиномов (с целыми или рациональными коэффициентами), и интегрировать приведенные выше формулы. Это по существу требует полиномиального сложения и умножения.
Иногда числитель и знаменатель будут иметь общие факторы, которые должны быть упрощены. Вы можете определить их с помощью алгоритма Евкидиана по полиномам, давая полиномиальный GCD. (Тогда вам нужно также полиномиальное деление.)
Благодаря этой системе упрощения придут сами по себе. Кроме того, выражение нормализуется, так что вы можете обнаружить дубликаты.
Если существует одна переменная, полиномы будут одномерными, и их представление будет простым. Для нескольких переменных это становится немного более сложным.
Теперь, если вы разрешите возведение в степень, можно выделить два случая:
-
показатели могут быть только положительными целыми числами: тогда вы можете расширить
p^nа такжеq^nдругим многочленам по правилу многочленов (но размер будет быстро расти); -
Показатели степени могут быть рациональными константами или функциями переменной: весь метод ломается.
Последнее замечание:
В конце концов, вам нужно будет создать упрощенное правило оценки, представляющее собой отношение двух полиномов. Эффективный способ выразить такую оценку — схема Хорнера. В некоторых случаях это вернет вас туда, откуда вы начали!
Пример:
упрощать
(1 - x / y) (x + y) + (x * x) / y
шаги:
1 - x / y => (y - x) / y
x + y => (x + y) / 1
(y - x) / y . (x + y) / 1 => (y² - x²) / y
x * x => x² / 1
y => y / 1
(x * x) / y => x² / y
(y² - x²) / y + x² / y => y³ / y²
y³ / y² => y / 1
Другие решения
Таким образом, общая схема заключается в том, чтобы сначала преобразовать выражение в формат дерева выражений. Это древовидная структура, где каждый узел представляет собой математическую операцию, число или переменную. Вы можете использовать алгоритм маневрового двора, чтобы выполнить преобразование, и вы можете обнаружить, что evalmath может быть изменен для создания дерева, а не просто для его оценки. Вероятно, есть другие библиотеки Python, которые могут делать больше, чем evalmath.
Когда у вас есть древовидная структура, вам станет намного легче манипулировать. Вы можете манипулировать небольшими поддеревьями для создания более простых форм, применяя некоторые математические правила, которые вы выучили в старшей школе.
Например, вы можете расширить скобки. Выражение (x + 3) * (x + 5) будет представлено в виде дерева как
*
+ +
x 3 x 5
это дерево может быть переписано как x ^ 2 + 8 x + 15
+
^ +
x 2 * 15
x 8
Общая схема, вероятно, будет расширять все ваши скобки. Тогда соберите одинаковые термины и упростите.