GrabDuck

Удаление общих подвыражений

:

Доброго времени суток!

Столкнулся с такой задачей: есть 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. Сорри если сумбурно, я уже совсем замучался((