Доброго времени суток!
Столкнулся с такой задачей: есть n уравнений, записанных в символьном виде, необходимо оптимизировать количество операций для их вычисления (пока для простоты подразумевается только сложение). Вот пример:
Исходная система уравнений:
x1 = a + b + c
x2 = a + d + c
x3 = a + e + c
В результате должно получиться следующее:
r1 = a + c
x1 = r1 + b
x2 = r1 + d
x3 = r1 + e
Здесь r1 - это замена повторяющейся операции a + b
. Легко видеть, что количество сложений уменьшилось с 6 до 4. Все это хорошо, но с маленькими уравнениями, а вот когда количество переменных переваливает за несколько сотен - надо писать программу.
Реализовывать алгоритм мне необходимо на C/C++.
После длительного гугления, я выяснил что это называется common subexpression elimination (или удаление общих подвыражений). Однако, как написать программу или каким именно методом такое можно реализовать я так и не понял. И поэтому придумал свой велоспед.
Суть велосипеда в следующем:
Входными данными является набор строк. Каждая строка представляет собой одно уравнение, например: abc
- это x1 = a + b + c
Алгоритм действий следующий:
1) упорядочиваем все переменные всех уравнений (ибо он могут быть записаны не по порядку)
2) создаем для каждого уравнения битовый вектор
3) Используя побитовый AND складываем все уравнения и ищем вектор с максимальным количеством установленных бит
4) Добавляем новое уравнение составленное из бит полученных на предыдущем шаге
5) Повторяем все шаги пока не получим нулевой вектор
Я сильно сомневаюсь, что иду правильным путем. Подскажите, пожалуйста, может кто-то сталкивался с подобными алгоритмами, или натолкнете на идею/книгу/библиотеку?
P.S. Сорри если сумбурно, я уже совсем замучался((