[理工] 演算法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