[理工] 算法minimum edit distance

楼主: z0953781935 (123)   2017-10-16 15:07:14
如题,做 minimum edit distance算法时遇到一个问体
若表格中的某一空格左上是最大的数,
上面跟左边则是一样的数但小于左上,
譬如上跟左皆是3,左上是4,那这样右下的方向是要往哪边?
怎么有时后上有时候左,方向不对backtracking过程就不对了
https://i.imgur.com/Q8tglGB.jpg
作者: can18 (18号)   2017-10-16 16:12:00
应该是都可以 因为那几种方法edit的cost都一样这个问题的答案本来就不一定唯一( 最小cost一定唯一 但过程不一定唯一)
楼主: z0953781935 (123)   2017-10-16 16:33:00
可是最右下角的箭头往上的过程完全不对完全碰不到删除更正:只有一个删除,但还是不对
作者: can18 (18号)   2017-10-16 17:36:00
什么叫过程不对?
楼主: z0953781935 (123)   2017-10-16 18:24:00
就一个字串转成另一个字串的动作,有增加删除转换三动作动作的这样排起来不对序列一样,抱歉,指上指左没差刚刚跟朋友碰面太晚确认了

Links booklink

Contact Us: admin [ a t ] ucptt.com