- 【Updated on May 12, 2025】 Integration of CiNii Dissertations and CiNii Books into CiNii Research
- Trial version of CiNii Research Knowledge Graph Search feature is available on CiNii Labs
- Suspension and deletion of data provided by Nikkei BP
- Regarding the recording of “Research Data” and “Evidence Data”
An A* Algorithm for Computing Edit Distance between Rooted Labeled Unordered Trees
Description
In this paper, we design an A* algorithm for computing the edit distance between rooted labeled unordered trees. First, we introduce some lower bounding functions that provide the constant factor lower bounds on the edit distance. Then, by using the lower bounding functions as a heuristic function, we design the A* algorithm as the best-first search for the edit distance search tree. Finally, we give experimental results for the A* algorithm.