知识卡片
编辑距离依赖允许操作成本
编辑距离在给定操作集与费用下,是把源串变成目标串的最低费用操作序列成本。
本题允许复制、替换、删除、插入、交换相邻字符与末尾清除,各有不同费用;若操作集或费用改变,距离与最优操作序列也会变。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第14章 动态规划 · 查看原书依据
the edit distance from x to y is the cost of the least expensive operation sequence that transforms x to y.
参考来源
- 位置:《算法导论(第4版)》第 14 章问题与章末注释(`OEBPS/chapter014.xhtml`,文本字符 [100000, 110000);图 14.12、Art_P482)。
- 结论依据:问题14-5(a) 把编辑距离定义为给定操作费用下的最低变换成本;题设列复制、替换、删除、插入、相邻交换、末尾清除等操作。
- 原始内容:the edit distance from x to y is the cost of the least expensive operation sequence that transforms x to y .