Algorithm for computing unordered tree edit distance
A student of ours recently looked into a dynamic programming A* algorithm for computing the unordered tree edit distance (although we adapted it for the ordered tree edit distance). I was not directly involved into this project, but as far as I know, this algorithm explores a search tree that represents all possible edit distances and stops exploring unpromising paths. This way it returns the tree edit distance in the end.

The student also implemented this A* algorithm, so it is not just a theoretical one.

Here's the link: http://ieeexplore.ieee.org/document/6630333/

Hope this helps!