Производное выражение дерева java - PullRequest
Новая
       8

Производное выражение дерева java

1 голос
/ 17 марта 2012

Я пытаюсь реализовать метод, который возвращает новое дерево, выражающее производную выражения.У меня есть дерево оригинальных выражений, а также точная копия в моем распоряжении.Я знаю, что могу к этому рекурсивно использовать правила дифференцирования и базовые случаи, когда узел является константой или числом.Но у меня возникают проблемы, когда я не могу понять, как хранить новые выражения.

Мне не нужен точный ответ, просто несколько советов / рекомендаций о том, как сохранить новое выражение?* Диаграмма полезна, спасибо!Я получаю там, однако все еще возникают проблемы с реализацией рабочего кода.

  if(this.getValue().equals("mult")){
        this.deepCopy().setValue("add");
        this.deepCopy().getRightChild().setValue("mult");
        this.deepCopy().getLeftChild().setValue("mult");
        // not sure what to recursively here!

        }

Ответы [ 2 ]

0 голосов
/ 17 марта 2012

В основном вы начинаете с корня исходного дерева и идете вниз, вычисляя производные для узлов, когда это становится необходимым. Например, поскольку D fg = f'g + fg ', для узла умножения выведите сумму произведений: 

           ....                   ....
             \                      \
              *                      +
             / \           ->       / \
            F   G                  *   *
                                  / \ / \
                                 F' G F G'

А откуда вы берете F 'и G'? Вот где начинается рекурсия.

Обновление: в принципе, вы не так уж и далеко, вам просто нужно заполнить поддеревья для умножения: 

Node right = this.deepCopy().getRightChild();
Node left = this.deepCopy().getLeftChild();
right.setLeftChild(derivative(this.getLeftChild()))   // F'
right.setRightChild(this.getRightChild()))            // G
left.setLeftChild(this.getLeftChild())                // F
left.setRightChild(derivative(this.getRightChild()))) // G'

Хотя я должен сказать, что API выглядит немного странно. deepCopy всегда возвращает один и тот же объект? Его название предполагает, что он делает новую копию каждый раз.

0 голосов
/ 17 марта 2012

Очевидный ответ - использовать язык, который был разработан для символического манипулирования формулами.Подсказка: это началось до 1960 года, и это четырехбуквенное слово.

Посмотрите, возможно, есть несколько новых методов в этой области: http://www.autodiff.org/

http://www.cs.berkeley.edu/~fateman/papers/ADIL.pdf

...