Алгоритм оптимизации вычисления арифметического выражения

Предположим, что у меня есть выражение, образованное целыми переменными и арифметическими операциями: сложение, вычитание и умножение. Я знаю, что каждое умножение занимает M секунд, и каждое добавление/подстановка занимает A секунд. Есть ли алгоритм, который будет вычислять выражение наиболее эффективным способом для произвольного присваивания переменным? (Предположим, что я могу сохранить в памяти только одно число).Алгоритм оптимизации вычисления арифметического выражения

Пример:

М = 10

А = 1

Выражение: а * а + а * Ь + Ь * Ь.

Первоначально он имеет 3 умножений и 2 дополнения, так что общее время составляет 3 * М + 2 * А = 32

Тем не менее, мы можем построить эквивалентное выражение (а + б) * (а + б) -a * b, который имеет только 2 умножения и 3 добавления, поэтому общее время вычисления будет 2 * M + 3 * A = 23.

источник

2013-09-04 Evgenii.Balai

Следует ли учитывать каждый M и A, используемый при расчете решения? ;) –

Да, каждая стоимость умножения равна M, и каждая добавочная стоимость. Вы не можете повторно использовать полученные результаты. (Предположим, вы используете реверсивную нотацию и вычисляете каждый + или * шаг за шагом). –

Я не уверен, поняли ли вы мой вопрос - например, в вашем примере вы описываете общее время вычисления как «2 * M + 3 * A = 23'. Я спрашиваю, что относительно M и A используется при вычислении вашего решения '2 * M + 3 * A = 23'. Возможно, потребуется еще 3 * M и 15 * A для вычисления решения 23. В этом случае сумма будет равна 23 + 45 ... –

Вы хотите применить алгоритм суммарного произведения.

См:

http://www.isiweb.ee.ethz.ch/papers/docu/aloe-2001-1.pdf

источник

2013-09-04 00:35:34 Owen

Я думаю, что здесь это неприменимо. Во-первых, он используется для вычисления маргиналов над продуктом факторов, а не переменных. Во-вторых, это не гарантирует оптимальность с точки зрения количества операций и зависит от выбранного вами выбранного порядка. Если я ошибаюсь, не могли бы вы показать, как использовать его в приведенном выше примере? –

Вы в основном хотите уменьшить количество умножений. Один из подходов заключается в следующем (я не знаю, будет ли в результате сокращения затрат оправдывают сложности алгоритма и стоимости):

Perfom добавление всех операндов, для которых добавление разрешено согласно старшинство операторов.
Форма пар операндов, которые должны подвергаться умножению.
Среди пар выньте общие операнды и добавьте их вместе.
Обновление пары и Гото шаг 3.
Stop, если такие общие пары не осталось. Затем просто выполните оставшиеся вычисления.

Пример: а * Ь + а * C + D * (е + е) выполнять сложение по электронной & F (скажем г = е + е) а * Ь + а * с + д * г пары: (a, b) (a, c) (d, g) a распространен в 1-й двух пар, поэтому мы добавляем b & c.

источник

2013-09-05 17:22:31

Это была моя первая идея. Я не могу доказать, что он всегда дает оптимальный результат. Откуда вы знаете, что нам не нужно будет добавлять что-то в наше оригинальное выражение? Например, при некотором выражении E мы можем добавить к нему a * b, вычислить E + a * b (с возможными упрощениями) и вычесть a * b после этого, чтобы получить исходный результат? Это приводит к бесконечному пространству возможных действий. Как доказать, что всегда лучше сочетать некоторые продукты, чем добавлять что-то новое в выражение? –

Алгоритм оптимизации вычисления арифметического выражения

ответ

Смежные вопросы