branch-and-bound - 编辑距离算法的分支定界方法

Question

我正在尝试对edit distance算法实施分支定界方法。我在互联网上找不到任何提示。谁能帮我进入算法的轨道。

Answer 1

我很抱歉将其发布为答案，我想将其添加为评论，但我没有足够的声誉来添加评论。

尝试在图相似性问题的背景下而不是在编辑距离算法的背景下进行该主题的文献搜索；先验是一个更普遍且经过充分研究的问题，找到最小编辑距离的问题属于该问题。您的编辑距离问题的任何实例中的字符串都可以描述为简单的有向图，并且编辑距离算法中的插入/删除和替换操作在图相似性问题中具有相似的操作（例如，顶点的插入和边/删除）顶点和边/改变边上的标签等等）。